yukicoder contest 449

　Dまで四完。

コンテストへのリンク

No.2914 正閉路検出

　解説AC。

　コンテスト中に解けなかったのは仕方ないとしても、解説読まずにACしたい問題でした。

　重み付きUnionFindを使うというのは自然なのに、ちょっと捻った形で出題されると気付けないのは情けない。

No.2915 辺更新価値最大化

　解説AC。

　最短経路問題におけるポテンシャルは、最小費用流のライブラリを作ったときしか勉強しておらず、全く忘れていた。こういうときにも使えるのか。復習になった。

No.2916 累進コスト最小化

　自力AC。

　各cごとにダイクストラをするだけでした。

AtCoder Regular Contest 173

　Cまで三完。レートが上がって嬉しいけど、喜んでいい程の成績でもない……と思っていたけど、ARC/AGCで2200以上のパフォを出したのは去年一回だけだったらしい。なら、喜んでいいかも。

コンテストへのリンク

コンテスト後のツイート

ただし、これだと端がおかしくなるので別計算。計算量は未証明。
端がダメなことはランダムテストを書いて気付いた。
Dは各点からダイクストラ差をgcd取って判定……みたいなのを提出したけど、的外れっぽいね。

— titia (@titia_til) March 10, 2024

D - Bracket Walk

　解説・解説放送を見てAC。

　コンテスト中は迷走していたが、正しい解法は非常にシンプルですね。

　ただ、負閉路判定にベルマンフォード法が使えることをちゃんと覚えていなかった。ベルマンフォード法自体のやり方自体は覚えていたけども……。負の辺があるときの最短距離ではベルマンフォード法を使うというのは覚えていたけれど、負閉路判定にも使えると覚えておきたい。

　この問題やこの問題のsigmaさんの解説も押さえておく。

E - Rearrange and Adjacent XOR

　解説・解説放送を見てAC。

　最後に残る値を実験で求めるパートも難しいし、その後の実装も難しい。

　熨斗袋さんのツイートのように、「偶数個のxorで表せる」というのを、各A[i]に61bit目が立っていると考え、そのbitが0になるような答えを考えるというのが分かりやすいですね。

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264） Fまで
B 1/4をお絵描きした。
C 行・列にbit全探索だが、実装が大変。
D 愚直で良い。Cよりかなり簡単。これはCとD入れ替えるべきでしょ。
E クエリを後ろから見る。実装が面倒。
F DPだが、遷移を立式するのが非常に大変。

— titia (@titia_til) August 13, 2022

G - String Fair

　解説放送を見てAC。

・後ろ二文字を持ってDP

　という方針を思い付けたなら、グラフの問題（最短経路問題）となり、負辺があるのでベルマンフォードを使って解くことができる。

Ex - Perfect Binary Tree

　解説放送を見てAC。

　ただのDPなのだが、遷移式を立てるのに非常に苦労した。特に工夫する方法もなさそうなので、落ち着いて、整理して考えるしかない。