結果

問題 No.291 黒い文字列
コンテスト
ユーザー ゴリポン先生
提出日時 2026-07-24 15:12:19
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 1,410 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,193 ms
コンパイル使用メモリ 173,944 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-24 15:12:26
合計ジャッジ時間 6,171 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/10/16/0900 より
// 動的計画法、文字列処理
import std;

// aとbを比較してbの方が大きいならばaの値をbに更新する
void chMax(T)(ref T a, in T b)
{
	if (a < b) a = b;
}
// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}

void main()
{
	// 入力
	auto S = readln.chomp;
	// 答えの計算
	int L = S.length.to!int;
	auto dp = new int[][][][][](2, 21, 21, 21, 21);
	fill(dp, -1);
	dp[0][0][0][0][0] = 0;
	int ans = 0;
	foreach (i; 0 .. L) {
		int cur = i % 2, tar = cur ^ 1;
		dp[tar] = dp[cur].dup;
		foreach (a; 0 .. 21) foreach (b; 0 .. 21) foreach (c; 0 .. 21) foreach (d; 0 .. 21) {
			if (dp[cur][d][c][b][a] < 0) continue;
			int v = dp[cur][d][c][b][a];
			if ((S[i] == 'K' || S[i] == '?') && a < 20) chMax(dp[tar][d][c][b][a + 1], v);
			if ((S[i] == 'U' || S[i] == '?') && b < 20 && a) chMax(dp[tar][d][c][b + 1][a - 1], v);
			if ((S[i] == 'R' || S[i] == '?') && c < 20 && b) chMax(dp[tar][d][c + 1][b - 1][a], v);
			if ((S[i] == 'O' || S[i] == '?') && d < 20 && c) chMax(dp[tar][d + 1][c - 1][b][a], v);
			if ((S[i] == 'I' || S[i] == '?') && d) chMax(ans, v + 1), chMax(dp[tar][d - 1][c][b][a], v + 1);
		}
	}
	// 答えの出力
	writeln(ans);
}
0