Day1 Fish 解説
--問題--
N匹の魚の体長と色(赤，青，緑のいずれか)が与えられる．
ここから1匹以上を選んで飼うとき，色の組み合わせは何通りあるか．
ただし，体長が2倍以上違う魚はでかいのが小さいのを食う(cf. IOI'08)ので同時に飼えない．
例：入力例1
体長 10 4 8 5
色 R G B B
-->「赤1匹」「緑1匹」「青1匹」「赤と青1匹ずつ」「緑と青1匹ずつ」「青2匹」の6通り
（たとえば「赤と緑1匹ずつ」は無理：体長10の魚は体長4の魚を食ってしまう）
--最も安直な解法--
魚の(空でない)部分集合(2^N-1通りある)を全部試す --- 5点
--アイデア1--
入力例1だと魚が少なくて寂しいのでもうすこし魚を増やした次のような例で考えてみる．
名前 a b c d e f
体長 4 5 7 8 9 15
色 R B B G G R
・魚a~cまではすべて同時に飼える --> 「赤1匹以下，緑0匹以下，青2匹以下」の組み合わせは全部作れる
・魚b~eまではすべて同時に飼える --> 「赤0匹以下，緑2匹以下，青2匹以下」の組み合わせは全部作れる
・魚c~eまでは…
・魚d~fまでは…
・魚e~fまでは…
・魚f~fまでは…
これを利用すれば安直にやってもO(N^4)で数えられる
もっとうまく数えたい
--アイデア2--
+-----+-----+
/ / /|
+-----+-----+ |
/ / /| +
+-----+-----+ |/|
| | | + |
| | |/| +
+-----+-----+ |/|
| | | + |
| | |/| +
+-----+-----+ |/
| | | +
| | |/
+-----+-----+ この図がなんだかお分かりいただけるであろうか．
これは「赤1匹以下，緑2匹以下，青1匹以下」の組み合わせすべて(12通り，ただし1匹も飼わない場合を含めた)を図示したものである．
+-----+-----+
/0,2,1/1,2,1/|
+-----+-----+ |
/ / /| +
+-----+-----+ |/|
| | | + |
|0,2,0|1,2,0|/| +
+-----+-----+ |/|
| | | + |
|0,1,0|1,1,0|/| +
+-----+-----+ |/
| | | +
|0,0,0|1,0,0|/
+-----+-----+ こういうことです(「赤がr匹，緑がg匹，青がb匹」をr,g,bと書いています)
求めたいのは，こういう直方体たちの和集合の体積 (から1を引いたもの) である．
==直方体たちの和集合イメージ図==
+---------+
/ /|
/ / |
+---------+ |
| | +--------+
+------+ | / /|
/ /| |/ / +-----+
/ / ;--+ / / /|
+------+ +-----------+ +-----+ +
| | | | | |/
| | | | +-----+
| | | |/
| | +-----------+
| |/
+------+
こういうのの体積を求めればよいので，各々の高さでの断面積がわかるといい．
+--+--+----+----+---+-->
| | | | | |
+--+--+----+----+---@
| | | | |
+--+--+----@ |
| | | |
+--+--+---------@
+--+--@
| |
| |
+--@
|
V
このような，長方形の和集合の面積が求められるとよい．たとえばO(N*logN)で可能 --> O(N^2*logN)
--アイデア3--
アイデア2の方針をさらに改良することができる：
断面を上から順に求めていくことにすると，求めたい断面はつねに直前に求めた断面に長方形を1個追加したものになる．
--> そのような場合に対して面積の変化が爆速で計算できればよい
+-------------------+-->
| |
| +---@
| |
| |
| |
| +---------@
| +--@
| |
| | o <-- たとえばこの点を追加するとします
+--@
|
V
+-------------------+-->
| |
| +-+-@
| | |
| | |
| | |
| +---------@ |
| +--@ |
| | |
| +--------------o
+--@
|
V
+-------------------+-->
| |
| +-@
| |
| |
| |
| ; |
| ; |
| |
| +--------------o
+--@
|
V
・更新される区間の両端は，たとえば現在の頂点の座標たちをstd::setなどでもっておけばO(logN)で計算できる．
・各々の長方形の頂点は1回setに入れられたあと高々1回消される
--> O(N*logN)
点数分布
100
100
40
30
30
15
15
15
15
15
10
5
0
0
0
……