AtCoder Beginner Contest 122
Updated:
Source codes
Solutions
A - Double Helix
string でまとめるか、 map<char, char> を使う。
B - ATCoder
累積和を使えば十分である。実際は累積和を使う必要もない。 int now = 0; を更新していけばいい。
C - GeT AC
$1$-indexed とする。
$sum[i] = S[0, i)$ に入っている “AC” の数
と定める。初期状態： $sum[0] = 0$, 遷移： $i = 1, \dots, N$ に対し、
\[
sum[i] =
\begin{cases}
sum[i - 1] + 1 & S[i - 1, i] = ``AC”, \\
sum[i - 1] & \text{otherwise}.
\end{cases}
\]
答えは、普通に考えると $sum[l _ j] - sum[r _ j - 1]$ であるが、ここでは “AC” がきた瞬間に “C” のところで増えているのでこれでは答えにならない。正しい答えは $sum[l _ j] - sum[r _ j]$ である。
ポイント
累積和でクエリに答える際に 1 個ずらすのがポイントである。
D - We Like AGC
模範解答
以下では A: 0, G: 1, C: 2, T: 3 とする。
含んではいけない文字列は “?012”, “?102”, “?021”, “0?12”, “01?2” の 5 パターンである。つまり末尾 3 文字を管理しておけば全て同じ状態と見做すことができる。そこから 4 つ $a = 0, 1, 2, 3$ で枝を伸ばせばよろしい。
そこで DP をする。
$dp[n][i][j][k] = n$ 文字からなる AGC 文字列のうち末尾が $kji$ であるものの個数
と定める。初期状態は $dp[0][3][3][3] = 1$, otherwise $0$. 遷移は $n = 0, \dots, N - 1$ に対し、 $0 \leq i, j, k, a \leq 3$ に対し、 $jia = 012, 102, 021$, $kjia = 0x12, 01x2$ を continue;, そうでないならば、
\[
dp[n + 1][a][i][j] \mathbin{ {+} {=} } dp[n][i][j][k].
\]
答えは以下で与えられる。
\[
\sum _ {i = 0} ^ 3 \sum _ {j = 0} ^ 3 \sum _ {k = 0} ^ 3 dp[N][i][j][k].
\]
もっと頭を使わない解法
上の解答では頭を使って含んではいけない文字列を列挙した。しかしこれらを理性で全て列挙することに自信が持てないとする。すると不可能な $4$ 文字からなる文字列を dfs で全て作ってしまうことが良いとわかる。 $forbid$ に突っ込んでおく。
$memo[i][S] = i$ 文字からなる AGC 文字列のうち末尾 $3$ 文字が $S$ であるようなものの個数
とする。 map<string, ll> memo[110]; と定義する。 vector<string> C = {"A", "G", "C", "T"}; とでもしておくと結局上とほぼ同じように書ける。
ポイント
この問題は混乱していてうまく解けなかった。「もっと頭を使わない解法」で解くべきだった。