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)に点を置いていくときに、点すべてを中に含む長方形の面積の最小値を求めよ」という風に解釈して苦労したのですが、こっちの考え方で解いた強者いらっしゃいますかね…

AtCoder Beginner Contest 057

競プロが絶不調の中、「下手すると全完出来ないかも」と思いながらやってました。 (コンテスト中は寝ていたので、終了後から解き始め、無事に1時間で全完出来ましたが) 今回はA〜CをPython2、DをC++で解いてます。

続きを読む

AtCoder Regular Contest 063

受験勉強の息抜き(やってる時点で浪人不可避な気がするけど気にしない)。久々だったのでコードがグダグダです。

一応1時間で3完できました。F問題は3分考えて何も浮かばないので離脱。残り時間でこちらを書いてました。

続きを読む

JPhO2016参加記

受験期だけあって、更新は適当です。

今回は、物理チャレンジ2016に参加してきたので、その様子を簡単に。なお、日記みたいな感じなので、詳細はJPhO速報ページ (http://jpho.jp/wp/)へ。

続きを読む