https://atcoder.jp/contests/abc394/tasks/abc394_d隣合うの2文字がマッチしたらそれらを削除してつなぎ合わせればよいので、リスト構造を使えばよいです。それをVecで作ればRustでも簡単に書けます。 // Colorful Bracket Sequence #![allow(non_snake_cas…

https://atcoder.jp/contests/abc393/tasks/abc393_d要するに1の移動距離の和を求めればよいですが、1の位置の累積和を計算しておけばどこを中心に集まるかを決めるとO(1)で求められるので、全ての中心について計算すればよいです。 // Fine Triplets #![all…

https://atcoder.jp/contests/abc392/tasks/abc392_gA + C = 2B なので、A+Cを計算して2Bと合うか調べればよいです。 A+Cは入力例1なら、を計算すればよいです。これはふつうに計算すれば多項式の長さの2乗の計算量ですが、畳み込みはフーリエ変換すれば単な…

https://atcoder.jp/contests/abc392/tasks/abc392_f平衡木が書ければ解けるのは明らかなのですが、今までAIでもなかなか書けませんでした。今回も最初は書けなかったのですが、Pythonでふつうの木を書いて、これを平衡木にと指定したらPythonでは書けました…

https://atcoder.jp/contests/abc392/tasks/abc392_eUnion-Findを使ってグラフを連結していきますが、連結に寄与しない、すなわちrootが同じになるエッジをためておいてあとで連結に使います。 // Cables and Servers #![allow(non_snake_case)] use std::co…

https://atcoder.jp/contests/abc392/tasks/abc392_d総当たりするだけですね。ただし、同じ値はHashMapでまとめておきます。 // Doubles #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// fn r…

https://atcoder.jp/contests/abc391/tasks/abc391_fA, B, Cを降順に並べ直すと、と取ればが最も大きくなります。その次は、のどれかになります。PriorityQueueを使えば簡単にK番目を求められます。 PriorityQueueに重複してTripletを入れてはいけないのでHa…

https://atcoder.jp/contests/abc391/tasks/abc391_e三分木を作って、再帰的に何回変えればいいか数えます。入力例1なら、010011101を三分割して011だから、1のどちらかを0にすればよいです。最初の1も次の1も1回変えれば0になるので、答えは1です。 // Hier…

https://atcoder.jp/contests/abc391/tasks/abc391_d同じXで集めてYが小さいほうから積みます。そうしたときに、下から同じ層のブロックが全て揃っていなければその層のブロックは消えることはありません。全て揃っているとき、消える時間は最大の高さと同じ…

https://projecteuler.net/problem=100トータルのディスクの数をn、青いディスクの数をmとすると、 これを変形して、 これはPell方程式です。解は、 と書けます。 import sys #################### process #################### # x^2 - 2y^2 = -1 fn next_…