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

D. Lucky PIN

atcoder.jp

解法

取りうる暗証番号(000〜999)が可能かどうか1個ずつ全部調べる。

暗証番号の、
1桁目(百の位)の数字は、それがSで現れる最初の桁目でとる。これをa桁目とする。
3桁目(一の位)の数字は、それがSで現れる最後の桁目でとる。これをb桁目とする。
2桁目(十の位)の数字が、Sのa以上b未満の桁の範囲に現れれば、これをc桁目とする。
a,b,c桁目以外の数字をSから取り除くことでその暗証番号を得られる。

事前にSに現れる数字とその位置を{数字:[位置、位置、...], 数字:[位置、位置、...], ...}の形で持っておくことで計算時間を短縮する。

例)
3141592653589793238
=> {'3': [1, 10, 16, 18], '1': [2, 4], '4': [3], '5': [5, 9, 11], '9': [6, 13, 15], '2': [7, 17], '6': [8], '8': [12, 19], '7': [14]}

'892'はとれるか？
'8'=>[12, 19]=>12桁目でとる
'2'=>[7, 17]=>17桁目でとる
'9'=>[6, 13, 15]=>12より大きく17より小さい13(or15)桁目でとる
∴ とれる

実装

辞書を作る

n=int(input())
ls=list(input())
nums={}
for idx,num in enumerate(ls):
    nums.setdefault(num,[]).append(idx+1)
count=0

ゼロ埋めをもちいて000〜999に対して調べる。

for i in range(1000):
    i_zero=str(i).zfill(3)
    encrypt=list(i_zero)

1桁目(first)と3桁目(third)のとる位置を取得。2桁目の数字(second)がそれらの間からとれるかチェックして取れたらcount+=1

    first_ls=nums.get(encrypt[0],[])
    if not first_ls:
        continue
    first=first_ls[0]
    third_ls=nums.get(encrypt[2],[])
    if not third_ls:
        continue
    third=third_ls[-1]
    second_ls=nums.get(encrypt[1],[])
    for j in second_ls:
        if j>first and j<third:
            count+=1
            break

print(count)

range(1000)のなかでsecond_lsをfor文で回してるためTLE臭がすごいけど、second_lsの長さもたかだか30000なのでギリギリ大丈夫だった。
forではなく二分探索で探せばもっとはやくできる。

コンテスト結果

レート変化

遅かったとはいえDまで解けたのに...

年内4桁いきてぇなぁ