[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} \) として逆順に考えていきます。
ディスカッション
コメント一覧
まだ、コメントがありません