AtCoder Beginner Contest 179

これを使っています。
https://github.com/tanakh/competitive-rs

A - Plural Form

与えられた文字列の末尾が "s" なら "es" を、それ以外なら "s" を付けろってことなんで、ends_with("s")でチェックすればいい。Rustだと s + if s.ends_with("s") { "es" } else { "s" } がボローチェッカーで通らないので s をクローンするか、テストを事前に行うかの2通りの回避法がある。クローンしても実行速度的には問題ないけど、無駄に計算リソースが増えるのを嫌って後者でやった。

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(s: String) -> String {
    let suffix = if s.ends_with("s") { "es" } else { "s" };
    s + suffix
}

B - Go to Jail

windows() っていう、連続n要素のスライスを全列挙するおあつらえなメソッドがあるんで、それを使うと楽。そのスライスのうちのどれかが、すべてぞろ目になっているかどうか、っていうのは関数型的なコードですごい綺麗にかけるっていうお手本のような問題になってる。

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(n: usize, d: [(i32, i32); n]) -> bool {
    d.windows(3).any(|s| s.iter().all(|(a, b)| a == b))
}

C - A x B + C

ABが決まるとCは自動的に決まるんで、ようするに $A*B<N$ となるA, Bの組の数を数えろということ。Aを決めればBの取れる最大値は明らかに単に $(N-1)/A$ だし、これを足していけばいい。

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(n: usize) -> usize {
    let mut ret = 0;
    for a in 1..=n {
        ret += (n - 1) / a;
    }
    ret
}

D - Leaping Tak

計算量考えなければ、典型的なDPで a[i] = sum(a[i+d], d ∈ S) みたいな感じなんだけど、Sの要素数は$O(N)$になりうるので、これは$O(N^2)$かかる可能性がある。

Sは連続した区間10個程度という条件があるので、これを利用するはず。区間和は、累積和を計算しておけば$O(1)$で求まるので、ようするにこれでa[i]を計算するようにすればK回の足し算でa[i]が計算できる。配列の後ろから要素の値と累積和を計算していって、a[0]が答えになる。

use competitive::prelude::*;

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

# [argio(output = AtCoder)]
fn main(n: usize, k: usize, lr: [(usize, usize); k]) -> GF {
    let mut a = vec![GF::new(0); 2 * n + 1];
    a[n - 1] = 1.into();
    let mut acc = vec![GF::new(0); 2 * n + 2];
    acc[n - 1] = 1.into();

    for i in (0..n - 1).rev() {
        let mut cur = GF::new(0);
        for &(l, r) in lr.iter() {
            let l = i + l;
            let r = i + r + 1;

            cur += acc[l] - acc[r];
        }

        a[i] = cur;
        acc[i] = cur + acc[i + 1];
    }

    a[0]
}

E - Sequence Sum

Nが死ぬほどでかくて一見いかついし、なんか問題文も無駄にいかつく書いてあるけど、A[i]には毎回mod mが入るので、この値は高々mの周期でループする。mはとても小さいので、ループさえ求めてしまえば十分高速に計算できる。

具体的には、愚直に1個ずつ要素を計算していって、同じ値が出てきたら、前回その値が出てきたのが何要素目だったのかと、その時のその時点での累積和がわかれば、ループの長さと、そのループでの要素の合計が求まる。残り回数でそのループが何回回るかを計算して、さらに端数を足し合わせてやればいい。

やることは単純なんだけど、要素を計算するタイミングとか累積を足すタイミングとか、意外と慎重に書かないとバグりそうなところがあった。

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(n: usize, mut x: usize, m: usize) -> usize {
    let mut prev = vec![None; m];
    let mut acc = 0;

    for i in 0..n {
        if let &Some((prev_i, prev_acc)) = &prev[x] {
            let rest = n - i;
            let loop_len = i - prev_i;
            let loop_sum = acc - prev_acc;

            let loop_cnt = rest / loop_len;
            acc += loop_sum * loop_cnt;
            let rest = rest - loop_cnt * loop_len;

            for _ in 0..rest {
                acc += x;
                x = x * x % m;
            }

            break;
        } else {
            prev[x] = Some((i, acc));
            acc += x;
            x = x * x % m;
        }
    }

    acc
}

既出の場所を覚えておくのではなくて、1ステップで1歩進むイテレーターと、2歩進むイテレーターを併進させて、同じ要素にたどり着くまでのステップ数を数えるようなやり方でもループが検出できる。この場合、iステップで合流したなら、ループ長がiということになる。ループ回数とか端数の計算がずいぶん楽になるし、管理しておく状態もすっきりするので、コードを書くにおいて気を付ける部分は減るのでだいぶ気持ちよく書ける気がする。

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(n: usize, x: usize, m: usize) -> usize {
    let mut x1 = x;
    let mut acc1 = x;

    let mut x2 = x * x % m;
    let mut acc2 = x1 + x2;

    for i in 1..n {
        if x1 == x2 {
            acc1 += (acc2 - acc1) * ((n - i) / i);

            for _ in 0..n % i {
                x1 = x1 * x1 % m;
                acc1 += x1;
            }

            break;
        }

        x1 = x1 * x1 % m;
        acc1 += x1;

        x2 = x2 * x2 % m;
        acc2 += x2;
        x2 = x2 * x2 % m;
        acc2 += x2;
    }
    acc1
}

F - Simplified Reversi

問題のタイトル通り、やることはすごい単純で、要するに正方形を縦横に切っていくだけなんだけど、どういう風にデータを持てばシンプルになるかってのがキモなのかな？まあどうやっても正直そんなに難しい問題ではないと思う。

左上に長方形があって、その右側と下側に長方形がならぶようなかたちになって、左上の長方形を切るように置くときと、そうじゃないときで場合分けできる。左上の長方形を切るときは、長方形が小さくなって、その反対側の残りを右か下かの長方形の集合に追加する。左上じゃないところを切るときは、長方形の集合のうちどこを切るかを、mapの二分探索で調べて、その高さを拾ってこればいい。ちなみにこの場合は長方形を同じ方向にスライスするだけなので、特に更新処理をしなくてもいい。

（正直これ文字で書くのはすごい大変なのでイラストでも書ければ一発なんだけど、いい感じのデバイスがない･･･）

use competitive::prelude::*;

# [argio(output = AtCoder)]
fn main(n: usize, q: usize, qs: [(usize, Usize1); q]) -> usize {
    let mut ret = (n - 2).pow(2);
    let mut sq = (n - 1, n - 1);

    let mut yoko = BTreeMap::new();
    let mut tate = BTreeMap::new();

    for (dir, x) in qs {
        if dir == 1 {
            if x < sq.0 {
                yoko.insert((x + 1, sq.0), sq.1);
                sq = (x, sq.1);
                ret -= sq.1 - 1;
            } else {
                let (_, height) = yoko.range((0, 0)..(x, n + 1)).rev().next().unwrap();
                ret -= height - 1;
            }
        } else {
            if x < sq.1 {
                tate.insert((x + 1, sq.1), sq.0);
                sq = (sq.0, x);
                ret -= sq.0 - 1;
            } else {
                let (_, width) = tate.range((0, 0)..(x, n + 1)).rev().next().unwrap();
                ret -= width - 1;
            }
        }
    }

    ret
}