AtCoder Beginner Contest 174 参加記

問題はこちら
https://atcoder.jp/contests/abc174

A - Air Conditioner

x >= 30 かどうかを調べるだけなんだけど、いくら何でも簡単すぎないか。

use competitive::prelude::*;

fn main() {
    input! {
        x: i32,
    }
    echo!(if x >= 30 {"Yes"} else {"No"});
}

B - Distance

計算誤差のことを考えたくないので、$\sqrt{x^2 + y^2} ≦ d$ は両辺を二乗して $x^2 + y^2 ≦ d^2$ で計算するべきという問題だと思う。その際に、これが i64 を溢れないかを無意識的にちゃんとチェックするようにしたい。

use competitive::prelude::*;

fn main() {
    input! {
        n: usize,
        d: i64,
        xy: [(i64, i64); n],
    }

    let ans = xy
        .into_iter()
        .filter(|(x, y)| x.pow(2) + y.pow(2) <= d.pow(2))
        .count();
    echo!(ans);
}

C - Repsept

$7...7$ を $k$ で割った余りは、m = (m * 10 + 7) % k とやると、逐次的に求まる。これが最初に0になるのが何回目なのかを求めれば良いんだけど、永遠に0にならないこともあるから、その場合を検出する必要がある。ループの各ステップにおいて、次の値は、直前の値のみに依存して決まるから、同じ値が2回出現したら、それはループになって永遠に0にはならないと言うことが分かる。それで、この値は0からk-1 (k <= 1e5)の値しか取らないので、既に見たものを覚えておけば十分高速に解ける。

いつもよりBとCの難易度の差が付いてた気がした。

use competitive::prelude::*;

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

    let mut ss = BTreeSet::new();

    let mut cur = 7 % k;
    for i in 1.. {
        if cur == 0 {
            echo!(i);
            break;
        }
        if ss.contains(&cur) {
            echo!(-1);
            break;
        }
        ss.insert(cur);
        cur = (cur * 10 + 7) % k;
    }
}

D - Alter Altar

最終的に WR という部分列を含まないようにせよと言うことだけど、これは結局どういうことかと考えると、最終状態が R...RW...W という具合に、Rがすべて左側に、Wが全て右側にならなければならないということだ。ということは、左から見ていって、Wが見つかったら、それはなんとかしないといけない。Rに変化させるか、どこかWのやつと入れ替えるかだけど、よくよく考えると右側のWもなんとかしないといけないわけなので、結局一番左のWと一番右のRをスワップさせるっていうのが、1手で2度美味くて、どうやら他の操作はこれより良くなると言うことがないように思えた。なんで、これを条件を満たすようになるまで繰り返せば良い。実装は、左端と右端のポインタを持って、それぞれWかRを見つけるまで反対側に向かって動かして行く、みたいなクイックソートのpartition操作と同じことをやればいい。クイックソートのスワップ回数が少ないって言うのがなんかこういうのでも分かるっていうのがなんとなく興味深かった。

use competitive::prelude::*;

fn main() {
    input! {
        n: isize,
        c: Chars,
    }

    let mut l = 0 as isize;
    let mut r = (n - 1) as isize;
    let mut ans = 0;

    loop {
        while l < n && c[l as usize] != 'W' {
            l += 1;
        }
        while r >= 0 && c[r as usize] != 'R' {
            r -= 1;
        }
        if l >= r {
            break;
        }
        l += 1;
        r -= 1;
        ans += 1;
    }

    echo!(ans);
}

E - Logs

丸太の長さの最大を決めれば、それに必要な切断回数の最小値は簡単に求まるよな、ってなって、んで丸太の長さの最大対して切断回数は明らかに単調減少だよなってなって、じゃあ二分探索するだけじゃんってなった。これCとかDと比べても超簡単だと思うんだけど、実際どうなんだろ。

use competitive::prelude::*;

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

    let ans = binary_search(1_000_000_000_usize, 0_usize, |m| {
        let t = a.iter().map(|a| (a + m - 1) / m - 1).sum::<usize>();
        t <= k
    });
    echo!(ans);
}

F - Range Set Query

結構悩んだ。直接的にやるなら、全位置に対してbitsetもってなんとかならんか･･･って思ったりして、でも $(5e5)^2/64$ bitはさすがに無理だよなあ。というか、よく考えたら減算するためには出現フラグじゃなくて出現回数がいるからそもそも全然ダメじゃん。とか不毛なことを暫く考えてた。

各石に対して直前の同じ色の出現位置を計算しておけば、[l, r) のクエリに対して、その範囲内の、直前の出現位置がlより前のものの数を数えれば、それはその範囲内で重複しないものなワケだから、つまりユニークな色の個数になるな、と気付いてなんかちょっと考察が進んだ。でもすぐに考えに詰まって、これはループ内の処理が無茶苦茶軽いから、SIMDが効いてワンチャン$O(N^2)$で通らんやろかとかよく分からん方向に考えが脱線したりしてた。

うーん、うーんと考えてたら、直前の出現位置がl未満のところを1に、それ以外を0にした配列に対して[l, r)の部分和を取ったものだという当たり前のことに気付いて、これはクエリがlに対して昇順だったら、1の場所は単調に増えていくだけになるから、SegmentTreeをアップデートしながらクエリを叩けば解けることに気付いた。じゃあ、クエリの順番をlでソートしてやれば良いだけだなってなって、ようやく解けた。

use competitive::prelude::*;

fn main() {
    input! {
        n: usize,
        q: usize,
        c: [Usize1; n],
        q: [(Usize1, Usize1); q],
    }

    let q = q
        .into_iter()
        .enumerate()
        .sorted_by_key(|r| r.1)
        .collect_vec();

    let mut cur_l = 0;

    let mut prev_occ = vec![-1_isize; n];
    let mut prev_pos = vec![-1_isize; n];

    for i in 0..n {
        prev_pos[i] = prev_occ[c[i]];
        prev_occ[c[i]] = i as isize;
    }

    let mut upd = vec![-1_isize; n];
    let mut b = SegmentTree::<Sum<isize>>::new(n);

    for i in 0..n {
        if prev_pos[i] == -1 {
            b.update(i, Sum(1));
        } else {
            upd[prev_pos[i] as usize] = i as isize;
        }
    }

    let mut ans = vec![-1_isize; q.len()];

    for (i, (l, r)) in q {
        while l > cur_l {
            if upd[cur_l] >= 0 {
                b.update(upd[cur_l] as usize, Sum(1));
            }
            cur_l += 1;
        }
        ans[i] = b.query(l, r + 1).0;
    }

    for ans in ans {
        echo!(ans);
    }
}