AtCoder Beginner Contest 400に参加しました。
久々に負けてしまいました。Eにかなり苦しんでしまいました。
Dまではまあまあ早い気もするので、Eを高速に解きたかったですね。では、振り返りです。
問題の解き方
A. ABC400 Party
fn main() {
input! {
a: u32,
}
println!("{}", if 400 % a == 0 { (400 / a) as i32 } else { -1 });
}やるだけですね。 print文の中でif文を使う回数を減らしたい気がしています。このように型がめんどくなることが多いので。
B. Sum of Geometric Series
どうしてGeometric Seriesなのかがわかりません、と思っていましたが等比数列のことを幾何級数と言ったりするそうですね。知りませんでした。
fn main() {
input! {
n: u128,
m: u32,
}
let mut x = 0;
for i in 0..=m {
x += n.pow(i);
if x > 10u128.pow(9) {
println!("inf");
return;
}
}
println!("{}", x);
}途中でbreakをすれば良いです。Rust的には、saturatingでも良かったみたいですね。
fn main() {
input! {
n: u128,
m: u32,
}
let mut x = 0u128;
let mut t = 1u128;
for _ in 0..=m {
x = x.saturating_add(t);
t = t.saturating_mul(n);
}
if x > 10u128.pow(9) {
println!("inf");
} else {
println!("{}", x);
}
}こういうことです。こっちの方が綺麗かな。
C. 2^a b^2
見たときは驚いてしまいました。適当に包除原理をすれば良いのかなと思って、計算量的に \(a\) で探索すれば良いと思いました。が、 \(a\) は \(a \mod 2\) に包含されるので \(a = 1, 2\) のみを考えれば良いのですね。いい問題です。
fn main() {
input! {
n: u64,
}
println!("{}", sqrt(n / 2) + sqrt(n / 4));
}ところで、sqrt関数を毎回手書き実装しています。苦しいので、テンプレートにnth_rootみたいなのを追加してもいいなって気がしてきました。
こういう問題のコツとしては、いい感じにダブりを無くすorダブりを引くという操作が必要なところです。 \(b\) が奇数と限定する方法もありますね。いい問題だ。
D. Takahashi the Wall Breaker
見た瞬間に01BFSですね。エア前蹴りをするのは常に非効率なことがわかります。
fn main() {
input! {
h: usize,
w: usize,
s: [Bytes; h],
a: Usize1,
b: Usize1,
c: Usize1,
d: Usize1,
}
let mut que = std::collections::VecDeque::new();
let mut dist = vec![vec![!0usize; w]; h];
que.push_back((a, b));
dist[a][b] = 0;
while let Some((x, y)) = que.pop_front() {
let d = dist[x][y];
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 s[nx][ny] == b'.' {
if d < dist[nx][ny] {
dist[nx][ny] = d;
que.push_front((nx, ny));
}
} else {
let d = d + 1;
if dist[nx][ny] > d {
dist[nx][ny] = d;
que.push_back((nx, ny));
}
let nnx = nx.wrapping_add(dx);
let nny = ny.wrapping_add(dy);
if nnx < h && nny < w && dist[nnx][nny] > d {
dist[nnx][nny] = d;
que.push_back((nnx, nny));
}
}
}
}
}
println!("{}", dist[c][d]);
}
簡単ですね。wrapping_addに感謝をしています。ありがとうございます。
E. Ringo’s Favorite Numbers 3
400numbersが平方数なので、数が十分少ない典型ですね。これに気づくのに時間がかかりました。
fn main() {
input! {
q: usize,
ask: [usize; q]
}
let sieve = SieveOfEratosthenes::new(10usize.pow(6) + 100);
let mut ans = vec![];
for i in 2..=10usize.pow(6) {
let fact = sieve.factorize(i);
if fact.len() == 2 {
ans.push(i);
}
}
for &a in &ask {
let sqrt_a = sqrt(a);
let x = ans.lower_bound(&(sqrt_a + 1));
println!("{}", ans[x - 1] * ans[x - 1]);
}
}実装自体は簡単でした。ans配列にそのまま突っ込んだので、再度sqrtが必要になりました。upper_boundの存在を忘れていたので、lower_boundでウジウジしました。これも良くないポイントですね。
なお、erathosthenesパートがかなり遅そうで不安でした。特にfactorize(i)を全てのiに対して読んでいる点です。倍数約数ゼータ変換みたいなので、調和級数だろ！みたいなノリでやっていました。本当ですか？
F. Happy Birthday! 3
区間DPであることはわかります。時間がありませんでした。円環の問題をこのように扱うと楽になるんですね。開いて倍にするの良さそうなので、他の問題に応用できそうな感じがして好きです。
感想
終わってみるともっと早く解けた気がします。最近（ここ1週間）精進してないせいで実装が遅くなっていました。
Rustの所有権周りのお勉強を始めました。ライブラリをさらに高速にもしたいし、BTreeMapの所有権バトルに負けたことがあったので、、、
大胆予想
さて、400以降はHTTPレスポンスのエラー系ですね。A問題はこのネタが出るんじゃないでしょうか？
401はUnauthorizedなので、名前のsetが与えられて、ある名前がそのsetの元であればtrue, そうでなければfalseを返す問題が出ると思います。
これはCTAサンプルです。
内容を編集するか削除してください。
