デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） Fが解けず終了。
B PythonならX//10
C (x1,y1)の近くの点を探索
D 素数列挙
E 木DP
F 「連結成分から出る辺が残り1個」なものから「2個以上のもの」へ繋ぐことを繰り返せば良い。とは分かったんだけど実装に失敗。

— titia (@titia_til) February 19, 2022

F - Construct Highway

　一応自力AC。落ち着いて考えたら実装できた。

　ツイートした通り、「連結成分から出る辺が残り1個」なものから「2個以上のもの」へ繋ぐことを繰り返せば良い。これをどう実装するかだが、最初に、連結成分ごとにまとめたものを一点と思って実装する。そうすると、実装上ネックになる「最初からある辺」を無視することができる。各連結成分ごとに、どの頂点から何本ずつ辺が出ているかを覚えておけば、そこから復元できる。

　コンテスト中もこの方法は考えたのだけど、一旦まとめてからもう一度復元するのは面倒な気がし、一気にやる方法を考えてしまった。（一気にやる方法もあるかもしれないけど、上手くいかないときは）横着しちゃダメね。

G - Builder Takahashi

　フロー（最小カット）なのは問題を読めば分かり、グラフの構築もそう難しくはない。

　あとは復元。解説動画を見てしまったが、グラフがスタート側とゴール側に分かれるということに思いがいけば難しくなかった。

　が、その後ACするまで苦労したのは、最初に与えられるグラフが有向グラフだと勘違いしたため。何度かWAを出した後問題文を読み直してようやく気付いた。復元部分で間違っているんだろうという先入観があったせいだけど、こういうミスはひどい。

Ex - Dice Product 2

　DPを立式し、どこをまとめて高速化すれば良いかは自力で分かった。

　が、実装が上手くいかず、解説放送を見てAC。

　やることは分かっても、この実装はなかなか難しいですね。