E - Ball Coloring

700点問題解説AC

典型っぽさはあったんですが、うまく考察を詰め切れませんでした。

問題：ｎ個のpairがそれぞれどちらかを青、他方を赤に塗る。青の範囲と赤の範囲の長さの積を最小化せよ

解説：

まず、小さいほうを片方に寄せることを考える。

そうでないとき、片方が大きく、もう片方が小さいという形になる。

もし中途半端なときどちらかを維持しつつもう片方を短くできる。

片方を大きくしたとき、もう片方を全部小さいほうにする。

この範囲をどう小さくするかを考える。

範囲の端点をpairの相手に変えるとき、特にこの場合は小さい側を大きいものに置き借る。そうすると、範囲が右側にずれて小さくなるか大きくなる。

これを繰り返して、範囲が最小の長さになるところが最適値である。

上のものと比べて小さいほうを出力する

感想：

範囲の最小化で、端点だけうまくいじるのは典型っぽく思えました。

どちらかに寄せておくのは自分でも考えつけたので良かったです。

だいたいの方針は当たったんですけど、最後の詰めが難しかったです。これは思いつきたかった感。