Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383） - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

コンテスト時間: 2024-12-07(土) 21:00 ~ 2024-12-07(土) 22:40 (100分)

A - Humidifier 1

Difficulty: 19

解答時間: 6:11

加湿器が1つあり、時刻 $0$ の時点で水は入っていない。これからこの加湿器に $N$ 回水を追加することを考える。 $i$ 回目の水の追加は時刻 $T_i$ に行い、水を $V_i$ リットル追加する。ただし、加湿器には穴が空いていて、加湿器に水が入っている間は単位時間につき水が $1$ リットル減り続ける。時刻 $T_N$ に水を追加し終えたとき、加湿器に残っている水の量を求めよ。
前回水を追加した時間を $l$ とすれば、 $T_i$ で水を追加するときに事前に $T_i - l$ を引くことで、穴から出た水の量をシミュレーションできる。
途中で水の量がマイナスになったときは $0$ に戻すのを忘れないこと。

B - Humidifier 2

Difficulty: 272

解答時間: 11:37

$H \times W$ のマス目 $S$ があり、 $S_{i, j} =$ #のときは机が、.のときは床である。なお、床のマスは必ず2つ以上存在する。床のマスから異なる2マスを選び、加湿器を設置する。加湿器が設置されたとき、あるマス $(i, j)$ は、加湿器があるマス $(i',j')$ からのマンハッタン距離が $D$ 以下であるときに限り加湿される。ここで、加湿器が置かれた床のマスも必ず加湿されている。このとき、加湿される床のマスの個数として考えられる最大値を求めよ。
マス目の広さは最大でもなので、地道に全探索で解けそう。具体的には以下の通り。
- 床のマス目を事前に配列 [tex v] に格納しておき、その中から2か所 (マスとする) を選ぶ。
  - $a, b$ それぞれを基準に、 $v$ の要素1つ1つとのマンハッタン距離を計算。 $D$ 以下ならカウンターを1増やす。
- 上の操作を行って得られるカウンターの最大値を出力。

C - Humidifier 3

Difficulty: 750

解答時間: 6:51

$H \times W$ のマス目 $S$ があり、 $S_{i, j} =$ #のときは壁、.のときは床、Hのときは加湿器である。あるマスは、ある加湿器から壁を通らず上下左右に $D$ 回以下の移動で辿り着ける場合加湿される。ここで、加湿器が置かれた床のマスは必ず加湿されている。このとき、加湿されている床のマスの個数を求めよ。
Hの各マスから $D$ 回の上下左右移動で到達できるマスが加湿されることになる。これは BFS によってすべて探索できる。
こういうのを多始点 BFS というらしい。

D - 9 Divisors

Difficulty: 884

解答時間: 9:52

$N$ 以下の正整数のうち、正の約数をちょうど9個持つものの個数を求めよ。
ある整数が正の約数をちょうど9個持つのは、次の2つの場合である。
- ある素数 $p$ を用いて、 $p^8$ と表される。
- ある2つの素数 $p, q$ を用いて、 $(pq)^2$ と表される。
どちらも素数が関わっているので、エラトステネスの篩を用いて、2つの場合それぞれに対して候補となる素数を列挙していくことにする。ここで、1つめのパターンについては $N^{\frac{1}{8}}$ 、2つめのパターンについては $\sqrt{N}$ まで列挙すれば十分。
あとは、それぞれの候補について実際に条件を満たしているかを確認して個数を数えれば OK 。
みんな尺取りって言ってるけど、別に要らないよな...？

結果

Performance: 1374

Rating: 693 → 782 (+89)

今回はC, D問題をかなり早く解くことができ、初めての水 Perf を取ることができた。次回入緑も夢ではない...？