脳log[20220609]

2022年06月09日 (木) [AtCoder] 精進。ABC116-D「Various Sushi」(ギリギリ青 diff)。K 個の総和を大きくしたいけど種類ボーナスがあるせいで若干の番狂わせがあるのをどうするか。とりあえず種類を気にせず大きいものから K 個取る。K 個で K 種類あるならそれまで。種類数が少ないなら、N-K 個の余りからおいしさが大きい順に、種類数が増える限りにおいて、入れ替えてスコアを再計算してみる。入れるもの出すものの選択は貪欲法でいい。■提出 #32335682 (AC / 338 Byte / 238 ms)。二分探索かなとか種類数を固定して考えるのかなとか、種類数を決めても種類の取捨選択で試行錯誤ができないのをどうするかなとか、わりと考えた。考えた結果が「(種類数を増やすにあたり)入れるもの出すものの選択は貪欲法でいい」。■ブログを読んでいると、種類数「の最低ライン」を決めてそれを満たすように X 種類 X 個を選んだあとで、残り K-X 個を無差別に選ぶのでも良かったらしい。種類数を固定するのではなく、種類数の最低ラインを固定する。ただ、こちらは効率的な実装が難しい気がするな。ソート列を２本持って、１本目から X 個取ったあとで、両方から K-X 個を取るような……。あ、Ruby で最速 207 ms の提出 #5420937 における strong と yowai_sushi ってそういうことか(２本のソート列)。そして、その提出によれば２本のソート列から K-X 個を取るパートはない。１本目のソート列から X 個を超えて取る方が良くなるケースは、X を増加させた後のループで試行されるのを待てばいいのだから、それはそう。そしてだからこそ、40 行目 tmp = intstrong[t] + intyowai[k - t] + t*t において K 個の実際の種類数が t 種類より多くてスコア計算が不正確であっても(不当に低くても)無視して良い。難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは。