https://atcoder.jp/contests/abc425/tasks/abc425_d新たに黒く塗ったセルの隣のセルが次に塗れるセルの候補なので、それを集めて塗れるか判定します。 // Ulam-Warburton Automaton #![allow(non_snake_case)] use std::collections::HashSet; ////////////…

https://atcoder.jp/contests/abc424/tasks/abc424_ePriority Queueを使って長い棒から順に切断していくだけですが、元の棒が同じものはまとめて切らないと間に合わないけれど、端数が出るときは調整して、Priority Queueにそのまま戻さないといけません。 /…

https://atcoder.jp/contests/abc424/tasks/abc424_d1行ごとのDPにします。2進法で白に塗ったマスを1にします。それを状態として、値を白に塗った箇所の個数で、これを最小化します。 // Sum of Subarrays #![allow(non_snake_case)] //////////////////// l…

https://atcoder.jp/contests/abc423/tasks/abc423_e典型的な和を取る順番を変える問題ですね。 まず、各が何回現れるか調べます。Lを元の数から1を引いた値とすると、となります。なので、答えは、 ですが、二次式を展開してでまとめると、 となるので、3種…

https://atcoder.jp/contests/abc423/tasks/abc423_dレストラン側で実際に店を出る時間でPriorityQueueに団体客を入れればよいです。 // Long Waiting #![allow(non_snake_case)] use std::cmp::max; use std::collections::BinaryHeap; ///////////////////…

https://atcoder.jp/contests/abc422/tasks/abc422_e過半数が一つの直線に乗っていれば、点をなるべく等分になるように2分割したとき少なくともどちらかが過半数が一つの直線に乗っています。例えば7点で4点直線に乗っていたとき、7点を4点と3点に分けますが…

https://atcoder.jp/contests/abc422/tasks/abc422_d半分にしてなるべく同じになるように分配する、という処理を繰り返します。 // Least Unbalanced #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…

https://atcoder.jp/contests/abc421/tasks/abc421_e今のダイスの状態をキープしたダイスは面の数を負にした数で表します。また、ソートして状態数を減らします。マスクが32通りあるので、その中で最大値を選びます。逆から辿って解答を得ます。 // Yacht #!…

https://atcoder.jp/contests/abc421/tasks/abc421_dRLEが2人で違いますが、分割して同期を取ると簡単になります。 Generic版のPointを今までより強化しました。 // RLE Moving #![allow(non_snake_case)] //////////////////// library ///////////////////…

https://atcoder.jp/contests/abc420/tasks/abc420_dマスごとにドアが元通りと反対になっているときの最小の操作数を記録すればよいです。 // Substr Swap #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library ///////…

https://atcoder.jp/contests/abc413/tasks/abc413_g典型的な分割統治法を使う問題です。障害物がなるべく半数ずつになるように領域を縦か横かで分割して境界を計算して、境界を統合します。各領域の4つの境界は(範囲, グループ番号)のベクトルで表して、統…

https://atcoder.jp/contests/abc419/tasks/abc419_e入力例1なら、長さLの幅にして、 4 2 1 3各列の要素がMの剰余で同じにして、一番上の行を足したらMの剰余で0になるようにします。 DPを使うことを考えて左から右に更新していきます。状態を一番上の行のそ…

https://atcoder.jp/contests/abc419/tasks/abc419_d木を作って指定した範囲に1を足して、最後に偶数ならS側の文字です。 // Substr Swap #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = St</t:>…

https://atcoder.jp/contests/abc418/tasks/abc418_e2点の組み合わせを線分として、全ての線分を方向で分類します。そうすると、同じ類の中の線分の2つの組み合わせが台形になります。ただし、同じ直線内の線分は除きます。 平行四辺形だと二重にカウントし…

https://atcoder.jp/contests/abc418/tasks/abc418_d00なら1に10なら0になどとなるので、1の個数の偶奇が文字列の長さが1短くなるごとに変わります。すなわち、文字列の長さが偶数なら1の数が偶数なら美しい数、奇数ならそうでない、などとなります。ここが…

https://atcoder.jp/contests/abc417/tasks/abc417_f指定した範囲を平均するので、木を作ればよいです。 // Random Gathering #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { le</t:>…

https://atcoder.jp/contests/abc416/tasks/abc416_d足してM以上になるペアをなるべくたくさん作ればよいです。Aを降順、Bを昇順にして、尺取り法的に処理すればよいです。 // Match, Mod, Minimize 2 #![allow(non_snake_case)] //////////////////// libra…

https://atcoder.jp/contests/abc415/tasks/abc415_f二分木を使って、各ノードに左端からどの文字が何文字連続しているか、それに右端とそれ以外も保持しておきます。 // Max Combo #![allow(non_snake_case)] //////////////////// library ///////////////…

https://atcoder.jp/contests/abc415/tasks/abc415_e右と下しか進めないのでDPでよさそうですが、xを決めないで計算しようとすると、今の持ちコインとともに今までのパスで最小のコイン数も保持しないといけなくて大変そうです。しかし、xを決め打ちすれば、…

https://atcoder.jp/contests/abc415/tasks/abc415_d今の瓶の数をnとすると、Aがn以上でA-Bが小さいショップを選べばよいです。なので、BTreeSetでA-B順にショップを並べて、別にAで並べたショップVecを持っておき、ショップのAがnを超えたらBTreeSetとVecか…

https://atcoder.jp/contests/abc414/tasks/abc414_ebとcを決めると取り得るaの個数が決まります。例えば、なら、だから9個です。一般には個になります。なので組合せの個数は、となります。とおけば、となります。内側の和は分母がbで分子は連続でb-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 #![allow(non_snake_…