ABC 401-500/ABC421D - RLE Moving - 競技プログラミング用 知識集積所

---

問題

ABC421D

必要知識

B以下レベルの内容は省略

• ランレングス圧縮※

考え方

ランレングス圧縮※を解凍して愚直にやるのは当然TLE。
そこで、2人の次の連続移動回数のうち小さい方を見て、その回数分の移動をまとめて扱う。

しかし、2人とも動くのはわかりづらいので、青木くんから見た高橋くんの相対位置で考える。
つまり、

• まず、2人とも同じように移動し、青木くんの座標を(0,0)にする
• 青木君の移動は、高橋くんの逆方向への移動として扱う

とする。
すると、各回の移動は

• 位置が変わらない
• どちらかの方向へ2マス進む（4方向）
• 斜め45度の方向へ1マス進む（4方向）

の9パターンになる。

「位置が変わらない」が連続する場合。
元々の相対位置が(0,0)であれば、移動回数分カウント。

「どちらかの方向へ2マス進む」が連続する場合。
移動しない方向の相対位置が0、かつ移動方向が(0,0)向きで、距離が偶数で、ちゃんと届く範囲なら1カウント。

「斜め45度の方向へ1マス進む」が連続する場合。
相対位置の両座標の絶対値が等しく、かつ移動方向が(0,0)向きで、ちゃんと届く範囲なら1カウント。

これをランレングス圧縮※の値を見ながら順に処理していけば答えが出る。

解答例

解答例

注意点

座標や答えがint型に入らない場合がある

同じ地点から延々と同じ方向に進むなどで、座標や答えが2*10^9を超える場合がある。
long long型を使うこと。

別解