AtCoder ABC308 全問題の解説スライドを作ってみた

はじめに

2023-07-02 に行われた CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308) - AtCoder の A～Ex 全問題の解説スライドを、水色コーダーが Draw.io で描いてみました。

スライド

ABC308 A - New Scheme

• 問題: A - New Scheme

ABC308 A スライドのキーワード

• 小問1: 8 つの整数を標準入力から受け取る
  • 言語によっては地味に大変。仕組みに乗るのをおすすめです
• 小問2: 整数 1 つの条件を確認する
  • 条件 2: $100 \le S_1, S_2, ...S_8 \le 675$
  • 条件 3: $S_1, S_2, ...S_8$ はすべて 25 の倍数
  • 8 個の配列を for 文で回し、それぞれ条件を満たすか確認する
• 小問3: 整数 2 つの条件を確認する
  • 条件 1: $S_1 \le S_2 \le ... \le S_8$
  • 7 個のペアを for 文で回し、それぞれ条件を満たすか確認する
• 実装例:
  • 小問 1 のコメント部分に小問 2, 3 を貼り付け
  • 最後に "Yes" を出力するコードを追加

ABC308 A 実装例 上 (Rust, インデックスを使った for)

ABC308-A-1.rs

use proconio::input;

fn main() {
    input! {
        s: [usize; 8],
    }
    for i in 0..8 {
        let x = s[i];
        if !(100 <= x && x <= 675) || x % 25 != 0 {
            println!("No");
            return;
        }
    }
    for i in 0..7 {
        if s[i] > s[i + 1] {
            println!("No");
            return;
        }
    }
    println!("Yes");
}

ABC308 A 実装例 下 (Rust, インデックスを使わない for)

ABC308-A-2.rs

use proconio::input;

fn main() {
    input! {
        s: [usize; 8],
    }
-   for i in 0..8 {
-       let x = s[i];
+   for &x in &s {
        if !(100 <= x && x <= 675) || x % 25 != 0 {
            println!("No");
            return;
        }
    }
-   for i in 0..7 {
-       if s[i] > s[i + 1] {
+   for v in s.windows(2) {
+       if v[0] > v[1] {
            println!("No");
            return;
        }
    }
    println!("Yes");
}

ABC308 A 実装例 その他 (Rust, for を使わず短く書く)

ABC308-A-3.rs

use proconio::input;

fn main() {
    input! {
        s: [usize; 8],
    }
    let yes = s.windows(2).all(|v| v[0] <= v[1])
        && s.iter().all(|&x| (100 <= x && x <= 675) && (x % 25 == 0));
    println!("{}", if yes { "Yes" } else { "No" });
}

ABC308 B - Default Price

• 問題: B - Default Price

ABC308 B スライドのキーワード

• 考察: 入出力例を動かしてみる
  • N, M ≦ 100 なら比較回数はせいぜい 10000 回。そのまま比較する。
    • 扱う数が 2 桁多ければ、map などの連想配列を使って高速化したい
• 実装例:
  • (0..m) の範囲で最初に条件を満たす値を探す find() が便利。
  • 代わりに for ループを二重に回しても良い。

ABC308 B 実装例 左下 (Rust)

ABC308-B-1.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        c: [String; n],
        d: [String; m],
        p: [usize; m + 1],
    }
    let mut result = 0;
    for i in 0..n {
        if let Some(j) = (0..m).find(|&j| d[j] == c[i]) {
            result += p[j + 1];
        } else {
            result += p[0];
        }
    }
    println!("{}", result);
}

ABC308 B 実装例 右下 (Rust)

ABC308-B-2.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        c: [String; n],
        d: [String; m],
        p: [usize; m + 1],
    }
    let mut result = 0;
    for i in 0..n {
-       if let Some(j) = (0..m).find(|&j| d[j] == c[i]) {
-           result += p[j + 1];
-       } else {
-           result += p[0];
-       }
+       let j = (1..=m).find(|&j| d[j - 1] == c[i]).unwrap_or(0);
+       result += p[j];
    }
    println!("{}", result);
}

ABC308 C - Standings

• 問題: C - Standings

ABC308 C スライドのキーワード

• 考察: 浮動小数点型の値のソートを精度良く行うにはどうするか
• 方針1: 比較を整数型で行う
  • $\frac{A_l}{A_l+B_l} < \frac{A_r}{A_r+B_r}$
  • $A_l(A_r+B_r)<A_r(A_l+B_l)$
  • この 2つの比較式は同じ意味。同じ正の値を掛け算している。
  • 下の式は整数だけで行える。 64bit 型の整数で解ける。
• 方針2: 誤差を無視できる精度の高い型を使う
  • $\frac{A_l}{A_l+B_l} \times FACTOR < \frac{A_r}{A_r+B_r} \times FACTOR$
  • 分母に現れる値は 32bit。比較するには分母だけで 64bit 欲しい。
  • $2^{64}$ など大きな値を成功率に掛け算しておけば、誤差で順序関係が変わらずに済む。
  • 128bit 整数型や、多倍数整数型を使う。
  • 80bit 以上の浮動小数点型が使える環境ならそれでも
• Tips:
  • ソートの比較方法を外から与えられる
    • 方針1 のように複数の値を使うこともできる
    • 成功率を「降順」にするなら「-1 を掛けて昇順」
  • 「安定ソート」比較結果が一致するときに順序を維持
    • 「成功率が同じ人は昇順」という本問題で便利
    • 成功率が同じ場合の追加条件を付ける方法でも OK

ABC308 C 実装例 方針1 (Rust)

ABC308-C-1.rs

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

fn main() {
    input! {
        n: usize,
        ab: [(usize, usize); n],
    }
    let mut v = Vec::with_capacity(n);
    for (i, &(a, b)) in ab.iter().enumerate() {
        v.push((i + 1, a, b));
    }
    v.sort_by(|l, r| {
        let (_, la, lb) = l;
        let (_, ra, rb) = r;
        (ra * (la + lb)).cmp(&(la * (ra + rb)))
    });
    let result = v.iter().map(|(i, _, _)| i).join(" ");
    println!("{}", result);
}

ABC308 C 実装例 方針2 (Rust)

ABC308-C-2.rs

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

fn main() {
    input! {
        n: usize,
        ab: [(i128, i128); n],
    }
    const FACTOR: i128 = 1 << 64;
    let mut v = Vec::with_capacity(n);
    for (i, &(a, b)) in ab.iter().enumerate() {
        v.push((i + 1, FACTOR * a / (a + b)));
    }
    v.sort_by_key(|(_, x)| -x);
    let result = v.iter().map(|(i, _)| i).join(" ");
    println!("{}", result);
}

より詳しい記事:

ABC308 D - Snuke Maze

• 問題: D - Snuke Maze

ABC308 D スライドのキーワード

• 考察: 入出力例3の到達可能なマスを順に塗りつぶしていく
  • 右下が塗られた "Yes"
• 実装:
  • 塗りつぶしたマスを覚える二次元配列を用意
    • どこから辿ったか、長さはどうか、という情報は不要
  • 上下左右の「塗りつぶしていない」マスで、新しく辿れるところを順に調べる
    • 辿り方はなんでもいい。全探索できる量なので
    • 塗りつぶしたマスを辿ってしまうと無限ループしかねないことに注意
  • 二次元配列の周辺に 1マス分のダミー (番兵) を作っておくと、実装が楽になる
    • 外枠の上下左右の確認を忘れて範囲外アクセス、ということを防ぐ

ABC308 D 実装例 (Rust)

ABC308-D-1.rs

use std::collections::VecDeque;

use proconio::{input, marker::Chars};

fn f(s: &[Vec<char>]) -> bool {
    if s[0][0] != 's' {
        return false;
    }

    let h = s.len();
    let w = s[0].len();
    let mut m = vec![vec![true; w + 2]; h + 2]; // visited
    for r in 0..h {
        for c in 0..w {
            m[r + 1][c + 1] = false;
        }
    }
    m[1][1] = true;
    let mut queue = VecDeque::new();
    queue.push_back((1, 1)); // row, column

    while let Some((r, c)) = queue.pop_back() {
        for i in 0..4 {
            let (r0, c0) = match i {
                0 => (r - 1, c),
                1 => (r + 1, c),
                2 => (r, c - 1),
                _ => (r, c + 1),
            };
            if m[r0][c0] {
                continue;
            }
            if (s[r - 1][c - 1] == 's' && s[r0 - 1][c0 - 1] == 'n')
                || (s[r - 1][c - 1] == 'n' && s[r0 - 1][c0 - 1] == 'u')
                || (s[r - 1][c - 1] == 'u' && s[r0 - 1][c0 - 1] == 'k')
                || (s[r - 1][c - 1] == 'k' && s[r0 - 1][c0 - 1] == 'e')
                || (s[r - 1][c - 1] == 'e' && s[r0 - 1][c0 - 1] == 's')
            {
                m[r0][c0] = true;
                queue.push_back((r0, c0));
            }
        }
    }

    m[h][w]
}

fn main() {
    input! {
        h: usize,
        _: usize,
        s: [Chars; h],
    }
    let yes = f(&s);
    println!("{}", if yes { "Yes" } else { "No" });
}

ABC308 E - MEX

• 問題: E - MEX

ABC308 E スライドのキーワード

• 考察1: 入出力例3' を眺める
  • 3重ループ 遅そう
• 考察2: それぞれの出現個数を左から数える (累積和)
  • STEP 1. M だけ見る
  • STEP 2. E だけ見る
  • STEP 3. X だけ見る
  • 単純ループ 3回 とても速い
• 別解: M → X → E の順に見る
  • STEP 1. M が左にいくつあるか、左から調べる
  • STEP 2. X が右にいくつあるか、右から調べる
  • STEP 3. E を動かし、両隣の M, X を見てそれぞれの MEX と個数を求める
  • 全部調べられるなら、 M → E → X の順でなくても大丈夫。両端を決めて真ん中を動かすというのも良く行います。

ABC308 E 実装例 (Rust)

ABC308-E-1.rs

use proconio::{input, marker::Chars};

// m:   0,      1,      2
// e 0: 0,      3(0-1), 4(0-2)
//   1: 3(0-1), 1,      5(1-2)
//   2: 4(0-2), 5(1-2), 2
fn update_es(mes: &mut [usize; 6], ms: &[usize; 3], e: usize) {
    match e {
        0 => {
            mes[0] += ms[0];
            mes[3] += ms[1];
            mes[4] += ms[2];
        }
        1 => {
            mes[3] += ms[0];
            mes[1] += ms[1];
            mes[5] += ms[2];
        }
        _ => {
            mes[4] += ms[0];
            mes[5] += ms[1];
            mes[2] += ms[2];
        }
    }
}

// me:  0, 1, 2, 3(0-1), 4(0-2), 5(1-2)
// x 0: 1, 2, 1, 2,      1,      3
//   1: 2, 0, 0, 2,      3,      0
//   2: 1, 0, 0, 3,      1,      0
fn mex(mes: &[usize; 6], x: usize) -> usize {
    match x {
        0 => mes[0] * 1 + mes[1] * 2 + mes[2] * 1 + mes[3] * 2 + mes[4] * 1 + mes[5] * 3,
        1 => mes[0] * 2 + mes[1] * 0 + mes[2] * 0 + mes[3] * 2 + mes[4] * 3 + mes[5] * 0,
        _ => mes[0] * 1 + mes[1] * 0 + mes[2] * 0 + mes[3] * 3 + mes[4] * 1 + mes[5] * 0,
    }
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
        s: Chars,
    }

    let mut ms = vec![[0, 0, 0]; n + 1]; // 0, 1, 2
    for i in 0..n {
        ms[i + 1] = ms[i];
        if s[i] != 'M' {
            continue;
        }
        ms[i + 1][a[i]] += 1;
    }

    let mut mes = vec![[0, 0, 0, 0, 0, 0]; n + 1]; // 0, 1, 2, 0-1, 0-2, 1-2
    for i in 0..n {
        mes[i + 1] = mes[i];
        if s[i] != 'E' {
            continue;
        }
        update_es(&mut mes[i + 1], &ms[i], a[i]);
    }

    let mut result = 0usize;
    for i in 0..n {
        if s[i] != 'X' {
            continue;
        }
        result += mex(&mes[i], a[i]);
    }

    println!("{}", result);
}

ABC308 E 実装例 別解 (Rust)

ABC308-E-2.rs

use proconio::{input, marker::Chars};

fn mex(m: usize, e: usize, x: usize) -> usize {
    (0..3).find(|&i| m != i && e != i && x != i).unwrap_or(3)
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
        s: Chars,
    }

    let mut m = vec![[0, 0, 0]; n]; // 0, 1, 2
    for i in 0..n {
        if i > 0 {
            m[i] = m[i - 1];
        }
        if s[i] == 'M' {
            m[i][a[i]] += 1;
        }
    }

    let mut x = vec![[0, 0, 0]; n]; // 0, 1, 2
    for i in (0..n).rev() {
        if i < n - 1 {
            x[i] = x[i + 1];
        }
        if s[i] == 'X' {
            x[i][a[i]] += 1;
        }
    }

    let mut result = 0usize;
    for i in 0..n {
        if s[i] != 'E' {
            continue;
        }
        for j in 0..3 {
            for k in 0..3 {
                result += m[i][j] * x[i][k] * mex(j, a[i], k);
            }
        }
    }
    println!("{}", result);
}

ABC308 F - Vouchers

• 問題: F - Vouchers

ABC308 F スライドのキーワード

• 考察: 割引額の大きなクーポンから順に、その時点でクーポン使用条件が一番厳しい商品に対して使う (貪欲)
  • 単純な方針ですが、クーポンの使い方を変えてもこれ以上の割引方法が思い当たらなければ、これで実装開始
• 実装例: クーポン使用前の商品を multiset で管理し、1 つずつクーポンを適用する
  • multiset の良いところ:
    • 二分探索が速い
    • 両端以外の追加削除が速い
    • 同じ定価の商品を複数持てる
  • set や map でも解けます

ABC308 F 実装例 (Rust)

ABC308-F-1.rs

use std::collections::BTreeMap;

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        p: [usize; n],
        l: [usize; m],
        d: [usize; m],
    }

    let mut sum: usize = p.iter().sum();
    let mut map = BTreeMap::new();
    for x in p {
        *map.entry(x).or_insert(0) += 1;
    }

    let mut v = Vec::with_capacity(m);
    for i in 0..m {
        v.push((d[i], l[i]));
    }
    v.sort();
    v.reverse();

    for &(d, l) in &v {
        if let Some((&x, &count)) = map.range(l..).next() {
            sum -= d;
            if count == 1 {
                map.remove(&x);
            } else {
                map.insert(x, count - 1);
            }
        }
    }

    println!("{}", sum);
}

ABC308 G - Minimum Xor Pair Query

• 問題: G - Minimum Xor Pair Query

ABC308 G スライドのキーワード

• 考察1: XOR の最小値はどこか、例題を2進数にして眺める
  • 全部の XOR を調べると $O(N^2)$ の組み合わせ確認がとても遅い
  • XOR が小さくなるのは、似た数字のとき
  • つまり、ソートして隣同士だけ調べれば良い。比較回数を $O(N)$ に減らせる
  • 木構造の multiset なら、検索・追加・削除とも $O(\log N)$ と高速
• 考察2: 追加削除のたびに最小値を更新するにはどうするか
  • 隣のすべての XOR も、multiset に入れて管理する
  • 最小値は mutliset の先頭
  • 一回の追加削除で 1個または 3個の入れ替えがある

ABC308 G 実装例 (Rust, multiset 相当を map で代用)

ABC308-G-1.rs

use std::collections::BTreeMap;

use proconio::input;

fn increment_or_insert(map: &mut BTreeMap<usize, usize>, key: usize) {
    *map.entry(key).or_insert(0) += 1;
}

fn decrement_or_remove(map: &mut BTreeMap<usize, usize>, key: usize) {
    if let Some(&count) = map.get(&key) {
        if count == 1 {
            map.remove(&key);
        } else {
            map.insert(key, count - 1);
        }
    }
}

fn main() {
    input! {
        q: usize,
    }
    let mut m_x = BTreeMap::new();
    let mut m_xor = BTreeMap::new();
    for _ in 0..q {
        input! {
            t: usize,
        }
        match t {
            1 => {
                input! {
                    x: usize,
                }
                increment_or_insert(&mut m_x, x);
                if *m_x.get(&x).unwrap() > 1 {
                    increment_or_insert(&mut m_xor, 0);
                    continue;
                }
                if let Some((&x0, _)) = m_x.range(..x).last() {
                    increment_or_insert(&mut m_xor, x0 ^ x);
                    if let Some((&x1, _)) = m_x.range((x + 1)..).next() {
                        decrement_or_remove(&mut m_xor, x0 ^ x1);
                        increment_or_insert(&mut m_xor, x ^ x1);
                    }
                } else if let Some((&x1, _)) = m_x.range((x + 1)..).next() {
                    increment_or_insert(&mut m_xor, x ^ x1);
                }
            }
            2 => {
                input! {
                    x: usize,
                }
                decrement_or_remove(&mut m_x, x);
                if m_x.contains_key(&x) {
                    decrement_or_remove(&mut m_xor, 0);
                    continue;
                }
                if let Some((&x0, _)) = m_x.range(..x).last() {
                    decrement_or_remove(&mut m_xor, x0 ^ x);
                    if let Some((&x1, _)) = m_x.range((x + 1)..).next() {
                        increment_or_insert(&mut m_xor, x0 ^ x1);
                        decrement_or_remove(&mut m_xor, x ^ x1);
                    }
                } else if let Some((&x1, _)) = m_x.range((x + 1)..).next() {
                    decrement_or_remove(&mut m_xor, x ^ x1);
                }
            }
            _ => {
                if let Some((&k, _)) = m_xor.iter().next() {
                    println!("{}", k);
                }
            }
        }
    }
}

ABC308 Ex - Make Q

• 問題: Ex - Make Q

ABC308 Ex スライドのキーワード

• 考察1: 入力例1 で作ることができる Q を眺める
  • ここから分かること:
    • Q の分岐候補 (茶色) を順に調べていく
      • N<300 なので遅くなさそう
    • エッジ 3本以上のノードだけ考えれば良い
      • ノード1, 4, 5 からは Q を作れない
  • 分からないこと:
    • 総コストの小さな Q の作り方
      • ひげ (緑) をどう選ぶ?
    • ループ (青) は 1つ調べれば十分?
      • コストの小さなループの求め方は?
• 考察2: 特定のノード (茶) から伸びるひげ (緑) の候補数は？
  • A) ループ候補ごとにひげを伸ばす:
  • B) ひげ候補ごとに最小ループを調べる:
  • ここから分かること:
    • ループに含まれない、最小コストのノードをひげにしたい
    • ループとひげで、合計 3つのノードを使用する
    • ひげの候補は、小さなコスト順の 3つだけ
  • 方針 A), B) どちらでも同じ答えになる。 B) の方が楽そう
• 考察3: 最小コストのループをどうやって求める？
  • 初手の移動先を「根」とする
  • 根が異なる最短経路が、最初につながったところが最小コストのループとなる
  • 茶・緑ノードは辿らないように
• 追加1: 最小コストのループから先に求める方法 (公式解説)
• 追加2: ひげをループから除かなくても良い (公式解説)

ABC308 Ex 実装例 (Rust)

ABC308-Ex-1.rs

use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::{input, marker::Usize1};

fn build_ungraph(n: usize, abc: &[(usize, usize, usize)]) -> Vec<Vec<(usize, usize)>> {
    let mut graph = vec![vec![]; n]; // node, (adjacent_node, cost)
    for &(a, b, c) in abc {
        graph[a].push((b, c));
        graph[b].push((a, c));
    }
    for i in 0..n {
        graph[i].sort_by_key(|x| x.1);
    }
    graph
}

fn find_shortest_loop(start: usize, q: usize, graph: &[Vec<(usize, usize)>]) -> usize {
    let mut queue = BinaryHeap::new();
    let mut v = vec![(0, start); graph.len()]; // total cost, second node
    for &(i, c) in &graph[start] {
        queue.push((Reverse(c), i, i)); // cost, node, second node
    }
    while let Some((Reverse(c), i, second)) = queue.pop() {
        if i == start || i == q {
            continue; // not loop
        }
        if v[i].0 > 0 {
            if v[i].1 == second {
                continue;
            }
            return v[i].0 + c; // loop
        }
        v[i] = (c, second);
        for &(i0, c0) in &graph[i] {
            queue.push((Reverse(c + c0), i0, second));
        }
    }

    std::usize::MAX
}

fn main() {
    input! {
        n: usize,
        m: usize,
        abc: [(Usize1, Usize1, usize); m],
    }
    let graph = build_ungraph(n, &abc);

    let mut result = std::usize::MAX;
    for i in 0..n {
        if graph[i].len() >= 3 {
            for j in 0..3 {
                let (q, c) = graph[i][j];
                let shortest = find_shortest_loop(i, q, &graph);
                if shortest != std::usize::MAX {
                    result = result.min(shortest + c);
                }
            }
        }
    }

    if result == std::usize::MAX {
        println!("{}", -1);
    } else {
        println!("{}", result);
    }
}

最後に

水色コーダーになったあたりから、F 問題からも手が届くことがあると言うか、難易度が E 問題までの延長上という感じがしてきました。使うテクニックはあまり変わらなくて、どちらかというと早解きや正確さが求められる感じです。

しかし公式解説を見ると、難しい問題ほど分かっている人に前提がスキップされたものになりがちだと思っています。解説 AC しようとしたときに、推奨レベル前の方には実際以上に難しく感じることもあるかもしれない、と。

そこで、私なら視覚的に流れがイメージできるようにしたい、として描いてみました。 kyopro_friends さんの Twitter 内簡易解説よりもう少し実装寄り、くらいの。本記事の公開はコンテストからだいぶ経っていますが、どなたかの精進のお役に立てば幸いです。

ところで ABC の公式解説を載せられるの資格があるのは黄色コーダー以上のようで。興味があってもまったく手が届く気がしません。しばらくこのまま、興味の出た問題を非公式で描いてみる感じになりそうです。