paizaxQiitaコラボキャンペーン対象問題全部抜く Bランク編

はじめに

paizaxQiitaコラボキャンペーンに参加して、対象問題をすべて解いてみました。
言語は全問題Rustで記述しました。

標準入力からの受け取りについて

Rustは標準入力の受け取りがめんどくさいと巷でよく言われています。
普段自分が遊んでいる競技プログラミングサイトではproconioという偉大なるクレートを用いることができるためここら辺はストレスフリーなのですが、
残念ながらpaizaでは導入されていなかったため、proconioのソースから必要な一部分を拝借・修正して入力できるようにしています。(最小限のものだけとってきてるので簡易版です)

入力箇所のinputマクロは以下に記載しますが、問題の本質とはズレるので解答コードからは省略しています。

#!/usr/bin/env rust-script

use std::{collections::HashMap, io::Read};

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

3Dプリンタ

私の解答

3次元配列、上から見るか、横から見るかみたいな問題です。
yz平面から眺めたときにどう見えるかみたいなことですね。
入力の制約は

・ 1 ≦ X ≦ 50
・ 1 ≦ Y ≦ 50
・ 1 ≦ Z ≦ 50

と小さいので、何やっても計算量的には大丈夫そうです。
そこで各zに対して、
敷き詰められたタイルがxyの順で格納されているのをtransposeという関数で配列の転置をして、yxの順番にしています。
こうしてしまえばあとは簡単で、
各yに#があるかどうかを判定すればよいだけですね。

ちなみに入力で使用しているproconioもどきは最小限すぎてこの問題のちょっと複雑な入力の取り方にだいぶ苦戦しました。。
あとはなぜか各入力の区切りに---という文字列が入るようになっていて、これは完全にpaizaさんの嫌がらせだと思いましたw

fn transpose<T: Clone + Copy + Default>(matrix: Vec<Vec<T>>) -> Vec<Vec<T>> {
    if matrix.is_empty() {
        return Vec::new();
    }

    let rows = matrix.len();
    let cols = matrix[0].len();

    let mut transposed = vec![vec![T::default(); rows]; cols];

    for i in 0..rows {
        for j in 0..cols {
            transposed[j][i] = matrix[i][j];
        }
    }

    transposed
}

fn main() {
    input! {
        x: usize,
        y: usize,
        z: usize,
        s: [[String; x + 1]; z]
    }
    let mut a = vec![];
    for row in s.iter() {
        let mut v = vec![];
        for word in row.iter() {
            v.push(word.chars().collect::<Vec<char>>());
        }
        v.pop();
        a.push(v);
    }
    let mut ans = vec![];
    for i in 0..a.len() {
        let mut v = vec![];
        let trans_a = transpose(a[i].clone());
        for j in 0..trans_a.len() {
            if trans_a[j].contains(&'#') {
                v.push('#');
            } else {
                v.push('.');
            }
        }
        ans.push(v);
    }
    ans.reverse();
    for row in ans.iter() {
        let w = row.iter().collect::<String>();
        println!("{}", w);
    }
}

神経衰弱

私の解答

入力でとった情報をシミュレーションしてあげればよいです。
人nの後は人1に戻ってくるので、順番が進むときには"今、誰の番か？"を管理している変数nowに対してnであまりをとっています。

fn main() {
    input! {
        h: usize,
        w: usize,
        n: usize,
        t: [[usize; w]; h],
        l: usize,
        abab: [(usize, usize, usize, usize); l]
    }

    let mut ans = vec![0; n];
    let mut now = 0;

    for &(a1, b1, a2, b2) in abab.iter() {
        let num1 = t[a1 - 1][b1 - 1];
        let num2 = t[a2 - 1][b2 - 1];

        if num1 != num2 {
            now += 1;
            now %= n;
            continue;
        }

        ans[now] += 2usize;
    }

    for &num in ans.iter() {
        println!("{}", num);
    }
}

みんなでしりとり

私の解答

これもシミュレーション問題ですね。
O(N)くらいで実装するモチベーションが途中で折れてplayersをベクタで管理してremoveしてるのでO(N^2)解ですが制約緩いので通ります。
"先頭のcharが前の言葉の最後のcharと一致しているか？ただし前の人がミスってたらその制約はナシ！"という条件を実装するのを忘れてて、とってつけたように実装しています。
その人がスタートするべきcharを管理する変数startに対して、前の人がミスってたら次の人の最初の文字をstartにいれてあげてます。なんかずるい気がしますがこれでいい気もします。

fn main() {
    input! {
        n: usize,
        k: usize,
        m: usize,
        d: [String; k],
        s: [String; m]
    }

    let mut db = d.into_iter().collect::<HashSet<String>>();
    let mut ss = vec![];
    for word in s.iter() {
        let chars = word.chars().collect::<Vec<char>>();
        ss.push(chars);
    }
    let mut start = ss[0][0];
    let mut players = (0..n).collect::<Vec<usize>>();
    let mut player = 0;
    for (idx, s_v) in ss.iter().enumerate() {
        if s_v[0] != start {
            players.remove(player);
            if idx + 1 < m {
                start = ss[idx + 1][0];
            }
            continue;
        }
        if *s_v.last().unwrap() == 'z' {
            players.remove(player);
            if idx + 1 < m {
                start = ss[idx + 1][0];
            }
            continue;
        }
        let word = s_v.iter().collect::<String>();
        if !db.contains(&word) {
            players.remove(player);
            if idx + 1 < m {
                start = ss[idx + 1][0];
            }
            continue;
        }
        db.remove(&word);
        player += 1;
        player %= players.len();
        start = *s_v.last().unwrap();
    }
    println!("{}", players.len());
    for &num in players.iter() {
        println!("{}", num + 1);
    }
}

長テーブルのうなぎ屋

私の解答

入力された順番にお客さんが来てくれるらしいので、
前から順番に処理していけば解けます。
椅子iに座っている人がいるかどうかを管理するtableを更新していきます。
また、椅子nのとなりは椅子1になるので、忘れずにMODをとってあげましょう。

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

    let mut table = vec![false; n];
    for &(a, b) in ab.iter() {
        let start = b - 1;
        let mut flg = true;
        for i in 0..a {
            if table[(start + i) % n] {
                flg = false;
                break;
            }
        }
        if flg {
            for i in 0..a {
                table[(start + i) % n] = true;
            }
        }
    }
    let ans = table.iter().filter(|&&e| e).count();
    println!("{}", ans);
}

名刺バインダー管理

私の解答

算数の問題です。なんか中学入試とかで出されそう。

ポケットの番号をすべて-1すると、
見開きをみたときに左側のページには n(mod 2n) ~ 2n -1(mod 2n)の数字が、
右側のページには0(mod 2n) ~ n - 1(mod 2n)の数字が格納されているのがわかるので、見通しがよくなります。
mを2nであまりをとったときにその値がnより大きければ裏側の数字はmより小さい値になり、小さければ裏側の数字はmより大きい値がはいっていることがわかります。

ここまでわかれば進むべき方向がわかるのであとはdiff分だけ進んだ値を計算して出力すればよいです！

fn main() {
    input! {
        n: isize,
        m: isize,
    }
    let mut m = m;
    m -= 1;
    let idx = m % (2 * n);
    if idx >= n {
        let target = idx - n + 1;
        let ans = m - 2 * target + 1;
        println!("{}", ans + 1);
    } else {
        let ans = m + 2 * (n - idx - 1) + 1;
        println!("{}", ans + 1);
    }
}

まとめ・感想

この記事ではpaizaxQiitaコラボキャンペーン対象問題のBランク相当の問題5問を解きました。
必要な知識量としてはCランク相当の問題と同等の知識で解けますが、ある程度の実装力も求められるようになってきました！

他のランクの問題も記事があるので併せて読んでいただけると嬉しいです！