第７回日本情報オリンピック 本選（オンライン）：C - ダーツ

問題

https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf

P_1, P_2, \cdots, P_N から重複を許して 4 点選び、それが合計得点 S となる。ただし S が M を超えた場合は 0 となる。合計得点の最大値を求めよ。

制約

  • 1 \le N \le 1000
  • 1 \le M \le 2 \times 10^8
  • 1 \le P_i \le 10^8

考え方

「複数変数あるときに、ある 1 つを全探索して他をいい感じに求める」というテクを使う。O(N^2) で 4 点から 2 点を選ぶ組み合わせを求めておく。その中から 2 点を選ぶ。という方針で解が求める。

選ぶ 2 点をそれぞれ Q_i, Q_j とする。Q_i を選んだときに、 Q_i + Q_j \le M となるような最大の Q_j は Q_i が定まれば Q_j \le M - Q_i なる最大の Q_j である。これは二分探索で O(logN) で求めることができるので、全体の計算量は (N^2 \cdot log(N^2)) となる。

Submission #3872426 - 第７回日本情報オリンピック 本選（オンライン）

どこに着目して考察するべきだったか

全探索の枝刈りしか思いつくことができなかった。 1 \le N \le 1000, 1 \le P_i \le 10^8 では合計値の候補が多すぎて解を求めることができなかった。

4 点から 2 点に集約する。2 点に集約した後、1 点を全探索して、もう片方は二分探索なりで求めることが分かれば解くことができる。

何がバグっていたか

得た知見

  • 複数変数のうち、ある 1 つを固定する
  • N \le 1000 程度のときに O(N^2) で候補を求める

類題