米田氏が企画した「競プロ典型90問」を解いていきます。
ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。
競プロ初心者なのでどうか温かい目で見守ってください。
なお、本記事中のPythonコードはブラウザ上で実行可能です。
よろしければ遊んでいってください。
問題
kyopro_educational_90/008.jpg at main · E869120/kyopro_educational_90
try
これは動的計画法(DP)でいけるんではないか？
def main(N, S):
MOD = 10**9 + 7
ATCODER = "atcoder"
dp = [[0]*len(ATCODER) + [1]]
for i in range(N-1, -1, -1):
idx = ATCODER.find(S[i])
if idx != -1:
now = dp[-1].copy()
now[idx] += now[idx + 1]
dp.append(now)
return dp[-1][0] % MOD
return dp
テストデータ・テスト関数定義 ↓
# 縮小表示
test_data = [
{
"in":[10, 'attcordeer'],
"out": 4
},{
"in":[41, 'btwogablwetwoiehocghiewobadegwhoihegnldir'],
"out": 2
},{
"in":[140, 'aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr'],
"out": 279999993
}
]
def test_all(f):
for i, data in enumerate(test_data):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
test_all(main)
結果
AC!やったー
提出 #32669434 - 競プロ典型 90 問
解説・想定コード
kyopro_educational_90/008.jpg at main · E869120/kyopro_educational_90
想定コード：
kyopro_educational_90/008.cpp at main · E869120/kyopro_educational_90
大体似たような実装ですが、想定コードでは$S$の頭から探索してますね。
DPといえば後ろ(部分)から前(全体)みたいなイメージがあったので上では$S$の末尾から探索してました。
try(2nd.)
という訳で想定コードを参考にした実装が以下です。
def main2(N, S):
MOD = 10**9 + 7
ATCODER = "atcoder"
dp = [[1] + [0]*len(ATCODER)]
for i in range(N):
idx = ATCODER.find(S[i])
if idx != -1:
now = dp[-1].copy()
now[idx + 1] += now[idx]
dp.append(now)
return dp[-1][-1] % MOD
test_all(main2)
無事AC
提出 #32670648 - 競プロ典型 90 問
前からでも後ろからでもやってることは同じですな。
なんで"後ろから"ってイメージだったんだろ🤔
まとめ
初めて自力でDPの発想～実装までできました！！
嬉しい😁
自由欄
