AtCoder Beginner Contest 420 に参加しました。その振り返りです。
すごく微妙な結果でした。考察自体はかなりはやくまとまったんですが、実装に時間がかかってしまいました。
A. What month is it?
$X$ 月の $Y$ ヶ月後が何月かを求める問題です。このような問題は、 $0$-index で考えて戻すと考えると $1$ 行で書きやすくなります。
println!("{}", (x - 1 + y) % 12 + 1);
B. Most Minority
問題文が長いですが、「$M$ 回のそれぞれの投票でだれが当選したか」を順に計算していくことができます。
$0, 1$ のどちらのグループが得点を得るかどうかが $O(N)$ で判断でき、得点を得た人の得点を更新する部分も $O(N)$ でできます。これが $M$ 回続くので計算量は高々 $O(MN)$ で十分高速に求まります。
実装がかなり回りくどくなってしまいました。
let mut scores = vec![0usize; n];
for j in 0..m {
let x = s.iter().filter(|s| s[j] == b'0').count();
let y = s.iter().filter(|s| s[j] == b'1').count();
if x == 0 || y == 0 {
for i in 0..n {
scores[i] += 1;
}
} else if x < y {
for i in 0..n {
if s[i][j] == b'0' {
scores[i] += 1;
}
}
} else {
for i in 0..n {
if s[i][j] == b'1' {
scores[i] += 1;
}
}
}
}
let mx = *scores.iter().max().unwrap();
for i in 0..n {
if scores[i] == mx {
print!("{} ", i + 1);
}
}
よく考えるとあまり削れるところがありません。タイピングが辛いです。
C. Sum of Min Query
要素がタプルの数列に対して、一点更新とそれぞれのタプルの最小値の和を計算する問題です。
各更新について、変更となる要素が一つしかありません。よって、その部分だけを逐一更新していけばよいです。更新自体も値を更新して最小値を計算するだけで、 $O(1)$ で可能だとわかります。
let mut ans = a.iter().zip(b.iter()).map(|(a, b)| a.min(b)).sum::<u64>();
for _ in 0..q {
input! {
c: char,
x: Usize1,
v: u64,
}
ans -= a[x].min(b[x]);
if c == 'A' {
a[x] = v;
} else {
b[x] = v;
}
ans += a[x].min(b[x]);
println!("{}", ans);
}
全体の計算量が $O(N + Q)$ となっています。
このように、更新をした時の影響範囲が少ないことはかなり役に立ちます。「操作をした時にほとんどは変わらない」といったことを考えるのとても大事です。
D. Toggle Maze
スタートからゴールへいくための最短経路を求める問題です。しかし、ドアが開閉するので、その部分が通れるかどうかわからず通常の BFS で解くことができません。
そこで、どのような情報がわかっていれば現在 o, x のどちらが通れるかを考えます。「この情報がわかっていれば BFS をそのまま適用できるのになあ」を考えて、その情報を状態に付け加えて BFS をするってわけです。
基本的に最短経路問題は賢すぎるものが多く、ある程度広い盤面での最短経路問題を考えようとすると BFS、DFS、ダイクストラなどの既知のアルゴリズムに帰着できないかなと考えることが多いです。
どのような情報が欲しいかを考えた時に、スイッチで切り替わった回数がわかればいいなとなります。しかしこれだけでは、状態の大きさが最悪で $O(HWHW)$（盤面の広さが $HW$ でそれぞれがスイッチの押された回数の状態をもつとしています）で、間に合わないことがわかります。
さらに考えると、スイッチが押されていない状況と $2$ 回押された状況はドアが閉じているか開いているかは全く同じになります。これを考えると、スイッチの押された回数の偶奇がわかれば、その状態からどのような遷移(上下左右)ができるかが決まります。これは状態の大きさが $2HW$ となり十分高速です。
あとは丁寧に実装するだけです。スタートにスイッチを一度押した状態で戻る場合があることを忘れて、2ペナしました。
let mut f = vec![vec![vec![!0usize; w]; h]; 2];
let mut que = VecDeque::new();
let mut s = (0, 0);
let mut t = (0, 0);
for i in 0..h {
for j in 0..w {
if a[i][j] == b'S' {
s = (i, j);
}
if a[i][j] == b'G' {
t = (i, j);
}
}
}
f[0][s.0][s.1] = 0;
que.push_back(((s.0, s.1), 0));
while let Some(((x, y), p)) = que.pop_front() {
let ok = if p == 0 { b'o' } else { b'x' };
let next = f[p][x][y] + 1;
for (dx, dy) in [(1, 0), (0, 1), (!0, 0), (0, !0)] {
let nx = x.wrapping_add(dx);
let ny = y.wrapping_add(dy);
if nx < h && ny < w {
if a[nx][ny] == ok || a[nx][ny] == b'.' || a[nx][ny] == b'G' || a[nx][ny] == b'S' {
if f[p][nx][ny] > next {
f[p][nx][ny] = f[p][x][y] + 1;
que.push_back(((nx, ny), p));
}
} else if a[nx][ny] == b'?' {
if f[(p + 1) % 2][nx][ny] > next {
f[(p + 1) % 2][nx][ny] = f[p][x][y] + 1;
que.push_back(((nx, ny), (p + 1) % 2));
}
}
}
}
}
println!("{}", f[0][t.0][t.1].min(f[1][t.0][t.1]) as isize);
地獄の実装です。盤面を上手く扱えるようなライブラリを作ろうかなと思うくらいには重実装でした。
E. Reachability Query
無向グラフの連結性判定に黒と白の頂点の色が関係する問題です。
タイプ 3 の判定が課題なんですが、よく考えると連結成分内に黒色の頂点があるかどうかを判断すればよいことがわかります。
黒と白がなければ、Union Find でできます。連結成分にしか興味がないので、各連結成分の代表点に黒色の頂点に関する情報をもたせてそれも一緒にマージしていけばよいことに気づけます。
今回の場合だと、黒色の頂点の個数です。クエリ 2 との関係を考えると黒色の頂点の個数を増減できるようにしたいので、個数を管理します。クエリ 2 のたびにその連結成分の代表点にまとめた黒色の個数も更新していきます。
let mut dsu = DSU::new(n);
let mut cnt = vec![0usize; n];
let mut col = vec![0u8; n];
for _ in 0..q {
input! {
t: u8,
}
if t == 1 {
input! {
u: Usize1,
v: Usize1,
}
let p = dsu.rep(u);
let q = dsu.rep(v);
if dsu.unite(u, v) {
let r = dsu.rep(u);
let tmp = cnt[p] + cnt[q];
cnt[p] = 0;
cnt[q] = 0;
cnt[r] = tmp;
}
} else if t == 2 {
input! {
v: Usize1,
}
if col[v] == 0 {
col[v] = 1;
cnt[dsu.rep(v)] += 1;
} else {
col[v] = 0;
cnt[dsu.rep(v)] -= 1;
}
} else {
input! {
v: Usize1,
}
println!("{}", if cnt[dsu.rep(v)] > 0 { "Yes" } else { "No" });
}
}
コードが長くなりました。これもライブラリ化を検討したいです。
DSU というのは、disjoint set union です。 $\lbrace 0, 1, \dots, n - 1 \rbrace$ をそれぞれ互いに交わらないいくつかの集合に分けるイメージを持っています。
計算量は $O((N + Q) \log N)$ となります。意外とマージ部分の実装が複雑で、ペなりました。
G. sqrt(n^2+n+X)
問題文がとても数学をしていました。
一旦冷静にサンプルを見てみると、 $m \ge 0$ が答えの時 $-m - 1$ も答えであるというエスパーができます。実際代入してみると、互いに同値であることが確認できます。よって、正であるようなものを全て求めることができれば、負であるものは $m \to -m - 1$ の変換をすることによって全て求めることができます。
以降は、 $n \ge 0$ として考えます。
$X \ge 0$ の場合をまずは考えました。すると、 $\sqrt{n^2 + n + X} \ge n$ なので、$\sqrt{n^2 + n + X} = n + \alpha \ (\alpha \ge 0)$ とおけます。これを計算すると、
$$
n = \frac{X - a^2}{2 \alpha - 1}
$$
となります。今回は、 $n$ を全て求めようとしているので $n = $ の式の形にまとめました。これをすべての $\alpha$ に対して調べるのですが、 $n \ge 0$ なので $X \ge \alpha ^2$ となります。このような $\alpha$ の個数はだいたい $\sqrt{X}$ 個なので、全探索することができます。
$X \lt 0$ のときを次は考えます。ここは天才発想なんですが、 $n' = -n, X' = -X$ の変換をします。これをどうして行なったかというと、まずは $X \lt 0$ は少し考えにくいので $X' = -X$ として正の数にしようと思いました。すると $n^2 + n - X'$ となるんですが、 $n' = -n$ とすることでさきほどと全く同じ式になることに気づきました（この部分は少し考察が難しいかもしれません）。
$\sqrt{n'^2 + n' + X'}$ という形になりました。最初の考察で $n$ の正のものをすべて見つけることと、負のものをすべて見つけることのどっちでも答えが求まることを見つけていました。そこで、 $n'$ が正のものをすべてみつけていこうという発想になりました。これで、 $X \ge 0$ の場合と全く同様に帰着できました。
if x >= 0 {
let mut ns = vec![];
for a in 0.. {
if x < a * a {
break;
}
ns.push((x - a * a) / (2 * a - 1));
}
}
ns.sort();
ns.dedup();
let mut ms = ns.clone();
for i in 0..ms.len() {
ms[i] = -ms[i] - 1;
}
ns.append(&mut ms);
ns.sort();
ns.dedup();
println!("{}", ns.len());
println!("{}", ns.iter().join(" "));
} else {
let x = -x;
let mut ns = vec![];
for a in 0.. {
let a = -a;
if (x + a * a) % (2 * a - 1) == 0 {
ns.push((x + a * a) / (2 * a - 1) - 1);
}
if x < a * a {
break;
}
}
ns.sort();
ns.dedup();
let mut ms = ns.clone();
for i in 0..ms.len() {
ms[i] = -ms[i] - 1;
}
ns.append(&mut ms);
ns.sort();
ns.dedup();
println!("{}", ns.len());
println!("{}", ns.iter().join(" "));
}
実装が思いつきでやっていたので、とても汚いです。
F. kirinuki
累積和っぽい！と思ってから、普通に計算量が落ちませんでした。こういう問題は調和級数による計算量解析が有効そうだなとも思っていました。解説を見ると知らない知識が載っていました。悲しい。
総括
考察自体はかなりスムーズでしたが、実装に入るまでにどのくらい考察するかみたいなところのチューニングがあっていなかったなと思います。ペナルティも多く、せっかくの得意回でレートを伸ばせなくて残念でした。
実装が重ためな問題こそ、コーディングをサボれる部分はサボらないと変なコードを書いてしまいます。提出する時に一回落ち着いてコード全体を見てみるなどもしっかりと取り入れていきたいなと思いました。