AtCoder Beginner Contest 215 - zeronosu77108’s blog

バーチャル参加をしました。 5完 52:58 でした。

A - Your First Judge

問題文の通り Hello,World! と一致するか判定したら良いですね。

fn main() {
    input! { s: String }
 
    let ans = s == "Hello,World!";
    println!("{}", if ans {"AC"} else {"WA"});
}

提出

B - log2(N)

問題文

$2 ^ k \leq N$ となる最大の $k$ を求める問題。制約が$N \leq 10^{18}$ なので最大でどれくらいになるか考えて見ます。 $\log_2(10^{18})$ は $60$ 以下なので、愚直に求めても良さそうです。愚直に $2$ の累乗を計算していって超えないギリギリを求めます。

fn main() {
    input! {
        n : u64
    }
 
    let mut ans = 0;
    {
        let mut tmp = 1;
        while tmp * 2 <= n { tmp *= 2; ans+=1; }
    }
 
    println!("{}", ans);
}

提出

C - One More aab aba baa

問題文

苦労しました… $N \leq 8$ なので全探索して良いんですが、 Rust の（Itertools の） permutations を使うと、重複が出るので焦っていました。よく考えると、重複削除してソートされた奴から $K$ 番目のやつを出力したら良いです…

C++ でも next_permutation とかを使って列挙したらいけると思います。

fn main() {
    input! {
        mut s : Chars,
        k : usize
    }
    let n = s.len();
    let mut ans = s.iter().permutations(n)
        .map(|p| p.iter().join("")).collect_vec();
 
    ans.sort(); ans.dedup();
    println!("{}", ans[k-1]);
}

提出

D - Coprime 2

問題文

難しくないですか？僕は苦手です。最大公約数が $1$ である必要があるので、素因数分解が使えそうです。 $10^{5}$ 以下の素数はそんなに多くないので、素因数分解してそこに現れる倍数を消していく。既に消されている素数はスキップする。とすると良さそうです。

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

    // 素因数分解用のテーブルを用意
    let mut amax = *a.iter().max().unwrap();
    let mut sieve = (0..=amax).collect_vec();
    for i in 2..=amax {
        if sieve[i] != i { continue }
        for j in ((i*i)..=amax).step(i) { sieve[j] = i; }
    }
    
    let mut ans : BTreeSet<usize> = (1..=m).collect();
    for &ai in a.iter() {
        let mut ai = ai;
        let mut p = HashSet::new();
        while ai != 1 { p.insert(sieve[ai]); ai /= sieve[ai]; } // a_i を素因数分解

        // 現れる素数の倍数を答え候補から削除
        for pi in p.into_iter() {
            if !ans.contains(&pi) { continue }  // 既になければスキップ
            for i in (pi..=m).step(pi as usize) { ans.remove(&i); }
        }
    }

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

提出

E - Chain Contestant

問題文

D よりこちらの方が（考察は）簡単に思えました。 AAC ～ AJC まで 10種類しかなくて、同じ種類のコンテストは連続でしか参加できないため、今までどこに訪れたか・最後に参加したコンテスト分かれば良さそうです。そういう状態を持った DP をします。

dp[i][j][k] : i番目の文字まで使って、j のビットが立っている所は訪れていて、 k というコンテストを最後に参加した場合の数。

i 番目の文字を使うというのがめんどくさいので、 dp と next というテーブルを使って遷移しています。

next[x][1<<x] += 1 をしているのは、その部分からコンテストに出始めたところを考えています。後は、 j >> x & 1 == 1 で j の状態は既に x が使われているかを判定していて、既に使われているなら最後に参加したコンテスト k が x と同じでないといません。その判定をして continue しています。後は、 j という状態から x を使ったという状態に行きたいので j | (1<<x) に遷移させます

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

    let mut s : Vec<usize> = s.iter().map(|&c| (c - b'A') as usize).collect();  // 0..9 に変換しておく
    let mut dp = vec![vec![0_u64; 1<<10]; 10];
    const MOD : u64 = 998244353;

    for x in s.into_iter() {
        let mut next = dp.clone();
        next[x][1<<x] += 1; // ここから参加し始める

        for j in (0..(1<<10)) { for k in 0..10 {
            if j>>x&1 == 1 && x!=k { continue } // xを使っているなら、最後が x じゃないとダメ
            next[x][j | (1<<x)] += dp[k][j];
            next[x][j | (1<<x)] %= MOD;
        }}

        dp = next;
    }

    let mut ans = 0;
    for i in 0..(1<<10) { for j in 0..10 { ans += dp[j][i]; ans %= MOD }}

    println!("{}", ans)
}