AtCoder Beginner Contest 122

Updated:

AtCoder Beginner Contest 122

ソースコード

解法のメモ

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"}; とでもしておくと結局上とほぼ同じように書ける。

ポイント

この問題は混乱していてうまく解けなかった。「もっと頭を使わない解法」で解くべきだった。

その他