D - うほょじご

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のフラグで管理する必要がある