トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) Eまで。F思いつけなかったのダメ。
A A|B
C どこから来たかを持ってdfs
D 貪欲にとったらWAが出たので、ゲームDPを再帰で書いた。
E 何周するか二分探索。その後シミュレーション。

— titia (@titia_til) September 24, 2022

F - Transportation

　解説AC。

　最小全域木を作る問題なので、クラスカル法かをプリム法を使うしかない。（一応、他にブルーフカ法というのもあるが、あまり使わない）

　空港・港とあるが、それぞれを使う・使わないで四種類ありそう。

　コンテスト中、ここまで考えて、止まってしまった。

　あとは、「超頂点を作って空港や港を処理する」というのを思いつかなくてはいけない。見たことないなら仕方ないが、何問も類題を解いているのに思いつかないのはまずい。

　ただ、超頂点を作る、という手法を思いつかずに問題を落としていることは結構多い気がする。自分の苦手な方法なのかもしれないので、気を付けよう。

　なお、PyPyだと制限時間がきつい。毎回グラフを構築していると間に合わないため苦労した。

G - Sequence in mod P

　解説放送を見てAC。

　B=0ならBaby-Step Giant-Step法が使えるので、それを応用できないか、と考えると大体そのまま解ける。Baby-Step Giant-Step法をよく覚えていなかったのは問題だけど、まあ平方分割ですね。

　ACするためには、A=1やA=0の場合をケアしないといけない。