結果
問題 |
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 |
ソースコード
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); }