AtCoder Beginner Contest 023 C D
C
図に書いてみると、行と列にどれぐらい点があるか着目すればよさそう。
このとき、
- i行にある点がc[i]個のとき、k-c[i]となる列の中から点そのものでない（クロスしたところ）を数える
- i行にある点がc[i]個のとき、k-c[i]+1となる列の中から点そのものを数える
とすれば解がもとまる。
これを愚直に実装すると部分点がもらえる。
Submission #985894 - AtCoder Beginner Contest 023 | AtCoder
点そのものの数を高速に求めるには、(i行目, j列目の点の数, j)としたデータを
ソートしてバイナリーサーチをすればよい。
counterをlongにするのを忘れずに。
Submission #985917 - AtCoder Beginner Contest 023 | AtCoder
考察メモ
D
二分探索の典型。解を決めるとそのペナルティ内に全部撃ち落とせるかどうかの判定問題になる。
愚直に実装するとO(n^2 log sn) で部分点。
Submission #986020 - AtCoder Beginner Contest 023 | AtCoder
ここで、
h[j] + s[j] * i > mid
は
i = (mid - h[j]) / s[j]
と式変形できる（iは次のタイミングでペナルティを超えるとき）。
これをlistに突っ込んでソートすれば、前から順々に見ていけばいい。
これでO(n log n log sn)。ちょっと危険だけど制限時間は5sec。
Submission #986082 - AtCoder Beginner Contest 023 | AtCoder
昔解けなかった問題が解説も見ずに解けて成長を感じる・・・。
ちょっと嬉しい。
C問題には2015年5月9日（たぶんコンテスト日）にチャレンジしてWAをもらったみたい。
