7K12 blog

猫でも分かるアルゴリズム解説

ABC132 E - Hopscotch Addict

f:id:tkr987:20210706023155p:plain

  • 頂点を増やすことでmodの遷移を判定する

f:id:tkr987:20210706030714p:plain
https://atcoder.jp/contests/abc132/submissions/24017041
愚直な考察をすると頂点に移動回数のmod情報を持たせたくなるが、実装が複雑で難しいので逆転の発想をする。具体的には頂点を増やすことで、modの情報を持つ必要なく移動回数のmodを判定できるようにする。今回はmod 3を判定すれば良いので頂点数を3倍に増やす。
 u_i \Rightarrow v_{i + N}, \ u_{i+N} \Rightarrow v_{i + 2N}, \ u_{i+2N} \Rightarrow v_i のようにグラフを構築すれば通常のBFS処理でmodを判定可能。