4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@bfs

【Rust】ABC422まとめ（A~E）

4
Last updated at Posted at 2025-09-09

AtCoder Beginner Contest 422

35分ほど遅れてunrated参加し、A~Dの4完（89分6ペナ）でした。
今回はA~Eまでをまとめていきます。

A - Stage Clear

$S$は8-8ではないという条件から、$S$の分岐は大きく

  • $1 \le i \le 8, \ 1 \le j \le 7$ のとき、i-(j+1)を出力
  • $1 \le i \le 7, \ j = 8$のとき、(i+1)-1を出力

の2パターンに限定されます。

use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        s: Chars,
    }

    let mut s_arr = s.iter().map(|c| *c as isize - '0' as isize).collect::<Vec<isize>>();
    if s_arr[2] == 8 {
        s_arr[0] += 1;
        s_arr[2] = 1;
    }else {
        s_arr[2] += 1;
    }
    println!("{}-{}", s_arr[0], s_arr[2]);
}

B - Looped Rope

$H, W \le 20$より、マス目数は最大で$400$マス、各マスについて上下左右の$4$パターンを参照するとしても最大$1600$回の計算量となります。
したがって、マス目を一つずつ見て#（黒）マスの場合に上下左右の#マスを数え、$2$個か$4$個以外のマスが一つでもあればNo、なければYesを出力するという全探索の解法で十分高速に解くことができます。

注意点としては、上下左右の#マスが$0$個の場合はNGとなります。
私は単純に偶奇で判定しようとして$0$個の場合を忘れていたので1ペナ食らいました。

use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        h: isize,
        w: isize,
        s: [Chars; h],
    }
    
    let mut ans = true;
    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];
    for i in 0..h {
        for j in 0..w {
            if s[i as usize][j as usize] == '#' {
                let mut cnt = 0;
                for k in 0..4 {
                    let ni = i + dx[k];
                    let nj = j + dy[k];
                    if ni >= 0 && ni < h && nj >= 0 && nj < w && s[ni as usize][nj as usize] == '#' {
                        cnt += 1;
                    }
                }
                if cnt % 2 != 0 || cnt == 0 {
                    ans = false;
                }
            }
        }
    }
    if ans {
        println!("Yes");
    } else {
        println!("No");
    }
}

C - AtCoder AAC Contest

AXC(XにはA,B,Cのいずれかが入る)という文字列をできる限り多く作る必要がありますが、注目すべき点はAとCを必ず一つ以上使わなければならないことです。

したがって、AXC開催数の上限としては$\min (n_A, n_C)$（$n_A$の個数と$n_C$の個数のうち小さい方）となることが考えられます。

▼図1）AXC開催数上限が$\min (n_A, n_C)$となるケース
Group 53 (1).png

一方で、$n_A$や$n_C$に比べ、$n_B$が非常に小さい場合はその限りではありません。
AXCのXにはA,B,Cをどれでも入れることができますが、Bが少ない時はAとCをBと同じように見做して$n_A$や$n_C$を実質的に減らす必要があるからです。

▼図2）AXC開催数上限が$\min (n_A, n_C)$よりも小さくなるケース
Group 54 (1).png

ここで、この問題を解くために残された課題は以下の二つです。

  • AXC開催数上限が$\min (n_A, n_C)$となるか、それ未満となるかの分岐条件は何か
  • AXC開催数上限が$\min (n_A, n_C)$未満となる場合、具体的な値は何か

一つ目の課題について考えましょう。
これは、$\min (n_A, n_C)$個のAXC文字列を作れるかどうかをプログラム上で判定すればよいです。
具体的には、AとCをそれぞれ$\min (n_A, n_C)$個使うと手元には合計で$\text{rest} = n_A+n_B+n_C - 2 \times \min (n_A, n_C)$個の文字が残りますが、この残り分はすべてXとして利用できるため、$\text{rest} \ge \min (n_A, n_C)$ならば$\min (n_A, n_C)$個のAXC文字列を作れることが言え、かつ答えの上限でもあるためこれを出力すれば良いです。

一方で、$\min (n_A, n_C)$個以上のAXC文字列を作れないとき、すなわち$\text{rest} < \min (n_A, n_C)$のときはどうなのかが二つ目の課題です。
ここで、AXCのXにはBの他にA,Cを入れることができるという点に着目しましょう。
その上で、改めて前の図2を見てください。AXCの開催数を最大化するためには、$n_A,n_B,n_C$の個数を均すようにA,CをXの位置に配置すれば良いことが図より明らかです。
つまり、A,B,Cの個数の平均値の小数点以下を切り捨てた$\lfloor {(n_A+n_B+n_C)/3} \rfloor$がAXC開催数の上限となるのでこれを出力します。

以上で二つの課題が解けたことによりこの問題をほとんど解けたも同然です。
各テストケース$n_A, n_B, n_C$を受け取り、次のように分岐処理を行えばよいです。
なお、計算量は$O(T)$となり十分高速です。

  • $\text{rest} \ge \min (n_A, n_C)$のとき、$\min (n_A, n_C)$を出力する
  • $\text{rest} < \min (n_A, n_C)$のとき、$\lfloor {(n_A+n_B+n_C)/3} \rfloor$を出力する

余談ですが、$\text{rest} < \min (n_A, n_C)$であることと$\lfloor {(n_A+n_B+n_C)/3} \rfloor < \min (n_A, n_C)$であることは同値なので、ものすごく理解力の高い方は初めから公式解説の通りに$\min (n_A, n_C, \lfloor {(n_A+n_B+n_C)/3} \rfloor)$を出力しても良いです。

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

fn main() {
    input! {
        t: usize,
        test_cases: [(isize, isize, isize); t],
    }

    let mut ans = vec![];
    for (a, b, c) in test_cases.into_iter() {
        let sum = a + b + c;
        let min = a.min(c);
        let rest = sum - 2 * min;
        if rest >= min {
            ans.push(min);
        } else {
            ans.push(sum / 3);
        }
    }
    println!("{}", ans.iter().join("\n"));
}

D - Least Unbalanced

$K$を$N$回にわたり$X$が最小となるように二分割するという再帰構造が見えたので、ABC413-Eの類題だと思ってdfs(深さ優先探索)で解きました。

たとえば、問題ページの$N=2, K=22$の例として$A=[6,8,3,5]$がアンバランスさ$6$となることが例示されていますが、$A'=[5,6,5,6]$とすればアンバランスさ$1$を実現することができます。
この$A'$を求める手順ですが、配列を半分にする操作を逆から見て、$[22]→[11,11]→[5,6,5,6]$のように構築しています。
具体的なロジックとしては、各要素$x$を二分割する際に、$\lfloor x/2 \rfloor$と$x-\lfloor x/2 \rfloor$に分けることで分割後の差がなるべく出ないようにします。

以上、お分かりの方もいると思いますが、差が最小となるように貪欲に二分割するので厳密にはdfsではなくただのfor文で解けます。というかdfsを使うのは考え方として少しおかしいのですが、どちらでも正解はできるので今回は両方掲載しておきます。

// 深さ優先探索で解く場合（考え方としては少しおかしい）
use proconio::input;
use itertools::Itertools;

fn main() {
    input! {
        n: usize,
        k: usize,
    }


    fn dfs(n: usize, depth: usize, ans: usize, cur: usize) -> (usize, Vec<usize>) {
        let n_min = cur / 2;
        let n_max = cur - n_min;
        let n_ans = ans.max(n_max - n_min);
        
        if depth == n - 1 {
            return (n_ans, vec![n_min, n_max]);
        }
        
        let (left_ans, left_arr) = dfs(n, depth + 1, n_ans, n_min);
        let (right_ans, right_arr) = dfs(n, depth + 1, n_ans, n_max);
        (left_ans.max(right_ans), [left_arr, right_arr].concat())
    }
    
    let (ans, ans_arr) = dfs(n, 0, 0, k);
    println!("{}", ans);
    println!("{}", ans_arr.iter().join(" "));
}

// for文で解く場合
use proconio::input;
use itertools::Itertools;

fn main() {
    input! {
        n: usize,
        k: usize,
    }

    let mut ans = 0;
    let mut ans_arr = vec![k];
    for _i in 0..n {
        let mut new_arr = vec![];
        for &cur in ans_arr.iter() {
            let n_min = cur / 2;
            let n_max = cur - n_min;
            ans = ans.max(n_max - n_min);
            new_arr.push(n_min);
            new_arr.push(n_max);
        }
        ans_arr = new_arr;
    }
    
    println!("{}", ans);
    println!("{}", ans_arr.iter().join(" "));
}

E - Colinear

$N$個の直線のうち、一つでも過半数の点を通る直線があればYes、なければNoを出力するということですが、適当に二点を選んでその二点を結ぶ直線上に過半数の点があるかどうかを$100$回くらい試せばまぐれ当たりが出そうな気がしませんか？

実際、過半数の点を通る直線がある時、その直線上にある二点を選ぶ確率は$1/4$以上あります。
同時に、そのような状況で$100$回二点を選ぶ試行を繰り返し、その直線上の二点を選ばない確率は$(3/4)^{100} ≒ 3.2\times 10^{-13}$となり十分に無視できるほど小さいです。

以上により、この問題は乱択アルゴリズムが十分な正当性を持ちます。
Rustでは乱数生成にrandという外部クレートを使うことができます。
JavaScriptのMath.random()と異なり、rand::thread_rngで初期化しておけばgen_range(a..b)で$a$以下$b$未満の整数を好きなタイミングで高速に生成することができ非常に便利です。

use proconio::input;
use rand::Rng;

fn main() {
    input! {
        n: usize,
        nodes: [(isize, isize); n],
    }

    let mut rng = rand::thread_rng();
    for _ in 0..100 {
        let idx1 = rng.gen_range(0..n);
        let idx2 = rng.gen_range(0..n);
        if idx1 == idx2 {
            continue;
        }
        let (x1, y1) = nodes[idx1];
        let (x2, y2) = nodes[idx2];
        let dx = x2 as isize - x1 as isize;
        let dy = y2 as isize - y1 as isize;
        let a = dy;
        let b = -dx;
        let c = -(a * x1 as isize + b * y1 as isize);
        let mut cnt = 0;
        for &(x, y) in &nodes {
            if a * x as isize + b * y as isize + c == 0 {
                cnt += 1;
            }
        }
        if cnt * 2 >= n {
            println!("Yes");
            println!("{} {} {}", a, b, c);
            return;
     }
    }
    println!("No");
}

まとめ

実質55分程度でA~Dを4完することができ、だんだんとRustを自在に書けるようになったことを実感しています。
次の課題としては、外部クレートやライブラリの存在や使い方を知り、もっと自由にRustを使いこなすことです。

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?