Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、13問目を解説していきたいと思います。
問題名 【D – Lucky PIN】
入力
N：数列の長さ
S[i] : 数列Sのi番目の数字
考察
ぱっと見、N個の数列から3つを選び出しを全探索すればできそうですが、実はそれだとTLEになってしまいます。
なぜなら今回 N = 30000 であるので、30000個の中から3つを選ぶ操作の全探索は、30000*29999*29998/3*2 > 10**8 となり、TLEしてしまいます。
ではどうすればよいでしょうか？
それでも全探索します。なにについて全探索するかというと、、、
今回は、答えとなりうる数字について全探索します。
今回答えとなる数列は 000 ~ 999 の1000通りです。
この1000通りについて、Sが前から見ていったときにその数列を作れるかで探索します。
今回 答えとなり得る数列は1000通りで、Sは最大で30000なので、計算量は、O(3*10^7)で、ギリギリ間に合います。
コード
from collections import deque
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
N = II()
ns = S()
box = []
for i in range(0,10):
i = str(i)
for j in range(0,10):
j = str(j)
for k in range(0,10):
k = str(k)
pw = i+j+k
box.append(pw)
ans = 0
for pw in box:
cnt = 0
for j in ns:
if pw[cnt] == j:
cnt += 1
if cnt == 3:
ans += 1
break
print(ans)まとめ
こーゆー問題は、言われれば解けるけどなかなか自分で気づけないものよね
前の問題 012【B – Counting of Trees】
次の問題 014【C – Digits in Multiplication】
コメント