AtCoder ABC232 A-E Rust

AtCoder ABC232 A-E

Rustで解いたときのメモなど

atcoder.jp

github.com

A - QQ solver

文字列をパースして掛け算する問題.
入力として受け取る型がStringとVec<char>とで後の処理方法が変わる.
Vec<char>なら文字xに対してx as u8 - b'0'で数値化.

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

#[allow(non_snake_case)]
#[fastout]
fn main() {
    input! {
      S: Chars,
    }

    let a = S[0] as u8 - b'0';
    let b = S[2] as u8 - b'0';
    let ans = a * b;
    println!("{}", ans);
}

B - Caesar Cipher

文字列Sをシフトしたとき文字列Tと一致するかどうかを判定する.
文字列Sと文字列Tの先頭の文字のシフト量を計算して, 他の文字のペアのシフト量がすべて先頭のものと一致しているかを判定することで解いた.

文字列S, 文字列Tのiterをzipしてすべての文字が条件を満たすかallで判定.

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

const YES: &str = "Yes";
const NO: &str = "No";

#[allow(non_snake_case)]
#[fastout]
fn main() {
    input! {
      S: Chars,
      T: Chars
    }
    let S: Vec<_> = S.iter().map(|&x| x as i32).collect();
    let T: Vec<_> = T.iter().map(|&x| x as i32).collect();

    let d = (S[0] - T[0] + 26) % 26;

    let ans = if S
        .iter()
        .zip(T.iter())
        .all(|(&x, &y)| (y + d) % 26 == x % 26)
    {
        YES
    } else {
        NO
    };

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

C - Graph Isomorphism

与えられた2つのグラフ構造が一致しているか判定する問題.
判定方法が問題文に与えられているので, 単純にこれを実装する.

rustで順列を作成するならitertoolsのpermutationsを使う.

順列作成で, すべてのリンクに対する判定でなので, 全体でで間に合うっぽい.

use itertools::Itertools;
use proconio::{fastout, input, marker::Usize1};
use std::collections::HashSet;

const YES: &str = "Yes";
const NO: &str = "No";
use std::cmp::{max, min};

#[allow(non_snake_case)]
#[fastout]
fn main() {
    input! {
        N: usize,
        M: usize,
        AB: [(Usize1, Usize1); M],
        CD: [(Usize1, Usize1); M]
    }
    let CD: HashSet<_> = CD.iter().collect();

    for P in (0..N).permutations(N) {
        let mut f = true;
        for &(a, b) in AB.iter() {
            let c = min(P[a], P[b]);
            let d = max(P[a], P[b]);

            if !CD.contains(&(c, d)) {
                f = false;
                break;
            }
        }
        if f {
            println!("{}", YES);
            return;
        }
    }
    println!("{}", NO);
}

D - Weak Takahashi

マスのグリッド上の右か下に移動可能なとき, 左上を始点としたときの最長経路長を求める問題.
右か下にしか移動できないので, 始点から移動可能なマスまでに踏むマスの数は一意に定まるので,幅優先で全探索して最大長を出力.

use proconio::{fastout, input, marker::Chars};
use std::cmp::max;
use std::collections::HashSet;
use std::collections::VecDeque;

#[allow(non_snake_case)]
#[fastout]
fn main() {
    input! {
      H: usize,
      W: usize,
      C: [Chars; H]
    }

    let mut q = VecDeque::new();
    q.push_back((0, 0, 1));
    let mut v = HashSet::new();
    v.insert((0, 0));
    let mut ans = 0;
    while let Some((x, y, z)) = q.pop_front() {
        ans = max(ans, z);
        if y + 1 < H && C[y + 1][x] == '.' && !v.contains(&(x, y + 1)) {
            v.insert((x, y + 1));
            q.push_back((x, y + 1, z + 1));
        }
        if x + 1 < W && C[y][x + 1] == '.' && !v.contains(&(x + 1, y)) {
            v.insert((x + 1, y));
            q.push_back((x + 1, y, z + 1));
        }
    }

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

E - Rook Path

ルークの移動を数え上げる問題. dpで解く. dpは以下のとおりに定義.

グループとは下記の画像の通り

• 0(グループA): 終了マス
• 1(グループB): 終了マスと同じ行
• 2(グループC): 終了マスと同じ列
• 3(グループD): それ以外

なのでdpの遷移は以下の通り

• A: B,Cからの移動のみ
• B: AからのBの各列へ移動, BからBの他の列への移動, Dからの移動
• C: AからのCの各行へ移動, CからCの他の行への移動, Dからの移動
• D: BからDの各行への移動, CからDの各列への移動, DからDの他の行と列への移動

最終的な解答は dp[K, 0].

遷移の条件を時間以内にまとめられませんでした...

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

const M: usize = 998244353;

#[allow(non_snake_case)]
#[fastout]
fn main() {
    input! {
        H: usize,
        W: usize,
        K: usize,
        x1: Usize1,
        y1: Usize1,
        x2: Usize1,
        y2: Usize1,
    }
    let mut dp = vec![vec![0; 4]; K + 1];
    let i = if x1 == x2 && y1 == y2 {
        0
    } else if x1 == x2 {
        1
    } else if y1 == y2 {
        2
    } else {
        3
    };
    dp[0][i] = 1;

    for k in 1..=K {
        dp[k][0] = (dp[k - 1][1] + dp[k - 1][2]) % M;
        dp[k][1] = (((W - 1) * dp[k - 1][0]) % M + dp[k - 1][3] + ((W - 2) * dp[k - 1][1]) % M) % M;
        dp[k][2] = (((H - 1) * dp[k - 1][0]) % M + dp[k - 1][3] + ((H - 2) * dp[k - 1][2]) % M) % M;
        dp[k][3] = (((W - 1) * dp[k - 1][2]) % M
            + ((H - 1) * dp[k - 1][1]) % M
            + ((W + H - 4) * dp[k - 1][3]) % M)
            % M;
    }

    println!("{}", dp[K][0]);
}