【AtCoder 緑色を目指して】ABC374 Rust バーチャル参加【競技プログラミング】

技術ブログ 競技プログラミング

はじめに

こんにちは、駒嶺です。

Rustの勉強のためにAtCoder Beginner Contest 374をRustで解きました。今回はバーチャル参加です。

A – Takahashi san 2

与えられた文字列の最後にsanがついているか判定します。

use proconio::input;

fn main() {
    input!{
        s: String
    }
    println!("{}", if s.ends_with("san"){"Yes"}else{"No"})
}

ends_withで一発ですね。

B – Unvarnished Report

文字列SとTが等しいか判定し、異なる場合は何文字目で異なるのかを示します。

解答

use proconio::{input, marker::Chars};
use itertools::{Itertools, EitherOrBoth::*};

fn main() {
    input! {
        s: Chars,
        t: Chars
    }
    if s == t {println!("0");return;}
    for (i, pair) in s.into_iter().zip_longest(t).enumerate(){
        match pair {
            Both(si, ti) => if si != ti {println!("{}", i + 1);return;},
            _ => {println!("{}", i + 1);return;}
        }
    }
}

SとTの二つのイテレーターをzip_longestを使ってまとめて1文字ずつ一致しているか確認しました。
iter_a.zip(iter_b)とすると(a, b)とそれぞれの値が入ったタプルのイテレーターに変換できます。
普通のzipだとイテレーターの長さが違う場合短い方に合わせるので、今回はzip_longestを使用しています。

C – Separated Lunch

できるだけ1つのグループが大きくならないようにN個の部署（部署iの人数はKi人）をグループA、Bに分けます。
Nは最大20です。

解答

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut k: [i64; n]
    }
    k.sort();

    let sum_all: i64 = k.iter().sum();
    let mut ans = sum_all;
    for bit in 0..(1 << n){
        let sum_sub: i64 = (0..n).filter(|x| (bit & (1 << x) != 0)).map(|x| k[x]).sum();
        ans = ans.min(sum_sub.max(sum_all - sum_sub))
    }
    println!("{}", ans);
}

Nが最大20と小さいのでbit全探索します。
bit全探索とは2^n乗の組み合わせをn桁の2進数で表してループを回し全探索する方法です。
今回の場合はN=4なら0000の時は全部署がグループB、1010なら部署4と部署2はグループA、それ以外はグループBといった具合です。

D – Laser Marking

レーザー印字するときの最適な経路を求めます。
線分((X1, Y1), (X2, Y2))がN個与えられます。
座標（0, 0）の初期位置からすべての線分を通るときの最短時間を求めます。
ただし、線分の中を移動するときは1秒あたり速度S、線分外を移動するときは1秒あたり速度Tで移動します。
Ｎは最大6です。

解答

use proconio::input;
use itertools::Itertools;
use std::mem::swap;

fn main() {
    input! {
        n: usize,
        s: f64,
        t: f64,
        lines: [((i64, i64), (i64, i64)); n]
    }
    let mut ans: f64 = std::f64::MAX;
    for perm in (0..n).permutations(n){
        for bit in 0..(1 << n){
            let mut current = (0, 0);
            let mut time = 0.0;
            for (i, (mut ab, mut cd)) in perm.iter().map(|x| lines[*x]).enumerate(){
                if bit & (1 << i) != 0{
                    swap(&mut ab, &mut cd);
                }
                time += dist(&current, &ab) / s + dist(&ab, &cd) / t;
                current = cd;
            }
            ans = ans.min(time);
        }
    }
    println!("{}", ans);
}

fn dist(p1: &(i64, i64), p2: &(i64, i64)) -> f64{
    (((p1.0 - p2.0).pow(2) + (p1.1 - p2.1).pow(2)) as f64).sqrt()
}

Nが最大6と小さいので全探索します。
線分をたどる順番はN!通りで、これはItertoolsのpermutationsを使うと簡単に表せます。
13行目 (0..n).permutations(n)はnPnの並び順すべての配列を返すイテレーターを生成します。

さらに線分をどちら向きに通るかで2^N通りの組み合わせがあるのでbit全探索をしています。
合計でN!×2^N通りですね。

D問題は制限時間内に間に合いませんでした。
19行目で線分の向きを入れ替えるためにswap()しています。
最初は線分をタプルのタプル((a,b), (c, d))ではなく一つの配列[a, b, c, d]で持っていたので所有権などの問題で上手くいかず苦労しました。
しかし結果としてswap()を使用するために座標を一つのタプルで表したことで分かりやすいコードになったので満足です。（競技的にはダメですが…）

コンテスト結果

今回はバーチャル参加なのでレート変動は無しです。パフォーマンスは417でした。

C問題まではすんなりと解けたのでこれならRustでレート参加しても大丈夫そうです。

おわりに

本ブログを通じて私と一緒に競技プログラミングの世界を楽しんでいただければ幸いです。
また、各種ご支援させていただきますので、お気軽に「お問い合わせフォーム」よりお問い合わせください。

お問い合わせ
業務実績

関連記事