[AtCoder] 三井住友信託銀行プログラミングコンテスト2019 D – Lucky PIN

問題

方針

長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 \) 通りなので、ある文字列が作成可能かどうかを調べます。ここで、各数字が何番目に出現したかというリストを作成し、全探索を行います。\( a(i, j) \) を数字 \( i \) が \( j \) 番目に出現した値とします。次の条件を満たす文字列 \(ijk\) は作成可能なので、\( i, j, k, l \) を全探索します。

\[a(i, 1) < a(j, l) < a(k, |a(k)|)\]

\( a(k, |a(k)|) \) は 数字 \( k\) が最後に出現した箇所です。

コード