競技プログラミング

AtCoder AGC 020 B – Ice Rink Game(500点)

実行時間制限: 2 sec / メモリ制限: 512 MB

配点 : 500

問題文

スケートリンクで、一人の大人の司会と N 人の子供がゲームを行います。
ゲームは K ラウンドからなり、ラウンド i では司会が次のように言います。

  • A_i 人組を作って!

すると、まだ脱落していない子供たちは A_i 人からなるグループをできるだけ多く組みます。
一人につき一つのグループにしか入れません。
グループに入れなかった子供たちは脱落し、その他は次のラウンドに進みます。
ラウンドで誰も脱落しないこともありえます。

最後まで、つまりラウンド K のあとまで残ったのは 2 人で、彼らが勝者となりました。

あなたは A_1, A_2, …, A_K の値を聞き、N の値は知りませんが、推定してみたくなりました。

ゲームの開始前にいた子供たちの人数として考えられる最小の値と、最大の値を求めてください。もしくは、考えられる N の値は存在しないと判定してください。

制約

  • 1 <= K <= 10^5
  • 2 <= A_i <= 10^9
  • 入力値はすべて整数である。

考えたこと

素直にAを逆から見て行って、Nの値の最小値と最大値を更新していけばいいのではと考えました。

もし考えられるNの最小値と最大値の中にA_iの倍数がなかったら実現値なしということで-1を返せばよく、それ以外なら最小値は[最小の倍数]、最大値は[最大の倍数 + A_i – 1]となります。

この更新を繰り返して行ってやれば答えが求まります。

このアルゴリズムはO(K)で済みます。無事ACでした。

振り返り

僕の方法は線形走査というらしく、別解として二分探索があるみたいです(確かに単調性がある!)。

ソースコード