ABC104 D - We Love ABC
解説を見ながら少しでもかみ砕こうとした記録
D - We Love ABC
全ての文字列のABC数の合計を求める問題
DPを使って解く
何らかの組み合わせの最大値や総数をで割った余りを求めるなどはDPを使う問題と連想できそう
今回の問題でのDPの考え方は「S の先頭から i − 1 文字目までに対する処理（? の置換と丸つけ）をすでに 行っていて、これまでに丸を j 個つけている場合の、S の残りの部分に対する処理を行う方法の個数」で、
- j < 3で「次に丸を付けるべき文字or?」なら数え終わっている文字の次の文字に組み合わせの数を引き継ぐ
- j = 3で「?」ならABCのどれでもいいので一つ前の組み合わせに3をかけるそうでなければ前の組み合わせを引き継ぐ
をDPすればよさそう
コード中の計算で
dp[i][j] = dp[i+1][j] * (s.charAt(i) == '?' ? 3L : 1L);
が3つ選び終わっていて今の対象の文字が「？」であればそれまでの組み合わせのすべてに「A, B, C」のいずれかをくっつけれるので3倍するところ。
if(j < 3 && (s.charAt(i) == '?' || s.charAt(i) == "ABC".charAt(j))) { dp[i][j] += dp[i+1][j+1]; }
ここが例えば2個つけていたら対象の文字が「A」または「？」のようにABC数を作れるかどうかで加算しているところ。
提出コード(写経しただけ)
