「AOJ2331 A Way to Invite Friends」の編集履歴（バックアップ）一覧に戻る
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331
以下の三種類の解法を示す
問題文は以下のように解釈してみると良いかもしれない。
まず人数を軸に取った数直線を考える。
入力で与えられるそれぞれの人が許容できる友達の人数を表す区間の線分を数直線に重ねてみる。
そのとき大きい区間が小さい区間を出来るだけすべて包含出来るように整理して重ねる。
-------------------------------------> n人
------------------
-----------
--------------
--
-------
------------
とあれば、
-------------------------------------> n人
------------------ -----------
-- --------------
------------
-------
とまとめるイメージをしてみる。下にあるものがより上にある線分をはみ出さないように注意する。
これより、重なりのもっとも多い部分が誘える友達の人数であると分かる。数字列に置き換えると
00122123444444433332011111111111000000...
これより上のような累積和を表す数字列を配列で示せれば、その配列の最大の値を見ると解が分かる。しかしO(N*T)の二重ループで実装するのは時間がかかり過ぎてしまう。
ここで、いもす法を用いる。
まずそれぞれの許容できる友達の人数区間の最小と最大のみ考える。上の図で言うと線分の端点のみに着目している。
ここで例えばある人が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)で答えが得られる。
（編集中）
（編集中）
