クソ記事でもいいから取り合えずたくさん書いて後から修正しようキャンペーンの第2弾なので質は。。です。
以前書いて、下書きに残っていたものをそのまま投稿しています。(なので古いです)
結果
a,b,cの3問正解に終わった。
d,eを考えたが、eは方針が微妙にたったが、詰めれず。
dは全く方針が思いつかなかった。(DPと言われたら確かにDPで解けそうだったので、これは発想力よりは自分の演習不足)
また、b,cの方針はすぐにたったものの実装で苦労していたので、(bは(Yes,No)の大文字、小文字に気つかなかったというだけなのでしょうもない間違えだったが早く気づけるようになりたい)そこも改善点。
解説をみながら復習
D: Digits Parade
問題:?と数字のみから構成される文字列を受け取り、?を任意の数字0〜9に置換するときに、13で割った余りが5になる組み合わせの数をこたえる。
ナイーブに考えると、$10^{(?の数)}$ のパターンがあるので、1つ1つ検証すると間に合わない。
そこから、まったくアイデアが浮かばなかった。
解説:
dp[i][j] := 先頭 i 文字として考えられるもののうち,13 で割ったあまりが j であるものの数
このとき i の昇順に dp テーブルを見ると,i − 1 文字目までを 13 で割ったあまり (dp[i − 1][j] の j) と
s[i] としてあり得る数字を全て試すことで dp[i][0] ∼ dp[i][12] の値がわかります
ということです。要するに先頭から13*|s|のサイズのdpの表を埋めていきます。
確かに、余りは各桁ごとにを13で割った余りの和であり、複雑な計算でない(前後の値などによって変化しない)ので、先頭からi文字目までの和をdp[i][j]とおけば、
dp[i+1][k] = \sum_{j}^{0-12}{(dp[i][j]*10+s[i+1])mod13)}
で表現できる。
ここで、頭がいいな、と思ったのは、僕は、dpと聞いて、s[i+1]$10^{(|s|-i)}$mod13
を足す処理を毎回しようとしたのですが、解説では先頭からi文字目までを数字にした時のあまりをi+1の時に10倍することで、計算を簡単にしています。(わかりにくくてすみません。。)