ABC 104 反省

A問題
A - Rated for Me
条件分岐をします.
提出
Submission #2950380 - AtCoder Beginner Contest 104
B問題
B - AcCepted
素直に条件を満たしているかどうか確認します. こういうのをやるときはboolを返す関数をつくると実装が楽なんだなあと解説生放送を見ながら思いました.
提出
Submission #2951814 - AtCoder Beginner Contest 104
C問題
C - All Green
問題をしばらく見つめて貪欲解が全く思い浮かばず, どん詰りの状態でしたがDの制約がとても小さいことから部分集合全列挙を思いつきました. コンプリートする問題の組み合わせを全部調べて解く問題の最小値を更新すればよく,コンプリートする問題がきまっていれば, コンプリートしていない問題の中から貪欲に点数の高いものをとっていけばいいことがわかります. この貪欲にとるとき, コンプリートしてはいけないことに注意が必要です. なにもコンプリートしないことも全列挙のうちに入っているので, あまり深く考える必要はありません.
提出
Submission #2955944 - AtCoder Beginner Contest 104

D問題
D - We Love ABC
コンテスト中いろいろ考えていたものの解けず, 解説を見ても???状態. DPは難しいですね....
こちらのけんちょんさんのブログを見てコードをまね, DPの気持ちを推量.
ABC 104 D - We Love ABC (400 点) - けんちょんの競プロ精進記録
自分の解釈で説明すると, dpの状態は4つあります. また, ?マークが出て文字列が3倍に増えることを分裂を呼称することにします.
dp[i+1][0]･･･Sのi文字目までで分裂した文字列の個数
dp[i+1][1]･･･Sとその分裂のi文字目までで出現するAの数
dp[i+1][2]･･･Sとその分裂のi文字目までで出現するABの数(A,Bは連続する必要がなく, この順番に並んでいればよい.)
dp[i+1][3]･･･Sとその分裂のi文字目までで出現するABCの数(A,B,Cは連続する必要がなく, この順番に並んでいればよい. )
初期値: dp[0][0] = 1 (初期は分裂しておらず１つの文字列)
遷移を考えると,

1.セットアップ(前状態からの繰越)
s[i] == '?'のとき
{dp[i+1][0] = 3*dp[i][0] (文字列の数が3倍になります.)
dp[i+1][1] = dp[i][1]*3
dp[i+1][2] = dp[i][2]*3
dp[i+1][3] = dp[i][2]*3
今まで見てきたA,AB,ABCについて, 文字列の数が3倍となったため, これらすべての量も3倍になります.
}
s[i] != '?'のとき
dp[i+1][0] = dp[i][0] (文字列は分裂しないので文字列の数はそのままです)

2.遷移
s[i] == 'A' のとき
dp[i+1][1] += dp[i][0] (分裂した文字列の数だけAが出現するので, すべて足す.)
s[i] == 'B'のとき
dp[i+1][2] += dp[i][1] (今までに登場したすべてのAに対してこのBを対応させることができます)
s[i] == 'C'のとき
dp[i+1][3] += dp[i][2] (今までに登場したすべてのABにこのCを対応させることができます. )
s[i] == '?'のとき
dp[i+1][1] += dp[i][0]
dp[i+1][2] += dp[i][1]
dp[i+1][3] += dp[i][2]
?はAにもBにもCにもなりうるため, すべての遷移パターンを実行します.

Submission #2960341 - AtCoder Beginner Contest 104

今回のABCはなかなか難しかったと思います...
Rate: 839 → 979 (緑)