大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277) Eまで。
A P.index(X)+1
C DFS
D 差が1以内で連続する数字の和。A+Aを考えると実装しやすい。
E 01BFSで良いのにダイクストラした。

— titia (@titia_til) November 12, 2022

F - Sorting a Matrix

　解説AC。

　行については、最小値・最大値を見てソートするのはOK。

　その後、列について考えるとき、ある行の二つの列で大小関係があるときに辺を張り、ループしたらダメ、としたい。が、辺の本数が多くなりそうで困っていた。

　こういうとき使うのが、超頂点を加える手法ですね。

　ただ、最近、この問題で使った方法とは超頂点の使い方が違うのが難しい。「同じ数字たちをまとめるために超頂点を使う」という手法はなじみがなかった。

　（とはいえ、超頂点を使うこと自体を考えなかったのはダメ）

　なお、答が一致した後もTLEを取るために苦戦した。

G - Random Walk to Millionaire

　解説放送を見てAC。

　Xの二乗とは何か？　と考えたとき、「どこでレベルアップしたか？」の組み合わせと考えてDPへ持ち込む。

　考え方は分かるのだけど、この問題でこの手法を使うとは。

　ただ、この問題ではDPくらいしかやりようがないし、DPを高速化しようと思ったらXの二乗というところを上手く使うしかない。そう思えば、この変形をするしかない、と考えるのは自然だとは思う。

　しかし、元々積で与えられているものを分けて考えるというのはピンと来なくて。難しい。