結果

問題 No.111 あばばばば
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-29 10:33:57
言語 D
(dmd 2.109.1)
結果
MLE  
実行時間 -
コード長 1,190 bytes
記録
コンパイル時間 4,057 ms
コンパイル使用メモリ 168,064 KB
実行使用メモリ 816,356 KB
最終ジャッジ日時 2025-08-29 10:34:08
合計ジャッジ時間 9,079 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;

import std;

// https://klee.hatenablog.jp/entry/2020/06/18/210754 より
// 最長回文半径の配列を計算する
// padding: 偶数長の回文を調べるための詰め物
long[] manacher(string padding = "#")(string _s)
{
	auto s = padding ~ _s.map!(a => only(a)).joiner(padding).array.to!string ~ padding;
	long n = s.length;
	auto rad = new long[](n);
	long c = 0, r = 0;
	while (c < n) {
		// cを中心に同じ文字がどこまで連続するか
		while (0 <= c - r && c + r < n && s[c - r] == s[c + r]) r++;
		rad[c] = r;
		// 回文の長さに応じて利用可能な範囲を確認しつつメモ
		long k = 1;
		while (0 <= c - k && k + rad[c - k] < r) {
			rad[c + k] = rad[c - k];
			k++;
		}
		//すでに計算が終わった分だけ中心と探索半径をずらす
		c += k;
		r -= k;
	}
	// paddingの分の補正
	foreach (i, ref v; rad) {
		if (i % 2 == 0)
			v = (v - 1) / 2;
		else
			v /= 2;
	}
	return rad;
}

void main()
{
	// 入力
	long L = readln.chomp.to!long;
	// 答えの計算
	auto res = manacher("ab".repeat(L / 2).joiner("").array.to!string ~ "a").filter!(a => a >= 2);
	// 答えの出力
	writeln(res.sum - res.walkLength);
}
0