AtCoder Grand Contest 020：B - Ice Rink Game

問題

https://atcoder.jp/contests/agc020/tasks/agc020_b

考え方

考えていたこと

ナイーブに考えると i 回目のラウンド前にいた人数を x とするとラウンド後は f_{i}(x) = x - x\ mod\ k_i となることは分かる。1 回目のラウンド前にいる人数を N として f を順に k 回適応すると最終的な人数が決まる。 k 回適応したときの結果を g(N) = f_{k}(f_{k-1}(\cdots f_{1}(x) \cdots )) とすると求めるべき解は g(N)=2 を満たす最小/最大の N となる。

N はある区間上に存在することになるから二分探索で求められる... と考えたが、単純に評価関数を g(N)=2 であるかどうかとする二分探索はできない。区間であるから条件を満たさない区切りが区間の大きい場合と小さい場合の 2 種類存在するためである。

三分探索とかいけるか？と思ったけど、仮に条件を満たす区間の値を -1 としてそうでない区間の値を 0 とすると、そうでない区間がすべて 0 になるので正しく区間を絞ることができないのでダメである。

解説見た

g(N) \ge 2 \land g(N) \le 2 \Leftrightarrow g(N)=2 を用いることになる。

直感的には g(N) に単調性があると想定できるが、単調性がわからないと以下の評価関数を定義することができなさそう。一応示すと以下のようになる。

f_p(x+1)-f_p(x) = (x+1 - (x+1)\ mod\ p) - (x - x\ mod\ p) = 1 + (-1) \ mod\ p \ge 0 であることから f(x) について単調性が示せた。g は f の合成関数であることから同じく単調性を持つ。

g に単調性があることから以下が言える。

  • g(N) \le 2 なる N については単調であって、ある値 x までは条件を満たし、x よりも大きい値は条件を満たさない
  • g(N) \ge 2 なる N については単調であって、ある値 x までは条件を満たさず、x よりも大きい値は条件を満たす

よって、それぞれの最小/最大値が二分探索で求められることになる。

Submission #4388322 - AtCoder Grand Contest 020

どこに着目して考察するべきだったか

評価関数を工夫すると二分探索が適用できるようになる。区間の最小値、最大値を二分探索で求めたいときには応用できるかもしれない。

何がバグっていたか

得た知見(典型ポイント)

  • 二分探索の評価関数を工夫する
  • ある値x以下 かつ ある値以上 は ある値

類題