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 #![allow(non_snake_…

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で考えると、(値, 場所)…