【AtCoder】ABC 419 振り返り

AtCoder Beginner Contest 419 に参加しました。その振り返りです。
結果としては、 A ~ D の 4 完でした。

かなり辛い結果に終わりました。E と F が難しかったです。個人的には発想が回りませんでした。文字列アルゴリズムは苦手な印象があります。E の DP も前計算部分が高速にできることがわかっておらず、間に合わないと思っていました。問題文から E も F も DP であることは気づけていました。

A. AtCoder Language

問題文の通りに文字列 $S$ に対して、 if もしくは match 文を書く問題です。つい癖で if 文を使ってしまいますが、このように 3 つ以上のパターンがある時は match 文の方が綺麗ですね。

if s == "red" {
    println!("SSS");
} else if s == "blue" {
    println!("FFF");
} else if s == "green" {
    println!("MMM");
} else {
    println!("Unknown");
}

typo に気をつけて実装すれば良いです。

B. Get Min

$\emptyset$ で初期化された集合に対して、「ある要素を加える」「最小の要素を取り出す」という 2 種類の操作を行う問題です。

これは、 BinaryHeap という構造体によって可能です。 BinaryHeap は降順に並ぶので、最小の要素を取り出すためには大小関係を反転させて要素を加える必要があります。
個人的にはビット反転をするのが好きです。x < y => !x > !y が成り立つことを応用してビット反転してヒープに入れ、取り出した際にビット反転をします。 !!x = x が成り立つことも応用しています。- をつけるよりもビット演算なので速いはず！と信じています。

let mut h = BinaryHeap::new();
for _ in 0..q {
    input! {
        t: u8,
    }
    if t == 1 {
        input! {
            x: u64,
        }
        h.push(!x);
    } else {
        println!("{}", !h.pop().unwrap());
    }
}

計算量も、 $O(Q)$ で十分高速です。

C. King's Summit

問題文が難読です。
操作をよく見ると、
$(i, j) \to (i + k, j + l) \ k, l \in \lbrace -1, 0, 1 \rbrace$
という操作になっていることに気づけます。つまり、縦と横でそれぞれ独立に移動方向を決めることができます。

縦方向のみを考えます。つまり、 $(i, j) \to (i + k, j) \ k \in \lbrace -1, 0, 1 \rbrace$ という変換で全ての点の $i$ 座標を一致させることを目指します。最も離れた二点が出会うのにいちばん時間がかかります。逆にそれ以外の点について、二点が出会う場所にいくためにかかる時間はそれ以下です。よって、答えは、
$$
\max_{i, j \in \lbrace 0, ..., N - 1 \rbrace} \lvert R_i - R_j \rvert
$$
となります。

横方向も同様に考えることができるので、最終的に求める答えは、
$$
\max_{i, j \in \lbrace 0, ..., N - 1 \rbrace} \max ( \lvert R_i - R_j \rvert, \lvert C_i - C_j \rvert)
$$
となります。これは、 $R, C$ をそれぞれソートして先頭と末尾の差となります。よって、 $O(N \log N)$ で求めることができます。

let mut ans = 0;
rc.sort();
ans = ans.max((rc[n - 1].0 - rc[0].0 + 1) / 2);
rc.sort_by_key(|x| x.1);
ans = ans.max((rc[n - 1].1 - rc[0].1 + 1) / 2);
println!("{}", ans);

D. Substr Swap

同じ長さの文字列 $S, T$ があり、指定された範囲の連続部分列を入れ替える操作を $M$ 回したあとの $S$ を求める問題です。

$S$ のそれぞれの文字が何回か入れ替わることになりますが、回数がが偶数であればもとの $S_i$ のまま、奇数であれば $T_i$ の文字に入れ替わることがわかります。
よって、それぞれの文字が入れ替わった回数の偶奇が求まればそれぞれの文字について $S_i$ が採用されているか $T_i$ が採用されているかわかります。
これは、 imos 法によって求めることができます。計算量は $O(N + M)$ で十分高速です。

let mut v = vec![0isize; n + 1];
for &(l, r) in &lr {
    v[l] += 1;
    v[r] -= 1;
}
for i in 0..n {
    v[i + 1] += v[i];
}
let mut ans = vec![];
for (i, &v) in v[..n].iter().enumerate() {
    if v & 1 == 0 {
        ans.push(s[i]);
    } else {
        ans.push(t[i]);
    }
}
println!("{}", ans.iter().join(""));

imos 法ってあんまり気にしたことがないです。数列 $A$ に対してその差分の数列を $D$ とします。つまり、 $D_i = A_{i}-A_{i - 1}, D_0 = 0$ とします。すると $D$ の累積和が $A$ になります。微分と積分を数え上げ測度上で行っている感じです。（簡単にいうと差分を取る操作が微分に対応して、和を取る操作が積分に対応しています。）その関数を直接求めるよりも導関数を求める方が簡単（今回だと一つ前の数との差分を求めるのが簡単）なので、それを求めてから積分しているイメージで、累積和と変わりなく思っています。

E. Subarray Sum Divisibility

数列 $A$ の全ての長さ $L$ の部分文字列が $M$ の倍数となるように、$A$ の各要素に $1$ を足していきます。このときの最小の足した回数を求める問題です。

まず、全ての要素を $M$ にすることで達成できるので、答えは $MN - \sum A$ 以下です。
条件を式で書くと、
$$
A_0 + \dots + A_{L - 1} \in M \mathbb{Z} \
A_1 + \dots + A_L \in M \mathbb{Z} \
A_2 + \dots + A_{L + 1} \in M \mathbb{Z}
...
$$

となります。（どうやって改行するのかわかりませんでした。\\ で改行できないのやめれくれ。）
これだと、複数の要素がかかわっているのでむずかしいですが、冷静に同値変形をすると

$$
A_0 + \dots + A_{L - 1} \in M \mathbb{Z}
$$
と
$$
A_{i + L} - A_i \in M \mathbb{Z} \ i \in \lbrace 0, \dots, N - 1 - L \rbrace
$$

となります。ここで二つ目の式により、 $A_0$ をある値に決めた時に $A_L, A_{2L}, \cdots$ をどのような値にするべきで最小の操作回数がいくつかが DP で求まります（$A_{kL}$ は $A_0, A_0 + L$ のどちらかの値となります。よってそれを耳に持つ DP をすればよいです）。同様にして $A_i$ をある値に決めた時に $A_{kL + i}$ をどのような値にすべきで最小の操作回数がいくつかも耳 DP で求めることができます。
さらに一つ目の式があるので、 $A_0 + \dots + A_i \ i \in \lbrace 0, \dots, L - 1 \rbrace$ が $L$ で割った余りを耳を持ってそのときの最小値を求める DP をしていけば良いです。

計算量が難しいですが、最初の DP で $O(M \times L \times \frac{N}{L})$ となります。最後の DP で $O(L \times M \times M)$ となります。よって、全体は $O(MN + LM^2)$ となり十分高速です。

コンテスト中には解けませんでした。「$A_0, A_1, \dots, A_{L - 1}$ の値が決まるとすべてが決まる」ということにきづけませんでした。悲しい。一つ目の式をすごく蔑ろにしていて、差分ばっか考えていました。おそらく、差分ばっか考えていても最初の DP パートは思いつけなくて、最後の DP をしたいので前計算で最初の DP をしたくなるんですよね。解説の書き方を逆にするべきだったなあと思うんですが、ここまで書いてしまいました。あは。

F. All Included

DP 感があります。 Trie みたいなものを耳に持ちたいです。なんとできるようです。むずかしいですね。
Aho-Corasick を初めて知りました。文字列アルゴリズムは弱いので勉強しなくては。大昔に授業でオートマトンをやったんですが、ほとんど記憶がないです。今回の F もオートマトンが関係あるように見えます。この辺を勉強したい！

総括

悔しい結果で終わりましたが、学びのある ABC でした。ちなみに ARC も考えていたんですが、何も成果がありませんでした。お疲れ様でした。