AtCoder Beginner Contest 172 参加記

誰かの役に立つこともあるかもしれないので、参加記を書いておくことにする。
https://github.com/tanakh/competitive-rs をライブラリとして使っているので、突然出てくるecho!とかはそれ由来だと思って下さい。

A - Calc

問題に書いてあるとおり $a+a^2+a^3$ を出力すれば良いだけだけど、念のために範囲を確認しておきたい。$1≦a≦10$ なので、64ビットでも32ビットで十分収まる。

use competitive::prelude::*;

fn main() {
    input! {
        a: i64,
    }

    let ans = a + a.pow(2) + a.pow(3);
    echo!(ans);
}

B - Minor Change

操作は1文字の書き換えだけなので、明らかに異なっている位置の文字を目的の文字に変更するのがベストのはず。なので操作回数は、SとTで異なっている位置の数になる。

use competitive::prelude::*;

fn main() {
    input! {
        s: Chars,
        t: Chars,
    }

    let ans = s.iter().zip(t.iter()).filter(|(c, d)| c != d).count();
    echo!(ans);
}

C - Tsundoku

一瞬小さい方の本をグリーディーに選択していくのがベストなのかなと思ってしまったが、これは間違い。例えば、

10 10 20
10 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5 5 5 5

のような入力が来たとき、Aの先頭に大きな値があるので下の方ばかり選ばれて4つしか読めないのに対して、最初にがんばって10を読めばあとで軽い本が沢山読めるので、先頭だけ見て貪欲に選んではいけない。

じゃあどうすればいいかって考えて、Aをどこまで読むのかを決めれば、あとはBを読めるだけ読むのがベストだろう。読む時間は正だと書いてあるので、読む数に対して単調増加である。こういう場合は、二分探索で高速に答えが求められる。これをAを読む冊数全てに対して行えば、計算量はO(NlogM)になるので、これで多分良さそうとなる。

use competitive::prelude::*;

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

    let mut a_acc = vec![0; n + 1];
    for i in 0..n {
        a_acc[i + 1] = a_acc[i] + a[i];
    }

    let mut b_acc = vec![0; m + 1];
    for i in 0..m {
        b_acc[i + 1] = b_acc[i] + b[i];
    }

    let mut ans = 0;

    for i in 0..=n {
        if a_acc[i] > k {
            break;
        }
        ans = max(ans, i + upper_bound(&b_acc, &(k - a_acc[i])) - 1);
    }

    echo!(ans);
}

しゃくとり法を用いた解法も考えられる。reverse(A)とBを連結した配列を考えると、そのsubstringのうち、AとBの境界を含んでいて、かつ和がK以下のもののうち一番長いものを求めるという問題に落とせる。和がKであるような区間の全列挙がしゃくとり法で$O(N+M)$でできるので、この問題もそれで解ける。

use competitive::prelude::*;

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

    let c = a.into_iter().rev().chain(b).collect_vec();

    let mut i = 0;
    let mut j = 0;
    let mut acc = 0;
    let mut ans = 0;

    loop {
        if acc <= k {
            if i <= n && n <= j {
                ans = max(ans, j - i);
            }
            if j >= c.len() {
                break;
            }
            acc += c[j];
            j += 1;
        } else {
            acc -= c[i];
            i += 1;
        }
    }

    echo!(ans);
}

D - Sum of Divisors

約数の個数ってどうやって求めるんだったっけ？ってWikipedia見直して、$n=p_1^{n_1}p_2^{n_2}...p_k^{n_k}$ のとき $(p_1+1)(p_2+1)...(p_k+1)$ ってのみて、ああ、そうだったどの素因数を何個選ぶかでユニークになるからそうだったってなった。1～nまで全部の数に対して都度素因数分解をしてたら微妙に間に合わなさそうだなあって思った。それで、1～nまで全部素因数分解するなら、エラトステネスの篩が使えるじゃん、って気付いた。普通は素数で配列をフィルターするだけだけど、その際にフラグを立てるのではなく、約数の個数を更新していけば良い。

use competitive::prelude::*;

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

    let mut num_of_divs = vec![1; n + 1];

    for i in 2..=n {
        if num_of_divs[i] != 1 {
            continue;
        }

        for j in (i..=n).step_by(i) {
            let mut t = 1;
            let mut k = j;
            while k % i == 0 {
                t += 1;
                k /= i;
            }
            num_of_divs[j] *= t;
        }
    }

    let mut ans = 0;
    for i in 1..=n {
        ans += num_of_divs[i] * i;
    }
    echo!(ans);
}

終了後の考察で、エラトステネスのふるいじゃなくても良いことに気付いた。素数だけじゃなくて、全部の数で愚直にその倍数を足せば良いだけだった。各ループが$N/i$ 回回るので、$N/1+N/2+...+N/N$ で $O(NlogN)$ で、ループが軽いから$N=10^7$程度でも通るみたいだ。

use competitive::prelude::*;

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

    let mut ans = 0;
    for i in 1..=n {
        for j in (i..=n).step_by(i) {
            ans += j;
        }
    }
    echo!(ans);
}

これがだいたい400msで通る。内側のループは、$i + 2i + ... + ki$ の等差数列なので、ループじゃなくて一発で計算できるし多分そうすれば一瞬で終わるようになると思う。でも計算するのは面倒なのでやらない。

E - NEQ

こういうの苦手でしんどかった。問題の条件は要するに、AとBで同じ位置には違うものが入ってるってのと、AとBはそれぞれ重複要素がないっていうことで、後者の重複要素がないってだけならまあ簡単。で、ここで考え方に分岐が発生するんだけど、1つめは両方の条件を満たすものを直接求める方法をなんとかして考えるって方針で、もう1つは前者の条件を満たさないものを引くっていう方針。

直接的な方法だと、何らかの状態を使ってDPとかになるのかなあという感じでもやもやしていたんだけど、どうやっても$O(NM)$より減らせる気配がなかった。

条件を満たさないものを引くっていう方針だと、それをどうやって計算するのかってのでいくつか考え方がありそうで、まあ1つは、1要素かぶってるものと、2要素かぶってるものと、･･･n要素かぶってるものをそれぞれ計算して引くって言うのがすぐ思いつくんだけど、これを採用するにはそれぞれが$O(logN)$程度で計算できる必要がある。i個かぶってるものってどうやったら計算できるんだろう？まず被ってる位置が$C(N,i)$通りあって、それへの割り当てが$C(M,i)$あるなあ。残りを重複しないように埋めるのはどうやるんだ･･･？適当に埋めるなら$P(M-i,N-i)^2$でいいけど、ダブってカウントする部分が出ますよね･･･うーんうーん･･･って考えてたら、これ被り方が最初の条件満たさないもののサブセットみたいになってないか？こういうときって包除原理使えばユニークな数が求められるんじゃ？ってピーンと来た。んでふんわりした気持ちのままとりあえず実装するだけならすぐなので実装してみたら、サンプルデータが全部通ったので、サブミットしたら通った。良かった。

use competitive::number::*;
use competitive::prelude::*;

type GF = competitive::gf::GF<promote!(1_000_000_007)>;

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

    let fact = gen_fact_table::<GF>(m + 1);
    let p = |n, k| fact[n] / fact[n - k];

    let mut ans = GF::new(0);

    for i in 0..=n {
        let t = comb_from_table(n, i, &fact) * p(m, i) * p(m - i, n - i).pow(2);
        if i % 2 == 0 {
            ans += t;
        } else {
            ans -= t;
        }
    }

    echo!(ans);
}

上のコードで、GFは有限体$F_p$を生成するクラスで、promote!は任意の整数定数から型レベル整数を作るマクロ。割り算が$O(logP)$でできる。

F - Unfair Nim

Eに時間がかかりすぎて解けなかった。あとで通しておきたい。