競プロ初中級者100問

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

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

この問題は全探索を用いて解くことができます。

方針

存在しうる暗証番号をK通りとして、全探索の計算量はO(NK)です。この問題では、暗証番号は3桁すなわちK=1000ですので、全探索でも十分間に合います。

コード

全探索

Pythonの場合だと実装によってはTLEとなるため、PyPyを用います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)

別解　計算量O(N)の解法

ハッシュテーブル(setなど)を使い、prefixを保存していくことで効率よく数え上げができます。

1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
S = input()

st = [set() for _ in range(3)]

for s in S:
    for pre in st[1]:
        st[2].add(pre+s) # 3桁目
    for pre in st[0]:
        st[1].add(pre+s) # 2桁目
    st[0].add(s) # 1桁目
        
print (len(st[2]))

記事情報

  • 投稿日：2020年5月16日
  • 最終更新日：2020年5月16日