ABC296 E問題 Transition Game

atcoder.jp

どんな操作？

具体的に考えてみます。

で最初 を選んだとします。
1回目の操作で、 になります。
2回目の操作で、 になります。
3回目の操作で、 になります。
4回目の操作で、 になります。
4回の操作で最初に戻るので、周期4の繰り返しになります。

また、
で最初 を選んだとします。
1回目の操作で、 になります。
2回目の操作で、 になります。
3回目の操作で、 になります。
4回目の操作で、 になります。
いったん4になると、以降はずっと4のままで1,2,3に戻ることはありません。

どちらが勝つか？

繰り返しになる部分は、指定された回だけゴールから逆方向に戻ったところをに選ぶことで、回の操作後にゴールに達することが可能です。つまり、の値にかかわらずを適切に選ぶことで高橋君の勝ちになります。
繰り返しにならない部分は、一度通り過ぎると再度訪れることはありません。そこで、最初に青木君が大きなの値を指定すると、回の操作後にゴールに達するようなは存在せず、青木君の勝ちになります。

ループとそれ以外の検出

操作による値の変化を有向グラフで表します。入ってくる辺の次数が 0 の頂点はループではありません。その頂点から出ていく辺を取り除いたときに入次数が 0 になる頂点もループではありません。これを繰り返すことでループではない頂点をすべてリストアップすることができます。残りの辺で結ばれている頂点はループになっているので、この頂点の数が答えになります。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()
  A = readInts()

  order = zeros(Int,N)

  for i = 1:N
    order[A[i]] += 1      # A[i] の入次数
  end

  stack = []

  for i = 1:N
    if order[i] == 0      # 入次数が 0 の頂点
      push!(stack,i)      # stack 配列に追加
    end
  end

  ans = N

  while length(stack) > 0
    p = pop!(stack)
    ans -= 1              # 入次数が 0 の頂点の分を引く

    q = A[p]
    order[q] -= 1         # p から出ていく辺が向かう頂点の入次数を 1 減らす
    if order[q] < 1
      push!(stack,q)      # 減らした結果、入次数が 0 になったら stack 配列に追加
    end
  end

  println(ans)

end  # function solve

# main
solve()