2025-01-01から1年間の記事一覧
https://atcoder.jp/contests/abc414/tasks/abc414_dまず基地局を各家に設置します。そして、基地局をMまで減らします。そのとき、d離れた家を基地局がカバーすることにすると、電波の強度もdになります。複数の家をカバーする基地局にもう一つ家をカバーで…
https://atcoder.jp/contests/abc413/tasks/abc413_fゴールからはじめて先入れ先出しすればよいです。取り出したグリッドの隣を見てその隣が2つ以上最小移動回数が確定で、小さいほうから2つ目が取り出したグリッド+1なら、最小移動回数が決まります。 // No…
https://atcoder.jp/contests/abc413/tasks/abc413_eよく反転する範囲を調べると、全体を半分にして右半分の最小値が左半分より大きければ、すなわち右半分に1があれば全体を反転するしかないことがわかります。そして、左半分と右半分をそれぞれ同じことを…
https://atcoder.jp/contests/abc412/tasks/abc412_f外にある靴下も合わせてAにして降順にソートします。今外にある靴下がでを取り出したとき、なら終わり、ならをそのままに、ならをそのままにすればよいので、期待値は、 として、 となります。これは少し…
https://atcoder.jp/contests/abc412/tasks/abc412_e素数か素数べきのときしかLCMは変わらないので、それをふるいで見つけます。 // LCM Sequence #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut l</t:>…
https://atcoder.jp/contests/abc412/tasks/abc412_dグラフがループのみで構成されるグラフを全て考えればよいです。ループはノード数が3以上でNが8以下なので、ループは2つ以下なのでちょっと楽です。そのグラフのエッジと与えられたエッジの交差を調べれば…
https://atcoder.jp/contests/abc411/tasks/abc411_f単にエッジの片方のノードを潰して、もう片方のノードに辺を集約します。そのときに減った辺の数を数えます。集約する方のノードは、UnionFindのrootになる方のノードとします。正確には、両方のノードのr…
https://atcoder.jp/contests/abc411/tasks/abc411_e入力例にあるようにどの目とどの目が出たら、というのではなく、この目が最大になる確率を計算します。全ての目を降順にソートして、ついでにそのサイコロで何番目に小さいかをペアにしておきます。最初は…
https://atcoder.jp/contests/abc411/tasks/abc411_dすぐにリスト構造を使えばいいとわかりますが、Rustではなかなか大変です。後ろに追加するリストは難しいので前にcharを追加して、最後に反転させて文字列を作ります。 // Conflict 2 #
https://atcoder.jp/contests/abc410/tasks/abc410_dノードが1000点までで重みも1023までなので、しらみつぶしができます。 // XOR Shortest Walk #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut l</t:>…
https://atcoder.jp/contests/abc409/tasks/abc409_f1500点しかないので、全ての点の距離を調べることができて、それをPriorityQueueに入れれば近い順に取り出すことができます。点を追加したら今までの点との距離を計算してPriorityQueueに入れます。マージ…
https://atcoder.jp/contests/abc409/tasks/abc409_d文字列をVecに変換します。隣同士で数を比較して右の方が小さいところが巡回シフトの最初です。そのあと、さっきの左側より大きい数を見つけます。そこまでが巡回シフトの最後です。 // String Rotation #…
https://atcoder.jp/contests/abc408/tasks/abc408_fDPを低いほうから行います。入力例1で、最初は1で最大回数は0です。次の2も0です。次の3の前に2以上高さが違っていればいいので、1に0をセットして、そして3の前後1の範囲で最大値を求めて1を足したものが…
https://atcoder.jp/contests/abc408/tasks/abc408_eラベルを2進で考えて、上のビットから1が必要かどうか調べます。すなわち1になっていない辺だけで1とNが繋がっているか調べます。 例えば、入力例1は、下から3番目のビットが1でない辺、すなわち4の辺を抜…
https://atcoder.jp/contests/abc408/tasks/abc408_d単なるDPですね。変更後で、まだ一度も0になっていない、1続行中、前に1になって0続行中、の3つの状態が考えられて、値を変更回数とします。 // Flip to Gather #![allow(non_snake_case)] //////////////…
https://atcoder.jp/contests/abc407/tasks/abc407_fこれは典型的な和の順序を変えると解ける問題ですね。すなわち、ある幅を持ったウィンドウをスライドさせて最大値を調べるのではなく、ある値が最大値になる幅を調べます。入力例2で考えると、(値, 場所)…
https://atcoder.jp/contests/abc407/tasks/abc407_d2進数をベクトルと考えて一次独立のものだけ選べばいいと思ったのですが、HWが20以下だからしらみつぶしで十分ですね。左上からそのマスを飛ばすか横のドミノを置くか縦のドミノを置くかの状態遷移すれば…
https://atcoder.jp/contests/abc406/tasks/abc406_e難しい問題ではないです。例の20は1足して21にすると考えやすいです。これを二進にすると10101です。 二進で10000は16ですが、[0, 16)の範囲はまとめて考えられます。1は2個なので、4C2=6通りあります。各…
https://atcoder.jp/contests/abc406/tasks/abc406_d同じxのyと同じyのxを集めるだけですが、時間的けっこう厳しいです。 // Garbage Removal #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line </t:>…
https://atcoder.jp/contests/abc405/tasks/abc405_fエッジの端点をxとyとすると、エッジを平面上の点と考えるます。そうすると、それと交差するエッジの端点(x1, y1)は、1 ≤ x1 < xかつx < y1 < y、または、x < x1 < yかつy < y1 ≤ N*2を満たせばよいです。…
https://atcoder.jp/contests/abc405/tasks/abc405_eまず、リンゴとブドウを並べます。そして、オレンジを配置します。オレンジは各リンゴの左とリンゴとブドウの間に配置できます。リンゴとブドウの間にオレンジをn個置くとします。そうすると、その他のオ…
https://atcoder.jp/contests/abc405/tasks/abc405_dEから幅優先探索するだけですね。 // Escape Route #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().re</t:>…
https://atcoder.jp/contests/abc404/tasks/abc404_e空でない茶碗は処理しないといけないので、空でない茶碗に移動します。問題は空の茶碗しかないときですが、そのときは空でない茶碗を右から探して、そこからDPで空でない茶碗にたどり着く最短手数を求めま…
https://atcoder.jp/contests/abc403/tasks/abc403_fDPなのですが、足し算の結果は次に括弧をつけないと掛け算に使えないところがいやらしいので、掛け算に使えるのと使えないの両方の値を保持しておきます。あと111とかは最初に決めておきます。 // Shortes…
https://atcoder.jp/contests/abc404/tasks/abc404_d動物園に行く回数は3通りなので合計通りです。計算量は、となり十分に間に合います。状態を動物を何回見たかとしますが、1種類の2ビットで表せるので、u128を2つ使えばよいです。同じ状態で最小の金額だけ…
https://atcoder.jp/contests/abc403/tasks/abc403_dDで割った余りで分類してソートします。同じ値ならカウントします。入力例1だと余り1の方は、 (1, 2), (3, 1), (5, 1)DPで削除する個数を最小にするようにします。 D=0の場合は重複を削除するだけです。 /…
https://atcoder.jp/contests/abc402/tasks/abc402_f左上と右下を分けて考えます。入力例2で考えると、左上から7 5 3の対角線上までの経路を考えると、[137], [135, 125], [123]です。あとで100掛けるので、[13700], [13500, 12500], [12300]となります。対…
https://atcoder.jp/contests/abc402/tasks/abc402_d残りの持ち金とどれをすでにクリアしたかでメモ化すればよいです。 // Payment Required #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line =</t:>…
https://atcoder.jp/contests/abc402/tasks/abc402_d2点の番号を足してNで割った余りが同じなら平行です。 // Square Price #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); </t:>…
https://atcoder.jp/contests/abc400/tasks/abc400_dグラフとか考えずに、ふつうにDijkstraっぽくやればいいですね。ただし、距離は0か1進むので、BinaryHeapではなく、VecDequeを用意して、距離0なら前に、距離1なら後ろにpushすればよいです。 // Replace …
