IJPC-2 E問題解説
- 2. 問題概要 ? 以下のコマンドを処理してください ? ?回目のコマンドの時、?1～? ?の中で、? + ?で割った余り が?以上の値のものをすべて、 その数より大きい最小の ? + ?の倍数に置き換える ? ? ? の値を出力する ? ?1～? ? すべてに?を加える ? はじめ、 ?1～? ? はすべて0
- 4. 考察 ? ?回コマンドを行った時の各??の値を??,?とする ? そして、次の図を眺める ?0,1 ?0,2 … ?0,? ?1,1 ?1,2 … ?1,? ?2,1 ?2,2 … ?2,? … ? ?,1 ? ?,2 … ? ?,?
- 5. 考察 ? ?回コマンドを行った時の各??の値を??,?とする ? そして、次の図を眺める ?0,1 ?0,2 … ?0,? ?1,1 ?1,2 … ?1,? ?2,1 ?2,2 … ?2,? … ? ?,1 ? ?,2 … ? ?,? こ っ ち か ら 更 新 し て み よ う
- 7. 考察 ? ?1～? ?が与えられ、?座標が??の位置に??(?? ≧ ?)秒間 緑信号、??(1 ≦ ?? ≦ 10)秒間赤信号の信号を置くことを 考える。 ? ただし、 ?1 ≦ ?2 ≦ ? ≦ ? ? ? ?1, ?2, … , ? ?の順番でこれらを設置していくので、あると ころまで設置した際、時間0で0からスタートして?座標 が?の場所にたどり着くのはいつか毎秒1動くとき答えよ ? というクエリに答える問題になる
- 8. 考察 ? この問題において、各信号の色が変わる回数というのを 考える ? これは、?? + ??秒して、初めて緑と赤が終わるので、?回 目の信号にたどり着く時間としてありうるのが??秒から ?? + ?=0 ??1 ? ?秒の間であることより、 1 ≦ ?? ≦ 10である ことを利用すると、この周期は高々10(? ? 1)/(?? + ??) 回しか起こらず、?? ≧ ? より、高々10回しか変わることが ない
- 9. 解法 ? よって、新しい信号機が変わるたびに、各信号がいつに なったら状態が変わるかの値をsegtreeで管理すること により、各信号機にたどりつく時間を管理することができ る ? これで、各クエリに対して、最も近い信号機からの距離を 足してあげることで解くことができる ? ただし、このsegtreeはやや実装が重くバグりやすい ? 計算量 ?(10?????)