TL;DR
- ABC406 C問題の「山谷数え上げ」を徹底分解
- 三重ループ爆死 → ランレングス圧縮（RLE）で高速化
- O(N³) から O(N) へ魔法のような改善法をRustで実装
- 初心者〜中級者でも追体験できる失敗→学び→成功の実録
C問題の概要 — チルダ型とは？
AtCoder Beginner Contest 406 の C問題では、与えられた整数列から「チルダ型部分列」を数え上げる課題が出題されます。
問題をざっくり要約すると：
-
長さ N の整数列が与えられる
-
長さ4以上の連続部分列のうち、
- 最初は増加
- 途中で山1つ＆谷1つだけ含む
- 最後も増加で終わる
-
上記の部分列の個数を求めよ！
……と聞いても、最初は 「え、チルダ？山谷？なんぞそれ」 という反応でした。
内容難しすぎて諦める
最初に問題文を読んだ瞬間はこう思いました：
「は？山と谷って何だ？部分列？探索？全探索？あーーーもう無理」
そこでとりあえず手を動かし、三重ループの愚直実装を書いたんですが：
use proconio::input;
fn main(){
// 入力読み込み: Nと整数列Pを受け取る
input! {
_n : usize, // 配列の長さ
_p : [usize; _n] // 配列Pそのもの
}
let mut ans = 0; // 答え（条件を満たす部分列の個数）を格納
// 部分列の開始位置を全探索
// 部分列の長さは最低でも4以上なので (_n - 3) まで回す
for first in 0.._n-3 {
// 部分列の終了位置を全探索
// 長さが4以上なので finishは first+3 以上から探索開始
for finish in 3+first.._n {
// 現在の部分列を格納する一時配列を作成
let mut judgement_vec: Vec<usize> = Vec::new();
// first から finish までの区間を切り出す
for j in first..=finish {
judgement_vec.push(_p[j]);
}
// 部分列が条件を満たしていればカウントを増やす
if judgemnent(judgement_vec){
ans += 1;
}
}
}
// 結果出力
println!("{}", ans);
}
// 部分列が条件を満たすかどうか判定する関数
fn judgemnent(judgement_vec : Vec<usize>) -> bool {
// 先頭2要素を取り出す
let a1 = judgement_vec[0];
let a2 = judgement_vec[1];
// 先頭が昇順であることを確認（問題の条件その1）
if a1 < a2 {
let mut judgement_count = 0;
// 中央部分の山・谷判定
// i: 1からlength-2まで走査（3つの要素を並べて山/谷を確認）
for i in 1..judgement_vec.len()-1 {
// ここが山または谷かどうかを判定する条件式
if (judgement_vec[i-1] < judgement_vec[i] && judgement_vec[i] > judgement_vec[i+1])
|| (judgement_vec[i-1] > judgement_vec[i] && judgement_vec[i] < judgement_vec[i+1]) {
// 山または谷を検出したらカウント
judgement_count += 1;
}
}
// 山・谷がちょうど2回検出されたら条件成立
if judgement_count == 2 {
return true;
}
}
// それ以外は条件不成立
return false;
}
秒殺でTLE（Time Limit Exceeded）。
まさに 「赤い死亡通知」 を受け取りました。
問題内容を分解することに
諦めるのは悔しいので、問題を図解して整理することに。
ここで気付きました：
-
隣り合う要素の大小関係を
-
<（増加） -
>（減少）
に変換すると良さそうだと。
-
たとえば：
入力: 1 3 6 4 2 5
大小: < < > > <
つまり：大小関係を文字列に落とせば、文字列上のパターンマッチになる！
解法が思い浮かばずに諦める（再び）
が、ここでまた詰まります。
「山谷1個ずつとか、部分列どう探索するのよ…」
- 素朴に全部列挙 → O(N³) ⇒ 爆死確定
- DFSもシミュレーションも面倒 ⇒ 萎え
QiitaやTwitterをググっても、みんな「ランレングス圧縮で解けます！」と書いてる。
「ランレングス？何それ美味しいの？」 状態に突入します。
ランレングスを学んでみる
✅ RLE（Run Length Encoding）とは？
- 連続する同じ文字を (文字, 連続個数) に圧縮する手法。
例：
<<>><<>>> → [('<',2), ('>',2), ('<',2), ('>',3)]
文字列全体を圧縮しながら、「どの位置に連続した山谷ブロックが出現するか」を整理できる！
天才すぎる……。
✅ どう使う？
-
<…>という文字列にしてからRLE -
RLE上で
- 真ん中が
> - 両側が
<
になってるブロックを発見
- 真ん中が
-
それぞれの長さを掛け算 ⇒ a × b
これだけで部分列の個数が一撃で出せる！！
ランレングス圧縮をして実装してみる
では、実際に Rust で組み上げた実装です👇
use proconio::input;
fn main(){
// 入力部分
input! {
_n : usize, // 数列の長さN
_p : [usize; _n] // 整数列P
}
// 隣接要素を比較し、大小関係を文字列化する
// _p[i] < _p[i+1] なら '<'、そうでなければ '>' として文字列に追加
let mut run_length_encoding_str = String::new();
for i in 0.._n-1 {
if _p[i] < _p[i+1] {
run_length_encoding_str.push('<');
} else {
run_length_encoding_str.push('>');
}
}
// ランレングス圧縮（RLE）を実行して、連続する同一文字を (文字, 連続回数) のペアに変換
let rle = run_length_encoding(&run_length_encoding_str);
let mut ans = 0; // 条件を満たす部分列の個数をカウントする変数
// RLE結果を走査：常に「中央の '>' ブロック」を探索する
for i in 1..rle.len() - 1 { // 先頭と末尾は '>' になりえないのでスキップ
if rle[i].0 == '>' {
// 現在位置iの両隣 (i-1, i+1) が '<' ブロックであることが前提
// 各 '<' ブロックの長さを掛け合わせることで部分列の数を計算
ans += rle[i-1].1 * rle[i+1].1;
}
}
// 最終的な答えを出力
println!("{}", ans);
}
// ランレングス圧縮を行う関数
fn run_length_encoding(input : &str) -> Vec<(char, usize)> {
let mut rle : Vec<(char, usize)> = Vec::new(); // 圧縮結果を格納するベクタ
// 空文字列の場合は空の結果を返して終了
if input.is_empty() {
return rle;
}
// 文字列を1文字ずつ取り出してイテレート
let mut input_chars = input.chars();
// 最初の文字を取得（unwrapで安全に取り出し）
let mut now_char = input_chars.next().unwrap();
let mut count = 1; // 最初の文字が1個登場済み
// 2文字目以降を順に処理
for c in input_chars {
if c == now_char {
// 同じ文字が続く場合はカウントをインクリメント
count += 1;
} else {
// 違う文字が出てきた場合、現在までの (文字, 個数) を結果に追加
rle.push((now_char, count));
// カウントをリセットして新しい文字を追跡開始
now_char = c;
count = 1;
}
}
// 最後の連続部分を忘れずに追加
rle.push((now_char, count));
return rle;
}
✅ 計算量
- 大小文字列化 → O(N)
- RLE圧縮 → O(N)
- 部分列探索 → O(ブロック数) ≤ O(N)
⇒ 合計 O(N) の爆速コード完成✨
まとめ
- RLEは競プロで本当に役立つ武器
- パターンマッチングは文字列化→圧縮→区間和が鉄板
最初にTLEを食らった自分を殴りに行きたいくらいシンプルな解法でした。
この記事が「C問題、怖くないかも！」と思う誰かの背中を押せたら嬉しいです。