「AOJ2331 A Way to Invite Friends」の編集履歴（バックアップ）一覧に戻る
*AOJ2331 A Way to Invite Friends
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331]
**解説
以下の三種類の解法を示す
+いもす法
+Segment Tree
+Fenwick Tree
***解法: いもす法
[いもす法: http://imoz.jp/algorithms/imos_method.html]
問題文は以下のように解釈してみると良いかもしれない。
まず人数を軸に取った数直線を考える。
入力で与えられるそれぞれの人が許容できる友達の人数を表す区間の線分を数直線に重ねてみる。
そのとき大きい区間が小さい区間を出来るだけすべて包含出来るように整理して重ねる。
>||
------------------------------------ n人
------------------
-----------
--------------
--
-------
------------
||<
とあれば、
>||
------------------------------------> n人
------------------ -----------
-- --------------
------------
-------
||<
とまとめるイメージをしてみる。下にあるものがより上にある線分をはみ出さないように注意する。
これより、重なりのもっとも多い部分が誘える友達の人数であると分かる。数字列に置き換えると
>|
00122123444444433332011111111111000000...
|<
