競プロでテスト用のライブラリを整備した。vscodeでコマンド1つで愚直解との比較を実行できる。

https://github.com/Kiterai/compro-template

当初はソースコードをmain.cppとtest.cppに分けるつもりではなく、良い感じに入力を受け取る部分をライブラリ化してフラグ次第でテストを実行する感じにしようと思っていたが、cin/coutで入出力するだけの素朴なコードを書くのをやめるのはあまりにも耐えがたいという結論になった。

そこで、cout/cinの入出力先を変更してファイルなどに書き出し結果を見る方策を思いついた。これでcout/cinを使う素朴なコードを書き換えずに流用することができる。さらにtest.cppに分けてvscodeのタスクで別扱いにすることによって、テストと本実行をソースコード上で切り替える必要すらなくなった。テストしたくなればtest.cppにテストコードを書けばいいし、テストが終わったらmain.cppのコードを提出すればよい。

今日のABCでは出番がなかったが、今後ARCの難しい問題とかで必要に迫られたときにスッと出せるのは絶対にアドになるはず。

---

ABC297に出た。初橙パフォーマンス！Highest更新！勝ちまくりモテまくり！

A: n-1か所の隣接部を確認すればよい。こんな問題多くない？

B: 丁寧に実装するだけ。ややめんどい。

C: 入れられるところへ貪欲に端から入れて問題ない。

D: 一般性を失わずA<Bとする。$\lceil(B-A)/A\rceil$回AをBから引くことが出来るので引く。これを繰り返すだけでよい。計算量解析としては、一回これをやるたびにBが半分以下になることが証明できるので$O(\log \max(A,B))$で解けることが分かる。B≧2Aのとき、BはA以下になるので元の半分以下。B<2Aのとき、B-A<1/2Bなので元の半分以下。

E: Nが小さいところが狙い目。setに分かっている払い方を詰めることにして、一番小さいものから順に取り出してそこからの遷移先を新たに詰めればよい。$O(NK\log (NK))$くらいで解ける。

F: 期待値の定義から、求めるべきは$\sum_{A=1}^H \sum_{B=1}^W (最小長方形がA\times Bになるパターン数)\times A\times B$となる。「最小長方形がA×Bになるパターン数」を求めるのはつらいが、「A×Bの長方形にKマスを収めるパターン数」は単純に$_{AB}C_K$で求められるので、これを起点に包除をやっていくと良さそうな感じがする。

ここには最小長方形が(A未満)×(B未満)であるような選び方が含まれているので、それを取り除いていけばよい。(A未満)×(B未満)の最小長方形のパターン数は全て求まっているものとすると、それら全てを取り除けばよい。A×Bの長方形に収めるパターン数には、P×Qの最小長方形のパターンが$(A-P+1)\times(B-Q+1)$個含まれているのでこれを差し引く。最後に、(A×Bの最小長方形のパターン数)×(H-A+1)×(W-B+1)の総和を取ればよい。これでとりあえず愚直$O(H^2W^2)$で解ける。

あとはこれを高速化する。単純に総和を取れば良いかと思いきや、$(A-P+1)\times(B-Q+1)$という係数が変化するので厳しい。式を展開すると項ごとに分離できるので、4つに分離して総和を取ると通る。積の和典型というやつ？

G: 先手後手が平等なゲームが複数並立しているので、全てGrundy数を求めてxorとればよい。問題は各ゲームのGrundy数を求める方法。

正直なんも良い考えが思い浮かばなかったので、例示は理解の試金石！！って言って数学ガールを盾にしながら小さいN,L,Rで実験したら$\lceil (N%(L+R))/L \rceil$という式が見えた。未証明でこれにしたらなんか通った。ラッキー！証明しろ。

Ex: 時間$O(N^4)$の空間$O(N^3)$の愚直DPは書けたが、そこから先はどうにもできなかった。