読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2176 For the Peace

AOJ

多分英文を読解するのに一番時間を費やしたと思います(真顔)

問題概要

問題文:For the Peace | Aizu Online Judge

n個の国がある.
各国はそれぞれ威力の異なるミサイルを順に作る予定である.
世界の均衡を保つため,いかなる瞬間においても各国がもつミサイルの威力の総和の最大値と最小値の差はd以下で保たれなければならない

各国がどのような順番でどんな威力のミサイルを作成するかのリストが与えられる.
これらのリストは独立で,異なる国の間でのミサイルの作成順序は分かっていない.
どの瞬間においても世界の均衡が保たれるようなミサイル作成パターンが存在するか答えよ.
1 \le n \le 100
1 \le d \le 1000
ミサイルの数の総和は10000以下

解法のような言い訳

ab番目までのミサイルを作ったときの威力の総和をP(a,b)とおく.
dp(k,i):=P(k,i)がどの国のミサイルの威力の総和よりも最小で,国kが次のミサイルを作成した場合,最終的にゴールにたどりつけるか
というようなDPを考える
まずどの国よりもP(k,i)が最小であることを考えたとき,他の国はP(k,i)+dを超えないギリギリまでミサイルを貪欲に作っても大丈夫そうな気がしてきますよね.
で,限界ギリギリまで各国のミサイルを作った後,国kのミサイルを1個作ります.
ここで全ての国がミサイルを作り終えた状態ならdp(k,i)=OKが確定です.
このとき制約を崩してしまった場合はdp(k,i)=NGが確定します.
制約を崩さなかった場合,次に解く候補はその時点でミサイルの威力の総和が最小となる状態です.
これをDFSっぽく走査してDPの表を埋めていきます.
メモ化再帰をし,どこまでミサイルを作ったかのリストを伝播させていくことによって,
おそらくO(ミサイル個数の総和*n)ぐらいの計算量になります.
計算量の解析ガバガバですけど多分正しいです()

貪欲で解けます.
どういう貪欲かというと,あるミサイルをその時に開発して,均衡を崩さないなら開発する.を繰り返すだけです.
なぜうまくいくのか背理法っぽく解説をします.
開発しても均衡が崩れないあるミサイルがあったとします.
そのミサイルを作らず他の国がミサイル開発をするとすると,
それを持っている国がもしすべての国の中でミサイル力が最小ならば,ミサイルを作らないことにより下限が更新されないため
その国がボトルネックとなり他の国が最終的にミサイルを作れなくなります.
その国が最小でなかったとしても,いずれ他の国がミサイルを開発していくと最初になりボトルネックとなります.
下限はできるだけ大きいほうがほかの国も作りやすいので,作れるだけ作る.という単純な解法が最適になります.


単純に実装するとO(n^2m)ぐらいになりますが頑張るとO(nm)でできます.