RustでTLE地獄を超えた！ABC406 Cをランレングス圧縮で突破した話

## TL;DR

* **ABC406 C問題の「山谷数え上げ」を徹底分解**
* **三重ループ爆死 → ランレングス圧縮（RLE）で高速化**
* **O(N³) から O(N) へ魔法のような改善法をRustで実装**
* **初心者〜中級者でも追体験できる失敗→学び→成功の実録**

---

## C問題の概要 — チルダ型とは？

AtCoder Beginner Contest 406 の C問題では、与えられた整数列から「**チルダ型部分列**」を数え上げる課題が出題されます。

### 問題をざっくり要約すると：

* 長さ N の整数列が与えられる
* 長さ4以上の連続部分列のうち、

  * 最初は増加
  * 途中で山1つ＆谷1つだけ含む
  * 最後も増加で終わる
* 上記の部分列の個数を求めよ！

……と聞いても、最初は **「え、チルダ？山谷？なんぞそれ」** という反応でした。

---

## 内容難しすぎて諦める

最初に問題文を読んだ瞬間はこう思いました：

> 「は？山と谷って何だ？部分列？探索？全探索？あーーーもう無理」

そこでとりあえず手を動かし、**三重ループの愚直実装**を書いたんですが：

```rust
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** で組み上げた実装です👇

```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問題、怖くないかも！」と思う誰かの背中を押せたら嬉しいです。**

---