🏃

AtCoder ABC276(A-E)を深堀ってみた

2022/11/06に公開約15,600字

以下の記事の続編です。必要に応じて参考にしてください。

https://zenn.dev/tipstar0125/articles/4589f2d49b065f
https://zenn.dev/tipstar0125/articles/f9c4626cdd4d5b

ABC274, 275とコンテストに参加して、今回で3回目の参加になります。
目標は3完をミニマムとして、4完できればと思っていましたが、結果としては3完という結果に終わってしまいました。。。D問題は、コンテスト終了後3分後ぐらいに自力で解けたので、解くスピードがもっと必要だなと感じました。E問題に関しては、見た感じ解けそうだったので、コンテスト翌日解いてみたら、自力で解くことができました。

以下、A-Eの問題について深堀りをしてみたので、共有します。深堀りが浅い箇所もあるかと思いますが。。。
ネタバレになりますので、自分で解いてみたい人は以下で解いた後、読んで頂ければと思います。答えは見たくないけど、ちょっとヒントがほしい人向けに、ヒントを記載しました(A, B問題は基本問題で、ヒントの書きようがないので、無しで)。
https://atcoder.jp/contests/abc276

ヒント

  • A. ヒントなし
  • B. ヒントなし
  • C. 入出力例の違いをみて法則性を見つけてみましょう!
  • D. [2, 2, 2]を割りすぎて、[1, 1, 1]にしたらダメ!割りすぎないようにするには何を求める?
  • E. 道を頂点としたグラフの問題

A - Rightmost

文字列を左から順番に見ていき、aなら、そのindexを保存していけば良さそうです。見つからなかったら-1なので、初期値は-1として、保存するindexは1 indexedにする必要があるので、+1します。

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

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            S: Chars
        }

        let mut ans = -1_isize;
        for (i, &s) in S.iter().enumerate() {
            if s == 'a' {
                ans = i as isize + 1;
            }
        }
        println!("{}", ans);
    }
}

A問題なので、あまり深堀ようがないのですが、右から逆順に見ていって、見つかったら、そのindexを出力して、見つからなければ、-1を出力する、という方針が第1感の人もいるかと思います。enumerateしてからrevすれば、文字列もindexも逆順になるので便利です。

for (i, &s) in S.iter().enumerate().rev() {
    if s == 'a' {
        let ans = i as isize + 1;
        println!("{}", ans);
        return;
    }
}
println!("-1");

B - Adjacency List

グラフの基本問題ですね。競技プログラミングの鉄則のグラフの問題で一番最初に習う隣接リストを求める問題です。グラフの問題だと最初に隣接リストを作ってから、色々処理を書くので、基本にして重要な技術です。この問題は隣接リストを作成して、出力時に昇順にソートすれば良さそうです。Rustの場合、cloneしてからソートする必要があります。

use itertools::Itertools;
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            N:usize,
            M:usize,
            AB: [(usize, usize); M]
        }

        let mut G = vec![vec![]; N + 1];
        for &(a, b) in &AB {
            G[a].push(b);
            G[b].push(a);
        }

        for i in 1..=N {
            let mut gi = G[i].clone();
            gi.sort();
            println!("{} {}", gi.len(), gi.iter().join(" "))
        }
    }
}

Rustな書き方として、隣接リストにVecを使用するのではなく、昇順に並んだ集合BTreeSetを使用すると、ソートが自動でなされるので、そのまま出力することもできます。

use std::collections::BTreeSet;

let mut G = vec![BTreeSet::new(); N + 1];
for &(a, b) in &AB {
    G[a].insert(b);
    G[b].insert(a);
}

for i in 1..=N {
    println!("{} {}", G[i].len(), G[i].iter().join(" "))
}

C - Previous Permutation

問題の通り、1つ前の順列を求める問題です。
コンテスト中に、与えられている順列と1つ前の順列の違いの法則性を見つけるのに、まぁまぁ時間を要してしまいました。。。知っていたらそんなに難しくはないと思いますが、コンテスト中は「は??むずくね??」と思っていました。。。
法則ですが、以下の入出力例を参考に説明します。以下のポイントに気が付くと思います。

  • 前半の9 8 6 5 10までは 変わっていない
  • inputの後半1 2 4 7は昇順になっている
  • inputの後半の昇順になっている箇所の1つ前は、後半昇順の中で1つ小さい値に変わっている
  • outputの後半7 4 3 1は降順になっている
9 8 6 5 10 3 1 2 4 7 // input
9 8 6 5 10 2 7 4 3 1 // output

以上の法則をコードにすれば良いです。流れとしては以下の通り。

  1. 後ろから順番に数字を比較していき、昇順になっていないindexを探す。この例でいうと、3のindex5となります。
  2. index6以降の中で、3より1つ小さい値を探す。
  3. 上記で探した値と3をスワップします。
  4. スワップ後、index6以降を降順にソートします(スワップした状態でも昇順の状態を維持しているので反転すれば降順になります)。
use itertools::Itertools;
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            N: usize,
            mut P: [usize; N]
        }
        // 1.
        let mut j = N - 2;
        while P[j] < P[j + 1] {
            j -= 1;
        }
        // 2.
        let mut k = N - 1;
        while P[j] < P[k] {
            k -= 1;
        }
        // 3.
        P.swap(j, k);
        // 4.
        let mut Q = vec![0; P.len() - j - 1];
        Q.clone_from_slice(&P[j + 1..]);
        Q.reverse();
        println!("{} {}", &P[..j + 1].iter().join(" "), Q.iter().join(" "));
    }
}

以上ライブラリを知らない人のやり方です。prev_permutationを使用すと、簡単に書くことができます。また、1つ後という問題であった場合は、next_permutationというのもあるので、それを使用すれば良いだけです。prev_permutationを使用すると、元の順列が、1つ前の順列に変更されます(なので、mutとする必要がある)。戻り値は1つ前の順列があれば、trueで、なければfalseとなります(今回は1つ前の順列があることが保証されているので不要です)。

use itertools::Itertools;
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};
use superslice::Ext;

struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            N: usize,
            mut P: [usize; N]
        }

        P.prev_permutation();
        println!("{}", P.iter().join(" "));
    }
}

D - Divide by 2 or 3

この問題を最初みたとき、2 or 3で割り切れたら、割って、その回数をインクリメントし、最終的な値が全て等しければ、回数を出力、等しくなければ-1を出力すればいいんじゃね?と思って、意気揚々と以下のコードを書きました。結果WA。。。数分考えて、例えば、[2, 2, 2]が最終的な目標だとすると、[1, 1, 1]にして余計に3回割ったらダメだと気が付きました。

input! {
    N: usize,
    a: [usize; N]
}
let mut b = vec![];
let mut ans = 0;

for &ai in &a {
    let mut c = ai;
    while d % 2 == 0 {
        c /= 2;
        ans += 1;
    }
    while d % 3 == 0 {
        c /= 3;
        ans += 1;
    }
    b.push(c);
}

for i in 0..N - 1 {
    if b[i] != b[i + 1] {
        is_ok = false;
    }
}

if is_ok {
    println!("{}", ans);
} else {
    println!("-1");
}

では、どうするか。割るのは最大公約数までだな、と気づきました。ただ、コンテスト中は、3つ以上の数の最大公約数ってどうやって求めるの?と悩んで、1つずつやっていけばいいだけだよな、と思いながらも、自信が持てず、ググったりしていました。。。色々試行錯誤していたら、コンテスト終了し、その数分後にAC取れるという、苦い結果になりました。。。

let mut b = vec![];
let mut ans = 0;

let mut g = gcd(a[0], a[1]);
let mut is_ok = true;
for i in 2..N {
    g = gcd(g, a[i]);
}

for &ai in &a {
    let mut c = ai;
    let mut d = ai / g;
    while d % 2 == 0 {
        c /= 2;
        d /= 2;
        ans += 1;
    }
    while d % 3 == 0 {
        c /= 3;
        d /= 3;
        ans += 1;
    }
    b.push(c);
}

for i in 0..N - 1 {
    if b[i] != b[i + 1] {
        is_ok = false;
    }
}

if is_ok {
    println!("{}", ans);
} else {
    println!("-1");
}

上述の書き方は少し無駄があるので、リファクタリングします。

  • 最大公約数は初期値を0として、1つずつ順番に求めていく
  • 最大公約数で割って、その後2 or 3で割り続けて、最終的に1にならなければ、 全て等しくならないので、その時点で-1を出力して終了
let mut ans = 0;
let mut g = 0;
for i in 0..N {
    g = gcd(g, a[i]);
}

for &ai in &a {
    let mut c = ai / g;
    while c % 2 == 0 {
        c /= 2;
        ans += 1;
    }
    while c % 3 == 0 {
        c /= 3;
        ans += 1;
    }
    if c != 1 {
        println!("-1");
        return;
    }
}

println!("{}", ans);

E - Round Trip

迷路系の問題は、道をグラフの頂点と見なして、隣接リストを作成する、グラフの問題とみなせそうです。公式解答を見る限り、幅優先探索とかUnionFindとか色々な解答がありそうです。私は深さ優先探索で、再帰関数使えば、ちょっとかっこよくね?と思ったので、深さ優先探索で解いてみました。結果としては、1つRE(実行エラー)が出てしまいました。色々調査してみましたが、コードは問題なさそうだったので、REになっている箇所のメモリをみると一番大きい値だったので、再帰関数によるスタックオーバーフローだな思って、main関数内のstack sizeを増やしました。結果、ACゲットしました。結論として、私の解答はエラーのリスクが高いので、よくない解答かなと思いました。

コードの流れは以下の通りです。

  1. スタート位置の頂点を探索
  2. 'S' or '.'を頂点とする隣接リストを作成
  3. 再帰関数で深さ優先探索(既に訪れた頂点は探索しないように再帰メモを用意)
  4. 深さが1より大きくて、スタート地点に戻ってきたら、is_okをtrueにする
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            H: usize,
            W: usize,
            C: [Chars; H]
        }

        let mut G = vec![vec![]; H * W];
        let mut start = 0;
        // 1.
        for i in 0..H {
            for j in 0..W {
                if C[i][j] == 'S' {
                    start = i * W + j;
                }
            }
        }
        // 2.
        for i in 0..H {
            for j in 0..W - 1 {
                if (C[i][j] == '.' || C[i][j] == 'S') && (C[i][j + 1] == '.' || C[i][j + 1] == 'S')
                {
                    let index1 = i * W + j;
                    let index2 = i * W + j + 1;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
            }
        }
        for j in 0..W {
            for i in 0..H - 1 {
                if (C[i][j] == '.' || C[i][j] == 'S') && (C[i + 1][j] == '.' || C[i + 1][j] == 'S')
                {
                    let index1 = i * W + j;
                    let index2 = (i + 1) * W + j;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
            }
        }
        // 3.
        let mut visited = vec![false; H * W];
        let mut is_ok = false;
        dfs(start, &G, &mut visited, 0, start, &mut is_ok);

        if is_ok {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(128 * 1024 * 1024) // 64 * 1024 * 1024 だとRE
        .spawn(|| Solver::default().solve())
        .unwrap()
        .join()
        .unwrap();
}

fn dfs(
    pos: usize,
    G: &Vec<Vec<usize>>,
    visited: &mut Vec<bool>,
    depth: usize,
    end: usize,
    is_ok: &mut bool,
) {
    visited[pos] = true;
    for &next in &G[pos] {
        // 4.
        if next == end && depth > 1 {
            *is_ok = true;
        }
        if !visited[next] {
            dfs(next, G, visited, depth + 1, end, is_ok);
        }
    }
}

幅優先探索の解答例です。コードの流れは以下の通りです。

  1. スタート位置の頂点を探索
  2. 'S' or '.'を頂点とする隣接リストを作成
  3. スタート位置に隣接している頂点をキューに追加し、道の名前として異なる数字を割り振る(まだ訪れていない箇所は-1、スタートは0とするので、それ以外で設定)。
  4. キューがなくなるまで幅優先探索
  5. 訪れていない箇所は道の名前を保存、スタックに追加し、訪れている箇所で道の名前が異なる場合は閉路(ただし、スタートの0以外)
use std::collections::VecDeque;

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

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            H: usize,
            W: usize,
            C: [Chars; H]
        }

        let mut G = vec![vec![]; H * W];
        let mut start = 0;
        // 1.
        for i in 0..H {
            for j in 0..W {
                if C[i][j] == 'S' {
                    start = i * W + j;
                }
            }
        }
        // 2.
        for i in 0..H {
            for j in 0..W - 1 {
                if (C[i][j] == '.' || C[i][j] == 'S') && (C[i][j + 1] == '.' || C[i][j + 1] == 'S')
                {
                    let index1 = i * W + j;
                    let index2 = i * W + j + 1;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
            }
        }
        for j in 0..W {
            for i in 0..H - 1 {
                if (C[i][j] == '.' || C[i][j] == 'S') && (C[i + 1][j] == '.' || C[i + 1][j] == 'S')
                {
                    let index1 = i * W + j;
                    let index2 = (i + 1) * W + j;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
            }
        }

        let mut visited = vec![-1; H * W];
        let mut is_ok = false;
        let mut Q = VecDeque::new();
        // 3.
        visited[start] = 0;
        for (i, &x) in G[start].iter().enumerate() {
            visited[x] = i as isize + 1;
            Q.push_back(x);
        }
        // 4.
        while !Q.is_empty() {
            let pos = Q.pop_front().unwrap();
            for &n in &G[pos] {
                if visited[n] == -1 {
                    visited[n] = visited[pos];
                    Q.push_back(n);
                } else if visited[n] != 0 && visited[n] != visited[pos] { // 5.
                    is_ok = true;
                }
            }
        }

        if is_ok {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

UnionFindの解答例です。コードの流れは以下の通りです。

  1. '.'を頂点とする隣接リストとSに隣接している頂点のリストを作成
  2. Sに隣接している頂点のリストは重複して追加されているので、ユニークにする
  3. 隣接リストからUnionFindを作成
  4. Sに隣接している頂点の数が1以下ならば、閉路はできないので、その時点で終了。
  5. 隣接リストはSを除外しているので、Sに隣接している頂点が同じグループにいれば閉路。
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[derive(Debug, Clone)]
struct UnionFind {
    parent: Vec<isize>,
    size: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: vec![-1; n + 1],
            size: n,
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] < 0 {
            return x;
        }
        let root = self.find(self.parent[x] as usize);
        self.parent[x] = root as isize;
        root
    }

    fn unite(&mut self, x: usize, y: usize) {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x == root_y {
            return;
        }
        let size_x = -self.parent[root_x];
        let size_y = -self.parent[root_y];
        if size_x >= size_y {
            self.parent[root_x] -= size_y;
            self.parent[root_y] = root_x as isize;
        } else {
            self.parent[root_y] -= size_x;
            self.parent[root_x] = root_y as isize;
        }
        self.size -= 1;
    }

    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    fn is_root(&mut self, x: usize) -> bool {
        self.find(x) == x
    }

    fn get_union_size(&mut self, x: usize) -> usize {
        let root = self.find(x);
        -self.parent[root] as usize
    }

    fn get_size(&self) -> usize {
        self.size
    }
}

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            H: usize,
            W: usize,
            C: [Chars; H]
        }

        let mut G = vec![vec![]; H * W];
        let mut start_adjacency = vec![];
        // 1.
        for i in 0..H {
            for j in 0..W - 1 {
                if C[i][j] == '.' && C[i][j + 1] == '.' {
                    let index1 = i * W + j;
                    let index2 = i * W + j + 1;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
                if C[i][j] == '.' && C[i][j + 1] == 'S' {
                    start_adjacency.push(i * W + j);
                }
                if C[i][j] == 'S' && C[i][j + 1] == '.' {
                    start_adjacency.push(i * W + j + 1);
                }
            }
        }
        for j in 0..W {
            for i in 0..H - 1 {
                if C[i][j] == '.' && C[i + 1][j] == '.' {
                    let index1 = i * W + j;
                    let index2 = (i + 1) * W + j;
                    G[index1].push(index2);
                    G[index2].push(index1);
                }
                if C[i][j] == '.' && C[i + 1][j] == 'S' {
                    start_adjacency.push(i * W + j);
                }
                if C[i][j] == 'S' && C[i + 1][j] == '.' {
                    start_adjacency.push((i + 1) * W + j);
                }
            }
        }
        // 2.
        start_adjacency.dedup();
        // 3.
        let mut uf = UnionFind::new(H * W);
        for i in 0..H * W {
            for &x in &G[i] {
                uf.unite(i, x);
            }
        }
        // 4.
        if start_adjacency.len() < 2 {
            println!("No");
            return;
        }
        // 5.
        let mut is_ok = false;
        for i in 0..start_adjacency.len() {
            for j in i + 1..start_adjacency.len() {
                if uf.is_same(start_adjacency[i], start_adjacency[j]) {
                    is_ok = true;
                }
            }
        }
        
        if is_ok {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

まとめ

今回目標にしていた4完は達成できませんでしたが、色々学びがあり非常に良い経験になりました。
実際の解答は以下のGithubを参照ください。

https://github.com/TatsuyaYoke/atcoder/tree/master/abc276

GitHubで編集を提案

Discussion

ログインするとコメントできます