DPわからねえ…解説を見ても数式わからねえ…やっぱメモ化探索安定…！
という筆者が、モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）の問題「RLE」を解いた考え方を記す。
問題概要
指定の長さの英小文字列 (長さ3,000以下) のうち、連続した同じ文字を「その文字と何個連続したかの十進表現」で置き換えることによってもとの文字列より短くなるものの個数を指定の数で割った余りを求める。
メモ化探索
これまでにどのような文字列を作ってきたかに関係なく、文字数が同じならその後の展開が同じになりそうなので、
「現在、操作前の文字列を何文字まで決めたか」「現在、ここまでの操作前の文字列に対する操作後の文字列が何文字になったか」を状態とし、
「現在の操作前の文字列に、同じ文字を何個か加える」を一手とするメモ化探索をする。
#include <stdio.h>
#define MAX 3156
int N, P;
/* a + b mod P を返す */
int add(int a, int b) {
int ret = a + b;
/* [0, P) の数を2個足した結果は 2*P 未満 */
if (ret >= P) ret -= P;
return ret;
}
/* a * b mod P を返す */
int mul(int a, int b) {
return (int)((long long)a * b % P);
}
/* 同じ文字が len 文字連続した文字列に対して操作を行ったとき、何文字になるかを求める */
int elementLength(int len) {
int ans = 1; /* 最初にアルファベットを1個おく */
/* 文字数の十進表現の長さを求める */
do {
ans++;
len /= 10;
} while (len > 0);
return ans;
}
/* [もとの文字列を何文字決めたか][操作後の文字列が何文字になったか] */
int memo[MAX][MAX];
char memoValid[MAX][MAX];
int calc(int srcLen, int destLen) {
int ans = 0;
int i;
/* 操作後の文字列の長さが N 以上になったため、条件を満たさない */
if (destLen >= N) return 0;
/* 操作後の文字列の長さが N 未満のまま操作前の文字列が N 文字になったので、条件を満たす */
if (srcLen >= N) return 1;
/* メモがあるなら、その値を返す */
if (memoValid[srcLen][destLen]) return memo[srcLen][destLen];
/* 次に同じ文字を何文字置くか、それぞれを試す */
for (i = 1; srcLen + i <= N; i++) {
ans = add(ans, calc(srcLen + i, destLen + elementLength(i)));
}
if (srcLen == 0) {
/* 最初は、好きな文字を選べる */
ans = mul(ans, 26);
} else {
/* 前回使った文字以外の中から好きな文字を選べる */
ans = mul(ans, 25);
}
/* 結果をメモして返す */
memo[srcLen][destLen] = ans;
memoValid[srcLen][destLen] = 1;
return ans;
}
int main(void) {
if (scanf("%d%d", &N, &P) != 2) return 1;
printf("%d\n", calc(0, 0));
return 0;
}
提出 #36903869 - モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）
無事TLEになった。(WAやREは出なかった)
メモの枠が $O(N^2)$ あり、1枠埋めるのに何文字加えるかを全通り試しているので $O(N)$、合わせて $O(N^3)$ である。
よく見ると、何文字加えるかを試しているとき、一手打った後の操作前の文字列の長さは1ずつ増えていくのに対し、
操作後の文字列の長さはあまり変わらないことがわかる。
そこで、ここを累積和を用いて高速化したい。
メモの直接操作
累積和を導入する準備として、ここまで書いたコードの変形を行う。
よく見ると、各状態における探索は、操作前の文字数の長さが今よりも長い状態にのみ依存している。
そこで、累積和を取りやすいように、再帰関数のかわりに操作前の文字列の長い順のループを用い、メモのデータに直接アクセスして処理を行う形に変形した。
#include <stdio.h>
#define MAX 3156
int N, P;
/* a + b mod P を返す */
int add(int a, int b) {
int ret = a + b;
/* [0, P) の数を2個足した結果は 2*P 未満 */
if (ret >= P) ret -= P;
return ret;
}
/* a * b mod P を返す */
int mul(int a, int b) {
return (int)((long long)a * b % P);
}
/* 同じ文字が len 文字連続した文字列に対して操作を行ったとき、何文字になるかを求める */
int elementLength(int len) {
int ans = 1; /* 最初にアルファベットを1個おく */
/* 文字数の十進表現の長さを求める */
do {
ans++;
len /= 10;
} while (len > 0);
return ans;
}
/* [もとの文字列を何文字決めたか][操作後の文字列が何文字になったか] */
int memo[MAX][MAX];
int main(void) {
int srcLen, destLen;
if (scanf("%d%d", &N, &P) != 2) return 1;
/* 操作後の文字列が N 文字未満で、操作前の文字列が N 文字に到達した */
for (destLen = 0; destLen < N; destLen++) {
memo[N][destLen] = 1;
}
/* 操作前の文字列の長い順に求めていく */
for (srcLen = N - 1; srcLen >= 0; srcLen--) {
/* 操作後の文字列が N 文字以上になったら条件を満たさないので、そこまで求めればいい */
for (destLen = 0; destLen < N; destLen++) {
int ans = 0;
int i;
/* 次に同じ文字を何文字置くか、それぞれを試す */
for (i = 1; srcLen + i <= N; i++) {
ans = add(ans, memo[srcLen + i][destLen + elementLength(i)]);
}
if (srcLen == 0) {
/* 最初は、好きな文字を選べる */
ans = mul(ans, 26);
} else {
/* 前回使った文字以外の中から好きな文字を選べる */
ans = mul(ans, 25);
}
/* 結果をメモする */
memo[srcLen][destLen] = ans;
}
}
printf("%d\n", memo[0][0]);
return 0;
}
提出 #36904018 - モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）
このコードも、無事TLEになった。
ループを用いているため、前のコードより $O(N^3)$ であることがわかりやすい。
累積和の導入
各状態において、何文字置くか (すなわち、操作前の文字列を何文字増やすか) をどんどん増やしながら答えを足していく。
このとき、操作後の文字列の長さは操作前の文字列を増やす量の桁数が増える時にしか増えないので、累積和を利用可能である。
具体的には、以下の図において、現在の状態が斜線部分とすると、赤い部分の和を求めたい。
($q+100 \leq N < q+1000$ とする)
そこで、それぞれの「操作後の長さ」について。「操作前の長さ」の降順に累積和を計算しておく。
降順に計算することで、新しい「操作前の長さ」について答えが求まったとき、それを累積和に反映させやすくなる。
そして、「操作前の長さ」を増やす量を9まで、99まで、999まで、… で区切り、それぞれにおける操作後の長さについて累積和から区間の和を求める。
それらの区間の和を用いることで、1個の状態あたり数回の計算で答えを求めることができる。
#include <stdio.h>
#define MAX 3156
int N, P;
/* a + b mod P を返す */
int add(int a, int b) {
int ret = a + b;
/* [0, P) の数を2個足した結果は 2*P 未満 */
if (ret >= P) ret -= P;
return ret;
}
/* a - b mod P を返す */
int sub(int a, int b) {
if (b == 0) return a;
/* b が正のとき、P - b は P 未満 */
/* b が P 未満 のとき、P - b は正 */
return add(a, P - b);
}
/* a * b mod P を返す */
int mul(int a, int b) {
return (int)((long long)a * b % P);
}
/* [もとの文字列を何文字決めたか][操作後の文字列が何文字になったか] */
int memo[MAX][MAX];
/* もとの文字列の長さの降順の累積和 */
int memoSum[MAX][MAX];
int main(void) {
int srcLen, destLen;
if (scanf("%d%d", &N, &P) != 2) return 1;
/* 操作後の文字列が N 文字未満で、操作前の文字列が N 文字に到達した */
for (destLen = 0; destLen < N; destLen++) {
memo[N][destLen] = 1;
memoSum[N][destLen] = 1;
}
/* 操作前の文字列の長い順に求めていく */
for (srcLen = N - 1; srcLen >= 0; srcLen--) {
/* 操作後の文字列が N 文字以上になったら条件を満たさないので、そこまで求めればいい */
for (destLen = 0; destLen < N; destLen++) {
int ans = 0;
int i;
int delta = 2; /* 操作後の文字列の長さが増える量 */
int deltaLast = 9; /* 増える量が delta となる最後の置く長さ */
/* 次に同じ文字を何文字置くか、それぞれを試す */
for (i = 1; srcLen + i <= N; ) {
/* 操作前の文字列が N 文字になるまでで打ち切る */
if (srcLen + deltaLast > N) deltaLast = N - srcLen;
/* 累積和を用いて加算する */
ans = add(ans, sub(memoSum[srcLen + i][destLen + delta],
memoSum[srcLen + deltaLast + 1][destLen + delta]));
/* 次の部分について求める準備をする */
i= deltaLast + 1;
delta++;
deltaLast = deltaLast * 10 + 9;
}
if (srcLen == 0) {
/* 最初は、好きな文字を選べる */
ans = mul(ans, 26);
} else {
/* 前回使った文字以外の中から好きな文字を選べる */
ans = mul(ans, 25);
}
/* 結果をメモする */
memo[srcLen][destLen] = ans;
/* 累積和をとる */
memoSum[srcLen][destLen] = add(memo[srcLen][destLen], memoSum[srcLen + 1][destLen]);
}
}
printf("%d\n", memo[0][0]);
return 0;
}
提出 #36904284 - モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）
ACになった。
$O(N^2)$ 個の状態それぞれについて、$N$ の桁数にだいたい比例する量の計算を行うので、$O(N^2 \log N)$ である。
おまけ
AtCoder に載っている解説
- 解説 - モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249） (公式 by PCTprobability)
- 解説 - モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249） (by Nyaan)
「ABC249 RLE」でググって出て来た解説
- 【AtCoder解説】PythonでABC249のA,B,C,D,E,F問題を制する！ - Qiita
- ABC249E - RLE - 競プロはじめました
- AtCoder Beginner Contest 249 E問題 RLE - Kazun の競プロ記録
- モノグサプログラミングコンテスト2022 (AtCoder Beginner Contest 249) E - RLE (500) - procon-kirokuyou
- AtCoder Beginner Contest 249 赛时记录 - Suzt_ilymtics - 博客园 ※中国語
- AtCoder Beginner Contest 249题解（E，F）_李公全的博客-CSDN博客 ※中国語
dp[0][0] = 1 としている時点で、自分とは考え方が違っているようである。