ganmo::cout

競技プログラミング始めました

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

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

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

*3:ARCが併設されないABC