あらかじめ、市松模様上に色を反転させておく。すると後は、黒一色の長方形と白一色の長方形の面積の最大値を求める問題になる。最大の長方形面積を求める問題は \( O(WH) \) の解法があるが、そこまでに頑張らなくても \( O(W^2H^2/4) \) の全探索で十分間…

本番では、嘘解法っぽい後ろからの貪欲の全探索で通したけど、合っている証明ができなかった。想定解法は、ミッションをRefuelの大きい順に順番を固定してから、動的計画法が適用する、というものだった。ミッションをRefuel の大きい順に並び替れば上手くい…