「AOJ2331 A Way to Invite Friends」の編集履歴（バックアップ）一覧に戻る
*AOJ2331 A Way to Invite Friends
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331]
**解説
以下の三種類の解法を示す
+いもす法
+セグメント木
+Fenwick木
***解法: いもす法
問題文は以下のように解釈してみると良いかもしれない。
まず人数を軸に取った数直線を考える。
入力で与えられるそれぞれの人が許容できる友達の人数を表す区間の線分を数直線に重ねてみる。
そのとき大きい区間が小さい区間を出来るだけすべて包含出来るように整理して重ねる。
>||
-------------------------------------> n人
------------------
-----------
--------------
--
-------
------------
||<
とあれば、
>||
-------------------------------------> n人
------------------ -----------
-- --------------
------------
-------
||<
とまとめるイメージをしてみる。これより、重なりのもっとも多い部分が誘える友達の人数でありそうだと思える。数字列に置き換えると
>|
00122123444444433332011111111111000000...
|<
これより上のような累積和を表す数字列を配列で示せれば、「基本的には」その配列の最大の値を見ると解が分かる。「基本的には」と書いたが、これについては後で詳しく追記予定。（上の例のような線分がうまく重なり合う以外に、上の線分が下の線分を包めないようなものがあるということ）
しかしO(N*T)の二重ループで実装するのは時間がかかり過ぎてしまうので別の方法を考える。
ここで、[http://imoz.jp/algorithms/imos_method.html:title=いもす法]を用いる。
まずそれぞれの許容できる友達の人数区間の最小と最大のみ考える。上の図で言うと線分の端点のみに着目している。
ここで例えばある人がa人以上b人以下が許容できるなら
>||
v[a]++
v[b+1]--
||<
として、あるa人以上b人以下の友達を許容出来る人の区間の端点情報のみ用いて、まずは求めたい配列上で数の増減のみを記録させておく。
ここで、b人までは許容できるがb+1人は許容できないのでv[b+1]においてデクリメントしているという意味があることに注意しておく。
このようにして例えば一人分の情報を用いると、以下のような1と-1のチェックが入った配列を得ることができる。
>||
00100000000000000000000000000000-1000000...
||<
これをN人分重ねて繰り返す。結果以下のような配列ができあがる O(N)
>||
00110-1111000000-1000-1-210000000000-100000...
||<
各数字に左隣の数字を足していくと目的の数字列を示す配列が手に入る O(T)
>||
00122123444444433332011111111111000000...
||<
結果O(N+T)で答えが得られそうである。
しかし注意点として最終的な解はhogehoge
***解法: セグメント木
（編集中）
***解法: Fenwick木
（編集中）
