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

AtCoder Regular Contest 073 E - Ball Coloring

長らく解けなかったので掲載。

問題概要

N組の2個のボールの組が与えられる。各組の片方を赤、もう片方を青に着色していったとき、赤のボールの範囲*青のボールの範囲の最小値を求めよ。

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder

 解説

AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説 - はまやんはまやんはまやんを参考にしています。AtCoderの解説準拠です。

ボールを2色に分けるのですが、全体の最小値と最大値は必ずRmax、Rmin、Bmax、Bminのいずれかに属します。よって最大値と最小値がどちらに属するかで場合分けします。

  • 最大値と最小値が異なる色のとき 最大値を赤、最小値を青とします。ここで、赤は小さいほう、青は大きい方を求める必要があります。赤の最小値を大きく、青の最大値を小さくすればいいのですが、これは色を塗るときに組の大きいほうを赤、小さいほうを青に塗ればよいです。
    ということで、各組の大きいほう、小さいほうからのみなる配列を作って、その最大値-最小値をかければOKです。

  • 同じ色のとき 赤が最大値、最小値両方占めたとしましょう。すると、残りのN-2組から任意に片方だけ抜いていった時の最大値-最小値が小さくなればよさそうです。取り敢えず全部の組で小さいほうを選んだとして、その後値の小さい組から入れ替えていって、入れ替え後に最小値が大きくなる間更新し続けます。(逆に大きいほうだけを抜き出し、最大値を減らしても求める)。参考にしたurlでは一気にセグメント木で殴っていたので、自分もそうさせていただきました。

Submission #1259798 - AtCoder Regular Contest 073 | AtCoder

感想

最初、x,yが出ていて、「(x,y)か(y,x)に点を置いていくときに、点すべてを中に含む長方形の面積の最小値を求めよ」という風に解釈して苦労したのですが、こっちの考え方で解いた強者いらっしゃいますかね…