Quiz
https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d
Submit
https://atcoder.jp/contests/mujin-pc-2018/submissions/4629326
解法
- (x, y)をノードとして考えて、高々1000x1000個のノードからなるグラフを考える
- 変換後、(x0, y0) -> (x1, y1)に変化したとする
- 全てのノードは矢印をたどっていくと、停止またはループに入る
- 停止とは(0, 1), (0, 2) ... なのでその点から矢印を逆に辿ればゼロに落ちる数が分かる
視点
- ループに入る数=全体ーループに入らない数
- 余事象
- グラフで考えて逆に辿る
- しかしグラフを構築するときは、与えられた変換を使って矢印を伸ばす
- 数ステップある変換の逆変換を考えるのは大変
- 逆方向と順方向のミックス
参考にした他人のSubmission
https://mujin-pc-2018.contest.atcoder.jp/submissions/2943150
注意点
- (x, y) = (123, 234)のとき x = rev(x) で321が現れるので、ノードは(999, 999)まで用意しておく必要がある
- (N, M)までではない
個人的注意点
- map<Point, vector
> mp; - でノードを管理したが遅かった。ギリギリAC (1.5sec)したが、mapのキーにクラス・構造体を与えると遅い
個人的注意点2
- 最後に、0から辿った数を数えるとき、最初は下記のdfsを使っていた
ll dfs(Point point){ ll sum = 0; auto list = mp[point]; for(auto p : list){ sum += dfs(p); } return sum + 1; }
- 間違っていそうにないdfs
- しかし今回は「注意点」に書いたとおり、N, Mよりも大きい値でもノードを作って矢印を張っている
- なのでdfsするとN, Mを越えた深さまで探索し、大きすぎる値が返ってくる
- よって、Submitのようにusedやvisitedのフラグで管理する必要がある