AtCoder Beginner Contest 116

初のunratedなABCでした。10分20秒で3完Perf1600（水色コーダーなのになにやってんだ）

A - Right Triangle (100点)

問題: A - Right Triangle
${\angle ABC = 90^\circ}$ なので、辺 $AB$ と辺 $BC$ が直角で、かつ三角形 $ABC$ の面積は整数であることが保証されているので、 $|AB|\times |BC|\div 2$ を出力すればAC。

拙解 (C++): Submission #4051815 - AtCoder Beginner Contest 116

B - Collatz Problem (200点)

問題: B - Collatz Problem
タイトルでググると*1まんまコラッツの問題なので、Wikipediaを見ると、少なくとも初期値が $5\times 2^{60}$ までの場合は必ず $f(n)$ の値は最終的に1に到達して、1→4→2→1のループに入る、とあるので、 $f(a_n)=1,2,4$ の時に $m=n+3$ を出力すればAC。

拙解 (C++): Submission #4052970 - AtCoder Beginner Contest 116

C - Grand Garden (300点)

問題: C - Grand Garden
これは「高さが $h_k$ の花に水をやることで高さが $1$ ずつ縮むときに全部の花の高さを $0$ にして消滅させる最小の回数」と読み替えることができるので、隣り合った $h_k\ge 1$ 以上の花にできるだけまとめて水をやって花を縮めると最小の回数になる。

拙解 (C++): Submission #4053693 - AtCoder Beginner Contest 116

D - Various Sushi (400点)

問題: D - Various Sushi
コンテスト中には解けなかった。Cまでを10分ちょいで終わらせて余裕ぶっこいていたらこのざまであった。
まずはボーナスを無視しておいしさ順に寿司をソートして、寿司各種ごとの先頭（つまり種類の中で最もおいしい寿司；「先頭寿司」と呼ぶことにする。その他の寿司を「一般寿司」と呼ぶことにする）にだけボーナスをあらかじめセットしておく*2。そうすると上から $K$ 個の寿司を食べたときの満足ポイントが計算できる。そして、ここからすでに食べた寿司のうち「一般寿司」の最もおいしくないものから食べず、食べなかった寿司のうち「先頭寿司」をおいしいものから食べていくとどうなるか、ということを該当する寿司がなくなるまで走査し、満足ポイントの最大値を出力すればAC。要するに、おいしい順に $K$ 個寿司を貪欲に食べて、そこから種類を増やして種類ボーナスポイントを増やしたときどうなるか、を全通り試している。こうすれば、ソートが $O(N log(N))$ 、走査が $O(N)$ で、 $N\le 10^5$ には余裕で間に合う。

拙解 (C++): Submission #4060890 - AtCoder Beginner Contest 116

まとめ

ac-predictorで順位表を見る限り、16分半以内に３完ができればMaxPerf (1600) が出ていたらしい…
最初コンテストが終わってからD問題のEditorial見てABCOnly*3にPriority Queueが要るってマジかよ…と思った矢先それが要らない解法を思いついた。やっぱりこれ400点問題だ

*1:AtCoderのABCの問題にはたまにタイトルが大ヒントになっているものがある。

*2: $n^2=\sum_{i=1}^n (2i-1)$