はじめに
ABC456に参加したため、振り返っていきます。結果は4完（A-D問）でした。
A - Dice
3つのサイコロの合計値が$X$になりうるかを判別する問題でした。
解法は全探索で、2重ループでi j（1 ~ 6）を探索し、3個目の目k = X - i - jが1 ~ 6に収まるかを確認します。
#include <stdio.h>
int main(void) {
int X; scanf("%d", &X);
for (int i = 1; i <= 6; i++) {
for (int j = 1; j <= 6; j++) {
int k = X - i - j;
if (k >= 1 && k <= 6) {
printf("Yes\n");
return 0;
}
}
}
printf("No\n");
return 0;
}
B - 456
3つのサイコロの目の数を配列として与えられた時、4 5 6が1つずつ出る確率を求める問題でした。
解法は全探索です。3重ループでi j k (1 ~ 6)を探索し、A[1][i] A[2][j] A[3][k]が{4, 5, 6}かを判定いします。判定条件はa+b+c == 15かつa!= b && b != c && c != aです。確率はサイコロの総パターン216通りで割れば求まります。
#include <stdio.h>
int main(void) {
int A[4][7];
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 6; j++) {
scanf("%d", &A[i][j]);
}
}
double count = 0;
for (int i = 1; i <= 6; i++) {
for (int j = 1; j <= 6; j++) {
for (int k = 1; k <= 6; k++) {
int a = A[1][i];
int b = A[2][j];
int c = A[3][k];
if (a != b && b != c && c != a
&& a + b + c == 15) {
count++;
}
}
}
}
double ans = count / 216;
printf("%f\n", ans);
return 0;
}
私は配列をA[4][7]と宣言しましたが、色々ややこしくなるので素直にA[3][6]でループを0から始めることをオススメします（テストケースで気づいたけど直すのめんどくさかった）。
型に注意
countをint型にしてしまうと確率計算が整数除算になります。分母を216.0として計算するか、countをdouble型として宣言しましょう。
C - Not Adjacent
隣り合わない部分文字列の個数を与えられた定数で割ってあまりを出力する問題でした（なぜ除算にこだわる...?）。
部分文字列とは
連続した文字の切り出しです。abbcからab bb bcなどは取れますが、acは取れません（部分列だと取れます）。
解法は動的計画法（DP）です。終点jを固定し、f(j) = jでおわる有効な部分文字列の個数を求めます。漸化式は以下の通りです。
$f(0) = 1$
$f(j) = f(j-1) + 1$（$S[j] != S[j-1]$のとき）
$f(j) = 1$ （$S[j] == S[j-1]$ のとき）
出力は$f(0) + ... f(N-1)$を$MOD$（定数）で割った余りです。
#include <stdio.h>
#define MOD 998244353
int main(void) {
char S[300001];
scanf("%s", S);
int n = 0;
while (S[n] != '\0') n++;
long long ans = 0;
long long f = 1; // f(j): jでおわる有効な部分文字列の個数
ans = 1; // j=0の分
for (int j = 1; j < n; j++) {
if (S[j] != S[j-1]) {
f = f + 1;
} else {
f = 1;
}
ans = (ans + f) % MOD;
}
printf("%lld\n", ans);
return 0;
}
注意点が2つあります。
まず、S[j] != S[j-1]とは前の終点で有効だった部分文字列はすべてS[j]を追加しても有効ということです。さらにS[j]単体（例：bなど）も加わります。
また、長さ2以上の部分文字列は必ず末尾にS[j-1] S[j]の重複が発生します（S[j] == S[j-1]）。有効なのはS[j]単体のみです。
D - Not Adjacent 2
C問題の「部分文字列」が「文字列」に置き換わった問題です。
部分列とは
文字列を飛ばしてもよく、順序だけ保った切り出しです。abbcからac（1文字目・4文字目）やabc（1, 2, 4文字目）も取れます。
部分文字列との扱い方の違いが以下の通りです。
| 部分文字列 | 部分列 | |
|---|---|---|
| 飛ばせるか | ×（連続のみ） | ○（飛ばせる） |
| 隣接の定義 | S上で隣接 | 部分列内で隣接 |
| DPの状態 | 終点の位置 | 終点の文字種 |
部分列では「$S$上で隣り合う文字」ではなく、「選んだ文字の中で隣り合う文字」が重複してはいけないです。そのため、位置ではなく文字種でDPを管理します。
dp[X]をこれまでに見つかった、文字xで終わる有効な部分列の総数、と置きます。文字xを処理するとき、以下の通りになります。
total = dp[a] + dp[b] + dp[c]
dp = (1 + total - dp[x]) // を加算
(1 + total) % MOD; // 直接代入と等価
-
1:x単体の文字列 -
total - dp[x]:x以外で終わる全部分列にxを追加したもの
#include <stdio.h>
#define MOD 998244353
int main(void) {
char S[300001];
scanf("%s", S);
int n = 0;
while (S[n] != '\0') n++;
// dp[0] = a, dp[1] = b, dp[2] = c
long long dp[3] = {0, 0, 0};
for (int i = 0; i < n; i++) {
int x = S[i] - 'a';
long long total = (dp[0] + dp[1] + dp[2]) % MOD;
dp[x] = (1 + total) % MOD;
}
long long ans = (dp[0] + dp[1] + dp[2]) % MOD;
printf("%lld\n", ans);
return 0;
}
おわりに
今回のコンテストの解法をまとめると、以下の通りです。
A問：やるだけ（全探索）
B問：やるだけ（全探索）
C問：DP, 部分文字列
D問：DP, 部分列
C, D問題ではDPの理解が試されていましたね。加えて部分文字列・部分列への知識も必要だったので精進していきたいです。