7K12 blog

猫でも分かるアルゴリズム解説

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

f:id:tkr987:20200619092004p:plain

https://atcoder.jp/contests/sumitrust2019/submissions/14461892

  • 制約を見て計算量の少ない要素の全探索がないか探す意識を持つ

f:id:tkr987:20200619092548p:plain

文章の通りにSから暗証番号を作ると大変なので、暗証番号が1000通りしかないことに着目する。暗証番号の範囲が[000,999]しかないので、各暗証番号を満たすか全探索すれば O(10^3N)で処理が終わる。

暗証番号1桁目の数字がS[i1]に存在したとして auto i2 = S.substr(i1+1).find(pin[1]); で暗証番号2桁目の数字を見つける処理を書くと、substr(i)で切り取る部分が文字列範囲を超えたりしてバグったりする(たぶん)ので S.find(pin[1], i1+1) だけで実装するのが楽に感じた。