c問題はよくある貪欲かと思いきや全探索の問題である。D問題はDPを使うことはわかったものの更新が分からずできなかった。
https://atcoder.jp/contests/abc104
C問題
方針
まず貪欲でできないか考えるが思ったより複雑なため全探索を考える。問題条件より、問題の種類は10種類しかないことと、ある種類の問題を途中で終わらせて、他の種類の問題に取り掛かるメリットは明らかにないので、ある種類の問題を中途半端に終わらせることは、途中では起こらないことがわかる。よって、1~N(N<=10)の問題について、それぞれ全部解いたら、違う問題を全部とくという風に全探索することで、最小回数を求められる。
D問題
DPの問題であるが、ここで文字列Sのi番目にいる時の状態を考えると3種類存在する。
(1) Aを加える
(2) (1)の状態から
(3) (2)の状態からCを加える
最終的に文字列の長さの時の(3)の数を見れば良い。
次に実際の遷移について考える。まず?が一個もない文字列について考えると、
i番目の文字が'A'の時
dp[i+1][0] = dp[i][0] + 1;
i番目の文字が'B'の時
dp[i+1][1] = dp[i][1] + dp[i][0];
i番目の文字が'C'の時
dp[i+1][2] = dp[i][2] + dp[i][1];
次に?が文字列中に現れる場合について考える。?が出てくると、?は3通りに買われることから、文字列の種類は3倍に増える。(AAB? => AABA,AABB,AABC)なのでこれらの増えた文字列についても全て考慮しなければならない。
以上より、文字列が増えた時の遷移の様子について考える。
i番目の文字が'A'の時
dp[i+1][0] = dp[i][0] + 文字列の数;
i番目の文字が'B'の時
dp[i+1][1] = dp[i][1] + dp[i][0];
i番目の文字が'C'の時
dp[i+1][2] = dp[i][2] + dp[i][1];
i番目の文字が'?'の時
上3つ全てについて足し合わせる。
この考えを用い、dpと文字列の総数を更新していくことで答えを導ける。