ABC263 を Rust で解く (C問題まで)

はじめに

AtCoder Beginner Contest 263 の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。

なぜやるのか

プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)

問題

A - Full House (Difficulty 27)
B - Ancestor (Difficulty 136)
C - Monotonically Increasing (Difficulty 298)
D - Left Right Operation (Difficulty 1016)
E - Sugoroku 3 (Difficulty 1659)
F - Tournament (Difficulty 2066)
G - Erasing Prime Pairs (Difficulty 2261)
Ex - Intersection 2 (Difficulty 3041)

前提

この記事にあるコードはこちらを import しています。

#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars, marker::Usize1};
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BTreeSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use itertools::Itertools;

A - Full House

ポーカーのフルハウスを判定する問題ですね。

やりかたはいろいろありますが、それぞれの数字が出た回数を調べる方法が思いつきやすいでしょうか。これは Vec や HashMap を使って判定できます。
もしくは、値をソートした後の状態を調べる方法があります。この方法は記述量が少なく、シンプルなコードになります。以下に紹介します。

フルハウスとなる手札をソートすると、a a a b b または a a b b b となりますね。それ以外にはなりません。そのため、この2パターンを判定すれば答えがわかります。

コードは以下のようになります。

  input! {
    mut v: [usize; 5]
  }
  v.sort();
  if (v[0] == v[1] && v[2] == v[4]) || (v[0] == v[2] && v[3] == v[4] ) {
    println!("Yes");
  }
  else {
    println!("No");
  }

B - Ancestor

親と子の関係が与えられて、子から親をたどる問題ですね。

考察

問題状況がイメージしにくいかもしれませんが、イメージしにくいときは、親と子の間に線を引いた図を書いてみましょう。すると、「$N$ から $1$ までたどるときに何本の線を通るか」という問題になります。

このような図をイメージしています

入力例 1 だと、 3 から 1 までの線の本数は 2 本ですね。
ちなみに、このような図を「グラフ」と言います。グラフの問題は AtCoder でよく出題されるので、慣れることをオススメします。

実装

実装で難しいのは、子から親をたどることでしょうか。
これは、いまいる場所を now として p[now] でたどることができます。あとは、now = p[now] として移動していき、その移動回数を数えれば答えになります。

コードは以下のようになります。

  input! {
    n: usize,
    p: [Usize1; n - 1]
  }

  let mut ans = 0;
  let mut now = n - 1;
  while now != 0 {
    // p のサイズが n-1 のために 1 ずれているので、1 を引いて調整する
    now = p[now - 1];
    ans += 1;
  }
  println!("{}", ans);

C - Monotonically Increasing

条件に合う文字列を列挙する問題ですね。

考察

問題文が複雑ですね。言い換えると、「$1 \sim M$ の数字をひとつづつ用意して、 $N$ 個選んで並べたときに、辞書順で昇順になるものを列挙する」という問題です。

$1 \le M \le 10$ より、 $1 \sim M$ の数字を並べたものは $10! = 3628800 \fallingdotseq 3.6 * 10^6$ 通りあります。これは全列挙しても時間内に終えられる量です。

また、今回は再帰関数が有効です。というのも、重複部分が多くて全列挙ができるためです。今回は文字列を構築する問題なので、 Vec に要素を追加しながら再帰します。

再帰関数は遷移条件と終了条件をかけば動きます。
今回は、遷移条件が「配列の最後尾よりも大きい数値を追加する」ことで、終了条件が「配列のサイズが $N$ になる」ことです。条件に満たないときは次への遷移をしないようにしましょう。

実装

ans を参照で渡して、条件に合う文字列をみつけたら要素を追加するようにしています。ans の所有権に苦戦しました。
dfs(...) 内で書いている for の範囲を back + 1..=m とすることで、辞書順で昇順になるように next に要素が追加されていきます。つまり、最後にソートをしなくても昇順になります。キレイです。

コードは以下のようになります。
出力部分で 2重ループを書いて 1要素ごとに出力するのがイヤだったので、Vec<String> に変換してから join(" ") を使っています。

fn main() {
  input! {
    n: usize,
    m: usize
  }
 
  let mut ans: Vec<Vec<usize>> = vec![vec![]];
  dfs(n, m, vec![], &mut ans);
 
  for vec in ans.into_iter() {
    let v = vec.into_iter().map(|c| c.to_string()).collect_vec();
    println!("{}", v.join(" "));
  }
}
 
fn dfs(n: usize, m: usize, now: Vec<usize>, ans: &mut Vec<Vec<usize>>) {
  if now.len() == n {
    // 答えとして保存する
    (*ans).push(now);
    return;
  }
 
  // 最後尾 + 1 ~ M を追加する
  // 最後尾が M 以上のときは for が実行されないので再帰もされない
  let back = now.last().unwrap_or(&0);
  for v in back + 1..=m {
    let mut next = now.clone();
    next.push(v);
    dfs(n, m, next, ans);
  }
}

おまけ

社内のエンジニアに聞いたところ、これでいけるといただきました。
combinations は今回の問題で求めるものをそのまま出力するので、このようにシンプルに書けます。

  input! {
    n: usize,
    m: usize,
  }
  for perm in (1..=m).combinations(n) {
    let a: Vec<String> = perm.iter().map(|x| x.to_string()).collect();
    println!("{}", a.join(" "));
  }

---

最後まで読んでいただきありがとうございます！