bouzuya.hatenablog.com

ぼうずやのにっき

ポケモンカード GB をクリアした / ABC177 A, B, C, D, E を解いた

先日『ポケモンカード GB 』をクリアした。プレイ時間は 13 時間。クリアし、プロモーションカードをコンプリートした。途中プロモーションカード (トレード) のためにメタモンを探して延々とバトルしていたので時間がかさんでいる。

デッキとしてはヒトカゲの初期デッキを簡素化したようなもの。ドローのためにマサキ・オーキドはかせあたりを限界まで足して、エネルギーリムーブやエネルギー回収などを積んだ感じ。基本的にはリザード・ウィンディのかえんほうしゃあたりの火力でなんとかする。ブーバー (どくが出る側) などでターンを稼いでみたりもした。リザードンは 2 枚さしていて火力が過剰かと思ったけど、最後の四連戦など HP の大きいポケモンを繰り返されるとリザードンの勢いでなんとかしないと厳しそうだった。個人的にはガルーラ (ドロー) が欲しかったのだけど最後まで出なかった。

ABC177 : AtCoder Beginner Contest 177

use std::collections::HashSet;

use proconio::input;

fn gcd(n: usize, m: usize) -> usize {
    if m == 0 {
        n
    } else {
        gcd(m, n % m)
    }
}

fn prime_factorization(n: usize) -> Vec<(usize, usize)> {
    let mut p = vec![];
    if n < 2 {
        return p;
    }
    let mut n = n; // shadowing
    for i in 2.. {
        if i * i > n {
            break;
        }
        let mut c = 0;
        while n % i == 0 {
            c += 1;
            n /= i;
        }
        if c > 0 {
            p.push((i, c));
        }
    }
    if n != 1 {
        p.push((n, 1));
    }
    p
}

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

    let mut pairwise = true;
    let mut set = HashSet::new();
    for a_i in a.iter().copied() {
        for (p, _) in prime_factorization(a_i) {
            if !set.insert(p) {
                pairwise = false;
                break;
            }
        }
    }

    let mut g_a = a[0];
    for a_i in a.iter().copied() {
        g_a = gcd(g_a, a_i);
    }
    let setwise = !pairwise && g_a == 1;

    let ans = if pairwise {
        "pairwise coprime"
    } else if setwise {
        "setwise coprime"
    } else {
        "not coprime"
    };
    println!("{}", ans);
}

今日のコミット。