【AtCoder】ABC421 振り返り

AtCoder Beginner Contest 421 に参加しました。その振り返りです。

結果としては勝ちになりました。D, E を早めに諦めたのがよかったです。ともに実装が重たそうな問題で、実装が苦手な私には相性がよくなかったです。

A. Misdelivery

書いてある問題文の通りに実装する問題です。特に話すこともないと思います。

println!("{}", if s[x - 1] == y { "Yes" } else { "No" });

Usize1 で受け取るのがセオリーですが、面倒だったので usize で受け取り 1 を引いて 0-index に揃えています。use proconio::marker::Usize1; のタイピングをめんどくさがった形です。

B. Fibonacci Reversed

こちらも書いてある問題文の通りに実装する問題です。 $f$ の計算を高々 $10$ 回しか行わないことを考えると、 $f$ の実装をある程度高速にすれば良いことがわかります。これは足し算をした後にリバースを言語の機能ですればよいです。 String に変換をすると行いやすいです。

for _ in 0..8 {
    let p = (x + y).to_string().chars().rev().collect::<String>();
    (x, y) = (y, p.parse::<usize>().unwrap());
}
println!("{}", y);

String を p.reverse() のようなことってできないんですね。悲しい気持ちになっていました。

C. Alternated

発想が必要な問題でした。最終的な状態がどのような状態かを考えると、
ABABAB..ABAB、BABABA..BABA の二通りしかありません。よって、それぞれにするために必要な操作回数を求めて、その最小値を計算すれば良いことがわかります。

ABABAB..ABAB にすることを考えます。移動している最中に同じ文字同士を入れ替える必要はありません。B同士を入れ替えることはないので、Aをすべての手で動かします。また、A同士を入れ替えることはないので、Aの初期状態のインデックス前からを $a_0, a_1, ..., a_{N - 1}$ とするとこれを最短で $0, 2, 4, ..., 2n - 2$ とするのがよいです。よって、
$$
\sum_{i = 0}^{n - 1} |a_0 - 2i|
$$
が答えとなります。
BABABA..BABA は、さきほどのA, Bをいれかえればまったく同じことになります。

これらを実装することで $O(N)$ で答えが求まります。

let mut ansa = 0;
let mut cnta = 0;
let mut ansb = 0;
let mut cntb = 0;
for (i, &s) in s.iter().enumerate() {
    if s == b'A' {
        ansa += i.abs_diff(2 * cnta);
        cnta += 1;
    } else {
        ansb += i.abs_diff(2 * cntb);
        cntb += 1;
    }
}
println!("{}", ansa.min(ansb));

コンテスト中とは思えないほど綺麗なコードになりました。

D. RLE Moving

これやばいです。することはすぐにわかりましたが、実装が面倒だなあと言って逃げました。何も言いません。

F. Erase between X and Y

ある数の後ろへ要素の挿入するクエリと、二つの数の間にある数の合計値を計算し削除するクエリの、二つのクエリをこなす問題です。

まず、クエリ2 に関してすべてのクエリでのトータルの削除される要素の数は、その度に削除されるのでクエリ1で挿入された要素の数以下になります。つまり、

$$
\sum_{Q_2} |i(x) - i(y)| < Q_1
$$

となります。未定義の文字や関数がたくさんありますが、気持ちで理解してほしいです。
この考察により、$1$ つの要素の削除に $O(1)$ や $O(\log Q)$ を使っても大丈夫だとわかります。

クエリ1 を見ると、言っていることは双方向リストと同じです。https://atcoder.jp/contests/abc344/tasks/abc344_e をみると、クエリ2を改変するだけで良さそうだとわかります（一点挿入一点削除と検索するとでてきました。上の考察で一点削除ができれば十分だと考察が進んでいたおかげで検索ができました）。

あとはクエリ2 で $x, y$ のどちらが先頭にあるかを求めることができれば良いです。$x \to y, y \to x$ を一手ずつ調べていくと、どちらかが「削除される個数回」で到達できることがわかります。クエリ全てでの合計の削除される個数が高々 $O(Q)$ であることは考察済みなので、両者をともに進めていくことで全体 $O(Q)$ で求めることができます。

以上を丁寧に実装します。ちなみに双方向リストの実装を全く知らなかったので、ながたかな先生のABC344Eの提出を参考にしました。先生の提出はとても勉強になるので、毎回見ています。わたしの Rust の書き方はかなりながたかな先生に影響を受けています。いつもありがとうございます。

let mut prev = HashMap::new();
let mut next = HashMap::new();
next.insert(-1, 0);
prev.insert(0, -1);
next.insert(0, 1 << 30);
prev.insert(1 << 30, 30);
for i in 0..q {
    let i = i as isize + 1;
    input! {
        com: u8,
    }
    match com {
        1 => {
            input! {
                x: isize,
            }
            let z = next[&x];
            *next.get_mut(&x).unwrap() = i;
            *prev.get_mut(&z).unwrap() = i;
            next.insert(i, z);
            prev.insert(i, x);
        }
        2 => {
            input! {
                mut x: isize,
                mut y: isize,
            }
            let mut cx = x;
            let mut cy = y;
            let mut b = true;
            for _ in 0.. {
                if let Some(z) = next.get(&cx) {
                    if *z == y {
                        b = false;
                        break;
                    }
                    cx = *z;
                } else {
                    b = true;
                    break;
                }
                if let Some(z) = next.get(&cy) {
                    if *z == x {
                        b = true;
                        break;
                    }
                    cy = *z;
                } else {
                    b = false;
                    break;
                }
            }
            if b {
                std::mem::swap(&mut x, &mut y);
            }
            let mut ans = 0;
            let mut x = next[&x];
            loop {
                if x == y {
                    break;
                }
                let w = prev[&x];
                let z = next[&x];
                ans += x;
                *next.get_mut(&w).unwrap() = z;
                *prev.get_mut(&z).unwrap() = w;
                next.remove(&x);
                prev.remove(&x);
                x = z;
            }
             println!("{}", ans);
        }
        _ => unreachable!(),
    }
}

以上で $O(Q)$ で実装できました。HashMap の影響で実行時間がかなり長くなっています。悲しいですね。

総括

考察自体はうまくいっていましたが、実装が苦手であることが顕著によくない方向にでました。自分の解ける問題をちゃんと見つけることができるようになっていて、途中を飛ばすことが増えてきました。
重実装に立ち向かえるように勉強をするべきなんですが、めんどい！！！考察をするのが好きなんですが、実装が嫌いです。考察だけして実装を飛ばした精進がたくさんあります。うーん。

なるべくいろいろなものをライブラリとして用意する方針にシフトチェンジしようかなと思っています。来週も頑張りましょう！