競プロ

AtCoder Buginner Contest 398 参加記

 

AtCoder Beginner Contest 398に参加しました。

前回から連続して青perfが出ました。嬉しいです。青が近くてコンテストに緊張しながら出るようになってしまいました。3月中に決着をつけたい。。。。

問題の解き方

A. Doors in the center

全てが – の配列の \(\lfloor \frac{n}{2} \rfloor\) と \(\lfloor \frac{n – 1}{2} \rfloor\) 番目を = に変える問題です。奇数長のときはこの二つが一致するのでうまく真ん中だけが変換されます。

use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    let mut ans = vec!['-'; n];
    ans[n / 2] = '=';
    ans[(n - 1) / 2] = '=';

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

こうすれば変な場合わけがいらないです。このようにA問題では上手に書くことでコード長を節約できる場合があって、そういう手口を考えるのが好きです。

B. Full House 3

かなり面倒な問題です。それぞれのカードの個数をソートして、3個以上のものと2個以上のものがあるかどうかを見れば良いです。解説はbit全探索をしていますが、大袈裟すぎないでしょうか。

use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        mut a: [u8; 7],
    }

    let mut a = a.iter().counts().iter().map(|x| *x.1).collect_vec();
    a.sort_unstable();
    a.reverse();
    println!(
        "{}",
        if a.len() > 1 && a[0] >= 3 && a[1] >= 2 {
            "Yes"
        } else {
            "No"
        }
    );
}

本番はこの個数ずつに分ける部分をかなりうじうじやってしまいました。反省しています。

C. Uniqueness

HashMapで個数を持てば、全探索が \(O(N)\) となります。Bよりも簡単に感じました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [u64; n],
    }

    let mut b = std::collections::HashMap::new();
    for &a in &a {
        *b.entry(a).or_insert(0) += 1;
    }

    let mut ans = !0;
    let mut cnt = 0;
    for (i, &a) in a.iter().enumerate() {
        if *b.get(&a).unwrap() == 1 {
            if a > cnt {
                ans = i + 1;
                cnt = a;
            }
        }
    }

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

ans: usize = !0 として、ans as isizeが -1 になることを利用しています。便利です。

D. Bonfire

煙全体が同じ方向に動くので、それ以外を動かせば良いという典型です。双対座標とも呼んだりしますね。

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        _n: usize,
        mut r: isize,
        mut c: isize,
        s: Bytes,
    }

    let mut set = std::collections::HashSet::new();
    let (mut x, mut y) = (0, 0);
    set.insert((x, y));

    for &s in &s {
        let (dx, dy) = match s {
            b'N' => (1, 0),
            b'W' => (0, 1),
            b'S' => (-1, 0),
            b'E' => (0, -1),
            _ => panic!(),
        };
        x += dx;
        y += dy;
        set.insert((x, y));
        r += dx;
        c += dy;
        if set.contains(&(r, c)) {
            print!("1");
        } else {
            print!("0");
        }
    }

    println!("");
}

これは簡単です。煙の座標をsetに入れて判定しています。

E. Tree Game

インタラクティブで驚きました。3以上の奇数長のパスは全て全て繋げることができ、あるパスを繋げたことによって他がつなげなくなることもないので、最初にこのようなパスを全列挙すれば良いです。

use proconio::{input_interactive, marker::Usize1};

fn main() {
    input_interactive! {
        n: usize,
        uv: [(Usize1, Usize1); n - 1],
    }

    let lca = LCA::new(&uv);
    let mut edges = std::collections::BTreeSet::new();
    for i in 0..n - 1 {
        for j in i + 1..n {
            let x = lca.dist(i, j);
            if x > 1 && (x & 1) == 1 {
                edges.insert((i, j));
            }
        }
    }

    if edges.len() & 1 == 1 {
        println!("First");
        let (x, y) = edges.pop_last().unwrap();
        println!("{} {}", x + 1, y + 1);
    } else {
        println!("Second");
    }

    loop {
        input_interactive! {
            i: isize,
            j: isize,
        }

        if i == -1 && j == -1 {
            return;
        }
        let i = i as usize - 1;
        let j = j as usize - 1;
        edges.remove(&(i, j));
        let (x, y) = edges.pop_last().unwrap();
        println!("{} {}", x + 1, y + 1);
    }
}

奇数長のパスの列挙はLCAを用いています。木は二部グラフであり、奇数長の閉路がないことと二部グラフであることは同値なのでこれを用いても解くことができます。計算量的にはそっちの方が良いですが、どちらでも十分解けます。

F. ABCBA

問題文にManacherと書いてありました。久々にライブラリを使ったので、使い方を思い出すのに時間がかかってしまいました。ちゃんと清書をしてREADMEも書きたいですね。

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

fn main() {
    input! {
        s: Chars,
    }
    let n = s.len();

    let mut pos = 0;
    let t = manacher(&s);
    for (i, t) in t.iter().enumerate().skip(n) {
        if t + i == 2 * n {
            pos = i;
            break;
        }
    }

    println!(
        "{}{}{}",
        s[..pos / 2].iter().join(""),
        if pos % 2 == 1 {
            s[pos / 2].to_string()
        } else {
            "".to_string()
        },
        s[..pos / 2].iter().rev().join("")
    )
}

どこで折り返しているかを意識する必要があります。ローリングハッシュとかでも解けるんですが、ライブラリを持っていません。文字列アルゴリズムは大体ローリングハッシュで解けてしまうのでちゃんと作っておきたいですね。

感想

2ペナがかなりパフォーマンス的に良くなかったですが、ABCDEFをある程度の速さで解けたのでよかったです。

相変わらずG問題には手が出ないのですが、どうしたら良いのでしょうか。今はGを解きにいく練習をしていなくて、どちらかというとFまでを安定して解くような精進をしています。とりあえずはこのような感じで典型を埋めて、青perfを維持できるようになりたいですね。

また来週も頑張りましょう。

CTAサンプル

これはCTAサンプルです。
内容を編集するか削除してください。

RELATED POST