Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 262 C問題 Min Max Pair

AtCoder ABC ABC262 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

1 以上 N 以下の整数からなる長さ N の整数列 a=\left(a_i \right)_{i=1}^N が与えられる.

以下を満たす整数の組 (i,j) の個数を求めよ.

  • 1 \leq i \lt j \leq N
  • \min (a_i, a_j)=i
  • \max(a_i,a_j)=j

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq N

解法

i=1,2, \dots, N に対して, p_i を以下を満たす整数 j の個数とする.

  • i \lt j \leq N
  • \min (a_i, a_j)=i
  • \max(a_i,a_j)=j

このとき, 最終解答は \displaystyle \sum_{i=1}^N p_i である.

\min(a_i, a_j) の値で場合分けする.

  • \min (a_i, a_j)=a_i の場合: a_i=i である. そして, i \lt j, \max(a_i, a_j)=j という条件と合わせることにより, a_j=j であることも導ける. 逆に, a_j=j であるような整数 j は全て条件を満たす. 従って, p_i は i \lt j \lt N を満たす整数 j のうち, a_j=j を満たす整数の個数である.
  • \min (a_i, a_j) \neq a_i の場合: このとき, a_i \gt a_j である. 従って, j=\max(a_i, a_j)=a_i, i=\min (a_i, a_j)=a_j である. これから, 可能な j は高々 1 つであることがわかる. そして, これは a_i \gt i かつ, a_{a_i}=i と同値になる. よって, p_i は a_{a_i}=i ならば, 1 , そうでなければ 0 である.

ここで, a_i=i となる整数 i を x_1,\dots, x_n~(x_1 \lt x_2 \lt \dots \lt x_n) , a_i \neq i となる整数 i を y_1, \dots, y_{N-n} とすると, 答えは

\begin{align} \sum_{i=1}^N p_i &=\sum_{k=1}^n p_{x_k}+\sum_{k=1}^{N-n} p_{y_k} \\ &=\sum_{k=1}^n (n-k)+\sum_{k=1}^{N-n} p_{y_k} \\ &=\dfrac{n(n-1)}{2}+\sum_{k=1}^{N-n} p_{y_k} \\ \end{align}

である. よって, 各 i に対して, a_i=i であるかをみて, そうでなければ a_i \gt i かつ a_{a_i}=i を満たすかどうかを見れば良い. 計算量は O(N) 時間である.