[AtCoder] AGC 032 A – Limited Insertion

問題

方針

得られる数列の候補

\( N \) 回の操作で得られる数列の候補を考えます。\( i \) 回目の操作で \( j = i \) としたときに得られる数列は、\( 1, 2, \cdots, N \) となります。よって、\( i < b_i \) となる数列は作ることができません。

逆順から考える

与えられた数列を \( B_N = (b_1, b_2, \cdots , b_N)\) とします。

\( i \) 回目までに出来上がった数列 \( A_i \) を \(A = (a_1, a_2, \cdots, a_i) \) とします。ここで、\( i = N \) のとき、\( A_{N – 1} = (a_1, a_2, \cdots, a_{N – 1}) \) が与えられたとき、\( A_N \) を \( B_N \) に一致させるには、\( b_j = j \ (1 \leq j \leq i)\) となるように挿入する必要があります。

\( b_j = j \) となる値が複数ある場合、最大の \( j \) を選びます。これは、\( B_3 = (1, 2, 3) \) の配列が与えられたとき、\( A_2 = (a_1, a_2) \) とします。このとき、\( j = 1 \) としまうと、\( A_N = (1, a_1, a_2) \) となり、\( a_i \leq i \) の制約から \( B_N \) を作ることができません。したがって、\( i = N \) のとき、\( b_j = j \) を満たす最大の \( j \) を消去した配列を \( B_{N – 1} \) として逆順に考えていきます。

コード

提出したコード