AtCoder AGC062 参加資格ゲット記念で挑んでみた話 (A, C 解答付き)

# はじめに

[AtCoder Grand Contest 062 \- AtCoder](https://atcoder.jp/contests/agc062)

https://qiita.com/hossie/items/19b2c3d9ebe789f05a3a 

水色になり、AGC の参加資格をゲットしました。そこで記念に 2023/05/21 の AGC062 に挑戦してきました。

|コンテスト|レーティング更新対象|推奨|時間|
|---|---|---|---|
|ABC: Beginner|0 - 1999 (青)||1時間40分|
|ARC: Regular|0 - 2799 (橙)||2時間|
|AGC: Grand|1200 (水色) - inf|2000 (黄色) -[^1]|3時間|

[^1]: https://twitter.com/atcoder/status/1266976796525789184

AGC の推奨レベルに達していません。本記事は背伸びして挑んでみました、という記録です。


# AGC062-A (60分)
* [A \- Right Side Character](https://atcoder.jp/contests/agc062/tasks/agc062_a)

## そのまま実装して TLE を確認 (10分)

* [提出 \#41605655 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41605655)

まずは問題文に書いている通りそのまま実装します。

結果、AC 8, TLE 19。知ってた。5分ロスです。まあ、早解きの ABC ならともかく 1問解ければ勝利の AGC では気になりません。


## 手を動かして仕組みを見つける (30分)

問題のサンプル入力を、手を動かして解いてみました。

```
1回目:
A B B A B A 
 ↘ ↘ ↘ ↘ ↘
  B     B
    B A   A
```

```
2回目:
  B B B A A
   ↘ ↘ ↘ ↘
          A
    B B A
```

```
3回目:
    A B B A
     ↘ ↘ ↘
      B  
        B A
```

```
4回目:
      B B A
       ↘ ↘
          
        B A
```

```
5回目:
        B A
         ↘

          A
```

2回目の `BBB` が `BB` になるところが気になります。途中に別の文字が割り込まれることはありません。1手進むごとに 1つ短くなるだけです。

そうすると、「B が 2つ以上並んでいても、最後の答えは 1つと同じになりそう」という仮説にができます。 A も同じです。

```
A A A A A A X
 ↘ ↘ ↘ ↘ ↘ ↘
  A A A A A X
   ↘ ↘ ↘ ↘ ↘
    A A A A X
     ↘ ↘ ↘ ↘
      A A A X
       ↘ ↘ ↘
        A A X
         ↘ ↘
          A X
           ↘
            X
```

```
B B B B B B X
 ↘ ↘ ↘ ↘ ↘ ↘
  B B B B B X
   ↘ ↘ ↘ ↘ ↘
    B B B B X
     ↘ ↘ ↘ ↘
      B B B X
       ↘ ↘ ↘
        B B X
         ↘ ↘
          B X
           ↘
            X
```

そうすると隣り合う文字を縮めれば、問題文は `ABAB...` パターンと `BABA...` パターンの2択です。しかも、この場合も 1回操作すると、

```
A B A B A B A
 ↘ ↘ ↘ ↘ ↘ ↘
  B   B   B
    A   A   A

→ BBBAAA
→ BA
→ A
```

```
B A B A B A B
 ↘ ↘ ↘ ↘ ↘ ↘
    B   B   B
  A   A   A

→ BBBAAA
→ BA
→ A
```

`A` で終わることがすぐわかる簡単なパターンになります。

だいたいの場合が `A` で終わりそうです。 `B` で終わるのは、同じ文字を圧縮した結果が `B` または `AB` で終わるとき、だけではないかと。

```
A B
 ↘ 
  B
```

## テストケースを書く (10分)

本当に同じ文字が連続しても結果が変わらないの？ と思い、テストケースを書いてみました。たしかに変わらなそうです。`B` が答えになるのがレアっぽいことも分かります。

```rust
#[test]
fn test_func() {
    use itertools::Itertools;
    assert_eq!(f("ABBABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABBBABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABBBBABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAAABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAAAABA".chars().collect_vec()), 'A');

    assert_eq!(f("ABA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAAA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAAAA".chars().collect_vec()), 'A');

    assert_eq!(f("AB".chars().collect_vec()), 'B');
    assert_eq!(f("AAA".chars().collect_vec()), 'A');
    assert_eq!(f("ABAB".chars().collect_vec()), 'A');
}
```

このようにいろいろなパターンをテストするときには、main に処理を書くより `f()` のような関数に分けると良いです。


## 解く (10分)

* [提出 \#41607982 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41607982)

```rust
use proconio::{input, marker::Chars};
 
fn f(s: Vec<char>) -> char {
    let n = s.len();
    let mut s0 = Vec::with_capacity(n - 1);
    s0.push(s[0]);
    for i in 0..(n - 1) {
        if s[i] != s[i + 1] {
            s0.push(s[i + 1]);
        }
    }
    if s0[0] == 'A' {
        if s0.len() == 2 { 'B' } else { 'A' }
    } else {
        if s0.len() == 1 { 'B' } else { 'A' }
    }
}
 
fn main() {
    input! {
        t: usize,
    }
    for _ in 0..t {
        input! {
            _: usize,
            s: Chars,
        }
        let result = f(s);
        println!("{}", result);
    }
}
```

タネが分かれば ABC の前半戦みたいな感じです。もしかすると前日の ABC302-B の方が面倒なくらいに。

`f()` を最初の遅い実装から書き換えて、全部のテストが通ることを確認。たぶん大丈夫でしょうと `cargo compete submit a`。

AC。お疲れさまでした。


# 次に取り組む問題を探す (20分)

もう満足しても良いところでしたが、あと2時間弱ありますし、問題だけは読んでみましょうと。

* AGC062-B: 15分考えて手がかりの欠片もなく、そっと閉じ
* AGC062-C: 5分考えて B よりはいけるかも？ という感覚

D 問題以降は考えてもしょうがなさそうですから、ここまでで割り切って AGC062-C に集中することにしました。


# AGC062-C (80分)
* [C \- Mex of Subset Sum](https://atcoder.jp/contests/agc062/tasks/agc062_c)

## 方針を考える (20分)

* まずは入力配列をソート、小さな数字から考える
* 小さな数字から「表現できる範囲」を `BTreeSet` で管理すると良さそう
    * たとえば `[1, 2, 4, 16]` の 4つの数字を使うと `(0, 7), (16, 23)` $1≦x≦7, 16≦x≦23$ の値を表現できる、のように
* 「表現できる範囲」に含まれない値を出力する
    * `(0, 7), (16, 23)` の場合は `8 9 10 ... 15` を順に出力する
    * 区間の間だけでは $K$ 個にならない場合、 `24 25 ....` も順に出力する
* 配列の要素を 1つ見るたびに、それまで使える範囲の組に今回の値を足したものを追加すると良さそう
    * たとえば `[1, 2, 4]` では `(0, 7)` の範囲を扱え、これに `6` を追加すると `(0 + 6, 7 + 6)` も扱えるようになる
* 配列の要素を 1つ見るたびに、区間の重複が起こりうるので、その都度マージすれば良さそう
    * たとえば `(0, 7), (6, 13)` をあわせて ` (0, 13)` とみなすことができる
* $K$ を十分解答できるところまでで探索を打ち切る必要があるはず
    * `[1, 3, 9, 27]` みたいな入力が与えられると、区間のマージが行えず、組の数が発散するはず
    * 答えを $K$ 個出力したいときに、最終的な範囲が先頭から $K$ 個分分かれば大丈夫。ここで打ち切ればきっと発散しないはず
    * もしかするとここに検討漏れがあるかもしれない
* ここまでで、はまらなければ 1時間強で実装できるはず

## 実装と不具合修正 (60分)

この通り実装しました。C++ ならこの手の `set` マージは簡単なのに、 Rust だと `BTreeSet` の読み取りと編集を同時に行えなくて面倒だと思いながら。

### 提出1: 探索打ち切りなし版 CE
* [提出 \#41610924 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41610924)

Compile Error。`cargo compete submit` でエラーになるときはだいたいこちらです。

> error: Could not extract information

どこがコンパイルエラーになるかは提出ページに書いています。その通り修正します。

```
27 |                 (l0, r0) = (l1, r1);
   |                 -------- ^
   |                 |
   |                 cannot assign to this expression
```

Rust 1.42 はつらいです。AtCoder 言語アップデートに期待です。[^2]

[^2]: https://atcoder.jp/posts/966

### 提出2: 探索打ち切りなし版 TLE
* [提出 \#41610976 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41610976)

探索打ち切りなし版。想定通り TLE です。WA はありませんでした。
この方針で打ち切り処理を書けば通過できるかも？ と欲が出てきました。

### 提出3: 探索打ち切り追加 WA
* [提出 \#41611262 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41611262)

半分ほど WA です。打ち切りの実装を間違えています。ひどい。
速度的には TLE から一瞬で返るようになっていました。方針的には良さそうです。

次は間違えないように単体テストを書きます。

```rust
#[test]
fn test_func() {
    assert_eq!(f(3, &[1, 2, 5]), vec![4, 9, 10]);
    assert_eq!(f(3, &[2, 5]), vec![1, 3, 4]);
    assert_eq!(f(1, &[100]), vec![1]);
    assert_eq!(f(2, &[100]), vec![1, 2]);
    assert_eq!(f(5, &[4]), vec![1, 2, 3, 5, 6]);
    assert_eq!(f(3, &[2, 2, 2]), vec![1, 3, 5]);
    assert_eq!(f(4, &[2, 2, 2]), vec![1, 3, 5, 7]);
    assert_eq!(f(5, &[2, 2, 2]), vec![1, 3, 5, 7, 8]);
}
```

### 提出4: WA 1
* [提出 \#41611396 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41611396)

勝利したと思ったのですが……。まだ何か抜けていました。

### 提出6: AC
* [提出 \#41611642 \- AtCoder Grand Contest 062](https://atcoder.jp/contests/agc062/submissions/41611642)

探索打ち切りを誤って $K$ の 1個分手前にしてしまうことがあるようでした。制限時間はとても余裕がありますから、念のため $K$ の 2倍見るようにしても大丈夫でしょう。というわけで追加。 AC。お疲れさまでした。 [^3]

[^3]: その前にうっかり、$K$ の 2倍で打ち切るつもりで、半分で打ち切るものを入れてしまって、さらに 1WA。焦ると良くないです。

このケース、単体テストを作るときに気づきませんでした。テストケースとして想定している運営はさすがだと思いました。

最終的にはこんな感じのコードになりました。長いです。でも使っているアルゴリズムの道具としては `BTreeSet` くらいで、「何かを知らなければ解けない」系ではありませんでした。じっくり時間をかけて解いても良いというのは、ABC とはまた違う楽しさがあると思いました。

```rust
use std::collections::BTreeSet;

use itertools::Itertools;
use proconio::input;

fn f(k: usize, a: &[usize]) -> Vec<usize> {
    let mut v = Vec::with_capacity(k);
    let mut set0 = BTreeSet::new(); // (1, 3) means 1..=3
    set0.insert((0usize, 0usize));
    'outer: for &x in a {
        // skip test
        {
            let mut k0 = 0;
            let mut r1 = 0;
            for &(l, r) in &set0 {
                if l > 0 {
                    k0 += l - r1 - 1;
                }
                if k0 > k {
                    break 'outer;
                }
                if r >= x {
                    break;
                }
                r1 = r;
            }
        }

        let prev = set0.clone();
        for (l, r) in prev {
            set0.insert((l + x, r + x));
        }

        // merge
        let mut set1 = BTreeSet::new();
        let mut it = set0.iter();
        let (mut l0, mut r0) = (0, 0);
        if let Some(x0) = it.next() {
            l0 = x0.0;
            r0 = x0.1;
        }
        while let Some(x1) = it.next() {
            let &(l1, r1) = x1;
            if r0 + 1 < l1 {
                set1.insert((l0, r0));
                l0 = l1;
                r0 = r1;
            } else {
                r0 = r0.max(r1);
            }
        }
        set1.insert((l0, r0));
        set0 = set1;
    }

    let mut it = set0.iter();
    let mut r0 = 0;
    if let Some(x0) = it.next() {
        r0 = x0.1;
    }
    while let Some(x1) = it.next() {
        let &(l1, r1) = x1;
        for i in (r0 + 1)..l1 {
            v.push(i);
            if v.len() == k {
                return v;
            }
        }
        r0 = r1;
    }
    let r1 = r0 + 1 + k - v.len();
    for i in (r0 + 1)..r1 {
        v.push(i);
    }
    v
}

fn main() {
    input! {
        n: usize,
        k: usize,
        mut a: [usize; n],
    }
    a.sort();
    let result = f(k, &a).iter().join(" ");
    println!("{}", result);
}
```


# その後 (20分)

* [D \- Walk Around Neighborhood](https://atcoder.jp/contests/agc062/tasks/agc062_d)

も眺めました。初手は打てそうでも、残り 20分で解けるわけがありません。制限時間を待つだけでした。


# 最後に

https://twitter.com/hossie/status/1660301668163162112

当日に問題の一言感想を書いていました。もしかすると試行錯誤の跡も役に立つかも、と思っていろいろ書き足してみました。

AGC062 参加は良い経験になりました。それにしてもこんな難しい問題を早解きしている上位陣は、いったいなにがどうなっているんでしょうか……。