ABC413

お久しぶりです。見返したらABCの振り返りはABC400と3ヶ月ぶりらしい。しばらくはゆったり更新しようかなぁと思います。

それから、少し前の回から録画をしていて、今回も例に漏れず。わざわざ録画して公開せずにおいておくのも微妙な気持ちになるので、一応公開してみる(URL)。一般的な水コーダーなので得られるものはあんまりない気もします。やばいことを言ってたら目を瞑ってください。Webカメラの調子が悪いので時折乱れます。

A - Content Too Large

$\sum A \leq M$ を判定すればよいです。

Rustには配列の合計を取るのにsumメソッドが存在しており、嬉しい。提出

use proconio::input;

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

    let s = a.iter().sum::<u64>();
    println!("{}", if s<=m { "Yes" } else { "No" });
}

B - cat 2

コンテスト終了後に気付きましたが、catコマンドということなんですね。本来の用法で(?)使われている場面を久しぶりに見た気がします。

解法の方はというと、制約が小さいので素直に二重ループを書いてあげればよいです。これぐらいの要素数であれば何も考えずにhashに突っ込んでも多分良いですね¹。Rustで文字列結合を書くのは微妙に面倒くさいので、Pythonで。提出

n = int(input())
s = [input() for _ in range(n)]

ss = set()
for i in range(n):
    for j in  range(n):
        if i==j: continue
        t = s[i] + s[j]
        ss.add(t)
print(len(ss))

Rustのコード量が多く序盤の問題を解くのが遅いよね～という文脈でPythonをとてもおすすめされ、ちょっとありだな～という気持ちはありつつ、型を頼りに生きているので真剣に序盤を置き換えるならNimになるのかな。などと考えています。

C - Large Queue

数列をそのまま管理するとメモリが壊れてしまう²ので、代わりにRLEした状態で管理してあげます。また、配列をそのまま使うと先頭の要素をpopする際に $O(|A|)$ かかってしまうので、代わりにqueueを使うことにします。提出

use std::collections::VecDeque;
use proconio::input;

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

    let mut que = VecDeque::new();

    for _ in 0..q {
        input! {
            t: u8,
        }
        if t==1 {
            input! {
                c: u64,
                x: u64,
            }

            que.push_back((x,c));
        } else {
            input! {
                k: u64,
            }

            let mut left = k;
            let mut ans = 0;
            while let Some((val, cnt)) = que.pop_front() {
                if left < cnt {
                    let v = cnt - left;
                    if v != 0 {
                        que.push_front((val,v));
                    }
                    ans += left*val;
                    break;
                } else {
                    left -= cnt;
                    ans +=val * cnt;
                    if left == 0 {
                        break;
                    }
                }
            }
            println!("{}", ans);
        }
    }
}

一応popする代わりに先頭位置のindexを管理する手法もありえますが、管理する対象を増やすと脳が壊れることが知られているので素直にやるのが吉です。

D - Make Geometric Sequence

「 $|r|$ が整数なので、制約から $N\geq30$ の場合は-1と1だけチェックしてあげればNoで、あとは何をやってもいいですね～」と言いながら書くとTLEとWAで困ります³。あれ？

まず、 $|r| \geq 1$ として良いです。これは、等差数列 $V$ に含まれる要素が有限個しかないことから、 $|r| < 1$ となるような場合はそれを反転した数列 $V'$ は公差が $\frac{1}{r}$ の等差数列になるからです⁴。

このことから、 $|r|=1$ の場合を除けば数列の要素の絶対値は狭義単調増加になっているはずで、結局ソートして判定をすればよいです。ソートがボトルネックで、 $O(N\log N)$ 時間で解くことができます。提出

use itertools::Itertools;
use num_rational::Ratio;
use proconio::input;


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

    let ca = a.iter().sorted().copied().dedup_with_count().collect_vec();
    if ca.len() == 1 {
        println!("Yes");
        return;
    } else if ca.len() == 2 && ca[0].1 == -ca[1].1 {
        if ca[0].0.abs_diff(ca[1].0) <= 1 {
            println!("Yes");
        } else {
            println!("No");
        }
        return;
    }
    
    let a = a.iter()
        .sorted_by_key(|x| x.abs())
        .map(|&x| Ratio::new(x,1))
        .collect_vec();
    
    let r = a[1] / a[0];
    let mut cur = a[0];
    for i in 1..n {
        cur *= r;
        if cur != a[i] {
            println!("No");
            return;
        }
    }
    println!("Yes");
}

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

    for _ in 0..t {
        solve();
    }
}

E - Reverse 2^i

問題文が難読シリーズ。やめてください。

なんやかんや15分ぐらい掛けて、以下の問題だなぁと読み取りました。

長さ $2^N$ の順列をマージソートします。ただし、ソートに使える操作は反転のみです。このとき作成可能な辞書順最小のものを求めてください。

ふむ。マージソートなんですか。なるほど？

少し困りますが、予想として、「2つの辞書順最小の配列 $A$ , $B$ があったときに、これらを連結して得られる数列 $C$ か、 $A$ , $B$ それぞれを反転して結合し、それを更に反転して得られる数列 $D$ のいずれかが、条件下で構築可能な辞書順最小となる」がぱっと浮かびます。

そして、これはやや明らかよりですね。辞書順最小を構成するには前にできるだけ小さい要素を起きたいので、そう考えるとこれしかない気がします。厳密な証明はわかりませんが、ACをかわりにおいておきます。提出

use itertools::Itertools;
use proconio::input;

fn rec(l: usize, d: u32, a: &mut Vec<u64>) {
    if d==0 { return; }
    
    let nd = d-1;
    let next_length = 2usize.pow(nd);

    rec(l, nd, a);
    rec(l+next_length, nd, a);

    let mut is_same = true;
    let k = l+2usize.pow(d);
    for i in l..k {
        if a[i] < a[next_length+i] {
            break;
        } else if a[i] > a[next_length+i] {
            is_same = false;
            break;
        }
    }

    if !is_same {
        a[l..l+next_length].reverse();
        a[(l+next_length)..k].reverse();
        a[l..k].reverse();
    }
}

fn solve() {
    input! {
        n: u32,
        mut a: [u64; 2usize.pow(n)]
    }

    rec(0, n, &mut a);
    println!("{}", a.iter().join(" "));
}

fn main() {
    input!{
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

F - No Passage

時間が足りません...

とりあえず青木くんの気持ちになりましょう。あるコマの隣接マスに"そこに移動したら $x$ ターンでゴールできる"マスがある場合、そこに移動させたくはありません。しかし、そのようなマスが2つ以上ある場合、青木くんがブロックできるのは高々1方向のため、高橋くんは $x$ が2番目に大きいマスへ移動すればよいということになります。

また、「あるマスがゴール可能になりうるタイミング」というのは、その隣接マスがゴールできる事がわかったタイミングです。ゴールに近いマスから確定していくので、周辺2マスが確定したマスはその時点で距離を確定してよいです。

以上を統合すると、ゴールマスを始点とする多始点BFSを行うことによって、 $O(HW)$ 時間で解くことができます。実装上、通常のBFSよりもdijkstraっぽい実装をするほうがきれいになると思います。提出

use std::{collections::VecDeque};

use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input!{
        h: usize,
        w: usize,
        k: usize,
        rc: [(Usize1, Usize1); k],
    }

    let mut seen = vec![vec![INF; w]; h];

    let mut que = VecDeque::new();
    for &(r, c) in rc.iter() {
        que.push_back((r,c,0));
    } 

    while let Some((pi,pj, c)) = que.pop_front() {
        if seen[pi][pj] != INF { continue; }
        seen[pi][pj] = c;

        for r in 0..4 {
            let ni = pi.wrapping_add(DI[r]);
            let nj = pj.wrapping_add(DJ[r]);

            if ni >= h || nj >= w || seen[ni][nj] != INF {
                continue;
            }

            let mut v = vec![];
            for rr in 0..4 {
                let nni = ni.wrapping_add(DI[rr]);
                let nnj = nj.wrapping_add(DJ[rr]);
                
                if nni >= h || nnj >= w || seen[nni][nnj] == INF {
                    continue;
                }
                v.push(seen[nni][nnj]);                
            }

            if v.len() >= 2 {
                v.sort();
                que.push_back((ni, nj, v[1]+1));
            }
        }
    }

    let ans = seen.iter().flatten().map(|x| if *x==INF { 0 } else { *x }).sum::<u64>();
    println!("{}", ans);
}