第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）

　141位。

コンテストへのリンク

コンテスト後のツイート

第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）141位
x+yが大きい方から順に、
・z<=x,w<=yなる(z,w)から(x,y)を作る
・minx=min(x,z),miny=(y,w)とし、(minx,miny)から(x,y)と(z,w)を作り(minx,miny)を挿入
を全ての(z,w)について調べ、コストが一番低いものを選択。

— titia (@titia_til) September 15, 2024

　マージした後のx+yの値が一番大きくなるような二点をマージする（マージの仕方はツイートと同じ）……という貪欲が強かった。

　これを思いつかなくてはいけなかったのだが、厳しかった。

　座標が大きい方から考えるのが良さそう、とは思ったけれど、コストをパラメーターに考えたくなってしまう。座標が大きいものをマージしたらコストも低くなる、とは考えにくかった。