AtCoder Beginner Contest 134 A-D - 今日から始める競プロ日記
はじめに
ABC 134 (2019/07/20) に参加。
今日はD問題まで。Eで時間切れ。
Eは簡単そうだなと思いながらも、 Dの実装で時間を使い過ぎてて、コンテストが終了した。
まずDをちょっと勘違いしてて実装でこけて3WAしたし、 そもそも問題文を理解するのに時間が無限に必要だった。
紙とペンをちゃんと用意してメモを取ろう。 頭の中だけだとごちゃごちゃになる。
それでもレートは上がったから嬉しい。
結果
- パフォーマンス：935
- レート：686 → 715 (+29)
解いた問題たち
A - Dodecagon
半径rの円に内接する正十二角形の面積が3r^2であることを初めて知った。
3r^2を計算するだけの問題。
B - Golden Apple
監視員はある地点に立つと、そこから± Dの範囲だけ監視できる。
つまり、監視員一人で2D + 1の範囲をカバーできる。
1～Nまでの範囲を監視するには、監視員は何人必要か、という問題。
単純に計算するとN / 2D + 1だけど、小数点を切り上げる必要がある
（例：7/3=2の場合は+1して答えを3にしたい）。
解説によるとA / Bにおいて切り上げるにはA + B - 1 / Bとなる（頭いい）。
よって答えはN + 2D / 2D + 1で求められる。
解説はスマート。
私は2で割り切れるかどうかで場合分けした（ごり押し）。
C - Exception Handling
長さNの配列A[1]～A[N]が与えられる。Aの中身は整数。
任意のiにおいて、A[i]を除いたとき、それ以外のN-1個の中で最大の値を答える問題。
一番大きい値と二番目に大きい値が分かればいい。
ソートが一番楽そう。
D - Preparing Boxes
問題を理解するのが大変な問題。
（したがって問題内容は省略）
後ろ半分はボールを入れるかどうか初めから確定できるから、 後ろからやればいいということはすぐに分かった。
さらにいうと計算量がO(NlogN)だということもなんとなく分かった。
だけど後ろから順番にやるだけで良かったところを、 なぜか「半分ずつやる必要がある」と思い込んでしまって無駄な実装をしていたら3WAしたし、時間も溶けた。
最後はちゃんと通せてレートも上がったから結果オーライではある。
おわりに
レート上がって良かった
