http://yukicoder.me/problems/6

  • まず、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に上がっている解説ですと、範囲集合を事前にソートするとしていますが、それは必ずしも必要ではありません。逐一マージすれば良いからです。

  • マージするには、二分探索で右側を求め、左側と重なっているかチェックして、右側はいくつ先まで重なっているかもチェック。それらを消して、新しい範囲を挿入すればよいです。

  • 事前にソートしない利点として、以下のように変形した問題も容易に解けることが上げられます。

  • 「N個の初期位置が与えられる。あなたは与えられた順番通りにN匹のアメーバを数直線上に配置する。配置されたアメーバは、分裂を開始してT秒後に停止する。停止するまで次のアメーバを配置することはない。さて、i番目のアメーバが停止した時点で合計何匹のアメーバが数直線上に存在するか?」
  • この考え方を使うことで解ける問題があります。そう、CODE FESTIVAL 2015 予選B D問題 (マスと駒と色塗り)です。

    • なお、残念ながら、この問題は制約が大きいため、Ruby/PythonだとTLEします。PyPy/Crystalは導入されていないため、通るかはわかりません。ただ、C++でもset解法でなければならず、deque解法は75点(ちなみにvectorは40点)だったので、通る可能性は低いかもしれませんが。
    • あと、if(l<=left->second+1)の「+1」は必須。
    • http://code-festival-2015-qualb.contest.atcoder.jp/submissions/549169
  • ※ ついでに言うと、CheckiO Painting Wallも逐一マージが想定解です。