AtCoder Beginner Contest 258

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 258　Eまで五完
C 2 xというクエリが来る度、先頭のindexを-xさせると考える
D それまでで一番短いステージを使う
E ループするところを探す
Gがたくさん解かれていたのでFを飛ばしてGに行き、有名問題っぽいと検索していた。bitsetを使うのは考えたはずなのに……。

— titia (@titia_til) July 2, 2022

F - Main Street

　自力ACだが時間かかってしまった。

　（K=1の場合を除くと）スタート・ゴールそれぞれから、直線で大通りに出る4通りを考えれば良い。その16通りを考えて最短のものを出力する。

　(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのときを気を付けるのが重要。このときはマンハッタン距離が答えにならないのに注意して実装する。

　基本的にはこれだけなのだが、自分が詰まったところを書いておく。

・if (スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのとき

・else if (スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき

　のように実装し、それぞれ迂回して行く最短距離を考えると、「(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bかつ(スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき」のときおかしくなる。

　このときはマンハッタン距離で良いことに長い時間気付けなかった。

G - Triangle

　解説AC。

　bitsetを使っても、bit_count(popcount)を高速化できないと意味がない。bit_countの高速化はこのスライドが詳しい（とtoamさんの解説に書いてあった）。

　予め63個ずつに区切っておき、それぞれについてこのスライドの方法でbit_countを求めるとTLEせず求められる。

Ex - Odd Steps

　解説放送を見てAC。

・Aを無視してDPを立式

・累積和を取ると式が簡単になる。行列累乗が使えそう

・A以外の部分は行列累乗で処理、Aのところだけ普通にDPする

　という流れ。

　上記のステップを経れば難しくないのだけど、Aが重要そうな問題で、Aを無視して処理することが解法に結び付くというのは意外だった。

　何も思いつかなければとりあえずDPを考えてみるのは重要か。