[yukicoder] アメーバがたくさん・n連勤 (and マスと駒と色塗り)

アメーバがたくさん

まず、N,D,Tを取得した後、アメーバの初期位置(e)を取得し、(e%D+D)%D(=mod)ごとに分けます。
「modごとに分け」て以降にDを考慮しなくても良いよう、分けられたアメーバは、その中で [(e-mod)/D-T,(e-mod)/D+T] という範囲(閉区間)に分裂するとします。
※言語によってはeが負だとバグるので、mod計算はきちんとやったほうが良いでしょう。
- Ruby/Pythonだとe//D-TでACですが、C++ではそうではない。

ここからが本題で、現在yukicoderに上がっている解説ですと、範囲集合を事前にソートするとしていますが、それは必ずしも必要ではありません。逐一マージすれば良いからです。
マージするには、二分探索で右側を求め、左側と重なっているかチェックして、右側はいくつ先まで重なっているかもチェック。それらを消して、新しい範囲を挿入すればよいです。
- Python2/3 http://yukicoder.me/submissions/4190
- Ruby http://yukicoder.me/submissions/56062
- C++
  - vector http://yukicoder.me/submissions/56075
  - deque <http://yukicoder.me/submissions/56074
  - set http://yukicoder.me/submissions/56079
  - dequeはvectorと比較しておおよそ定数倍の高速化が望めます。(cf: CODE FESTIVAL 2014 あさぷろD 枕決め)
  - この問題はNが小さいので実行時間の差があまり出ませんが、Nが大きいとvector > deque > setの順番に時間がかかることが如実にわかります。
  - 順序が重要ですので、当然ながらunordered_setは使えないことに注意して下さい。
- Crystal https://yukicoder.me/submissions/227018

事前にソートしない利点として、以下のように変形した問題も容易に解けることが上げられます。
「N個の初期位置が与えられる。あなたは与えられた順番通りにN匹のアメーバを数直線上に配置する。配置されたアメーバは、分裂を開始してT秒後に停止する。停止するまで次のアメーバを配置することはない。さて、i番目のアメーバが停止した時点で合計何匹のアメーバが数直線上に存在するか？」

先述の発展の考え方で解けますが、この問題は制約が大きいため、Ruby/PythonだとTLEします。C++でもset解法だと100ms切れますが、deque解法だとぎりぎりなので、Crystalも厳しそうです。(ちなみにvectorは4075点)
あと、if(l<=left->second+1)の「+1」は必須。
set gcc https://code-festival-2015-qualb.contest.atcoder.jp/submissions/2077679
set clang https://code-festival-2015-qualb.contest.atcoder.jp/submissions/2077677
deque gcc https://code-festival-2015-qualb.contest.atcoder.jp/submissions/2077680
deque clang https://code-festival-2015-qualb.contest.atcoder.jp/submissions/2077670

右に接する場合もマージしないといけないので、while(right!=se.end() && right->first-1<=r)の「-1」は必須となります。
- 逆にマスと駒と色塗りでは右に接する場合はマージしてはいけないことに注意してください。
set https://yukicoder.me/submissions/252271
deque https://yukicoder.me/submissions/252272
vector https://yukicoder.me/submissions/252273