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

atcoder.jp

diff 836

回答時の方針

Submission #12909261 - Sumitomo Mitsui Trust Bank Programming Contest 2019

N個の数字の中から3個選んで3桁の数字を作ろうかと思ったがとなり筋が悪そうだと思い別の方法を検討した.暫くして3桁としたときにN個の数字の中からを決定する場合に同じ数字を選ぶことを考えると左のものから優先で選ぶことが最適だと気づいた.入力例2123123からの値として1を選ぶ場合index=3は考える必要がなくindex=0が最適となる.

s:  123123 // 文字列s
c:  333210 // 2桁目としてとり得る値の種類

この場合xとして1を選ぶと,

x=1 -> y=[1 i=3,2 i=2, 3 i=3] -> 2+3+3 = 8

同様にx=2,3について

x=2 -> y=[1,2,3] -> 2+1+3 = 6
z=3 -> y=[1,2,3] -> 2+1+0 = 3

t=8+6+3=17

ということで文字列を左から精査して各桁について先にマッチしたindexで決めてしまうのが最適だとわかる. 計算量は1桁目の選び方[1-9]2桁目の選び方[1-9]文字長Nでかな？ 各文字ごとにi番目以降の数字のバリュエーションを保持しているぶん,解法の貪欲法より若干早い気がする.

正答

いくつか解法が提示されていたが計算量を見積もるのが重要だなと改めて思った.全探索で間に合うならそれで解けばよい.

貪欲法

表現が難しいんだがとり得る値ベースで全探索する方法が便利そうだなと思った, ABC 057 C - Digits in Multiplication でも同様の方法で解答されていたので競技プログラミングではよくやる書き方なのかなと思った.業務プログラミングだと全然やらない書き方だから意識して慣れないとあまり思いつかない.今回でいうととり得る値が[0,1000]なので for(ll i =0; i < 1000; i++) で回すみたいや感じのやつ,圧倒的に解答がシンプルになって良いので書けるようにしたい.

動的計画法

入力例1

4
0224

dp[i][j][k]としてiを現在の文字列の位置,jを選択した文字長,kを構築した値として初期値dp[0][0][0]=trueとする. 例えばi=2,j=1,k=2のとき次の番号を選択するときdp[2][2][2*10+2]=true,選択しない時dp[2][1][2]=trueと分岐する. 桁数[0,3],暗証番号候補[0,999]について網羅的にこれを繰り返し暗証番号が作れるかどうかを記録する.

最終的に求めたいのは暗証番号3桁で文字列を最後尾まで探索したときの要素なのでdp[N][3][k]について判定を行う.

所感

DP汎用性高いから積極的に使っていきたいが今回のような解法は思いつかない...

緑問題を難なく解けるようになるには計算量の見積もりを正確にして解法はそこから逆算する感じが良い気がする,あとは全探索でもシンプルに書けるならそっちのほうが良くてコードがシンプルであればエッジケースにも気づきやすいと思った.思考の順番としてまずは全探索を考えてそれが無理になら計算量を減らす方法を考えるのようにする.