↑こちらも読んでみてください．

AGC020 B問題について書きます．

目次！

B : Ice Rink Game

B : Ice Rink Game

B - Ice Rink Game

問題概要

子供が $N$ 人いる．
$K$ ラウンドからなる「n人組作って～♪」ゲームをする．
「n人組」を作ると中にはあぶれちゃう子も出てしまう．そのような子は脱落する．
$K$ ラウンド終了したとき，残った子供は二人だったという．
あなたはこのゲームを傍から見ていたので，「このゲームが何ラウンド行われたか( $K$ の値)」と「各ラウンドにおいて作る『n人組』のnの値」を知っている
あなたはこの情報からもともといた子供の数を推測してみたくなった

答えるべきもの

$N$ の最小値と最大値
$N$ として適切なものがない場合は $-1$ と出力

制約

$1\leq K\leq 10^{5}$
$2 \leq A_{i} \leq 10^{9}$ ただし， $A_i$ とは第 $i$ ラウンドにおいて作る『n人組』のnの値

解説

僕がこの問題を解いたときの思考過程をなぞりながら書きます．

具体例で考える

まずこの問題文を読んだ時に思ったのが「よくわからん」だったので，例で確認してみました．

入力例1

4

3 4 3 2

全部で4ラウンドあり，『3人組』→『4人組』→『3人組』→『2人組』の順でグループを組んでいきます．

この時，出力が

出力

6 8

でした．実際に計算してみると， f:id:kebobokawawan:20180117145911p:plain となります．確かにあっていそうです．

求めるものは $N$ なので今度はこの例を用いて6,8を出す作業をやってみようと思いました．

$N$ の最小値は6だったので，6を求める作業をしていきます．

この表は各ラウンドにおいて「ラウンド終了時の子供の人数」と「ラウンド開始時の子供人数」と「作る組の人数」を表にしたものです．

赤色の文字は与えられた数値です．ゲームを開始する前は第0ラウンドということにしました． f:id:kebobokawawan:20180116225242p:plain

最終ラウンドである4ラウンド終了時の子供の人数が2なので，4ラウンド開始時には子供は2人いるか3人います．

もし，4ラウンド開始時に子供が2人いたなら，それはすなわち3ラウンドの終了時に残った子供が2人ということです．

f:id:kebobokawawan:20180117145955p:plain

しかし，これはありえません．3ラウンド終了時に残った子供が2人だけという状況がありえないからです．

3ラウンドでは『3人組』を作れという指示だったので，少なくとも3人は子供が残ります．(後の重要な伏線)

では4ラウンド開始時に子供が3人いたとしましょう．

f:id:kebobokawawan:20180117150018p:plain

これは正しいです．

では次に3ラウンド開始時(2ラウンド終了時)の子供の人数を考えてみます．候補は3人，4人，5人のいずれかになります．

f:id:kebobokawawan:20180117150037p:plain

6人以上だとすると3ラウンド終了時に6人以上残ってしまいます．

6人以上はあり得ない f:id:kebobokawawan:20180117150057p:plain

今回の場合，4人の場合のみありえます．

2ラウンドでは『4人組』を作れという指示だったので，残る子供の数は4人以上ですし，必ず4の倍数になっていないといけません．

f:id:kebobokawawan:20180117150136p:plain

こんな感じで表の数字を埋めていくと次のようになりました． f:id:kebobokawawan:20180116231752p:plain

一般的に考えてみる

具体例でこの作業をしているとこのゲームの仕組みが分かってきました．一般的に論じてみます．

f:id:kebobokawawan:20180116232708p:plain

第 $i$ ラウンド終了時の子供の人数を $x$ 人とすれば， $x$ は $A_i$ の倍数である
第 $i-1$ ラウンド終了時における子供の人数は $x+p$ 人である
$0\leq p \leq A_i -1$ である． $p$ とは $x+p$ を $A_i$ で割ったときの余りである．
$x+p$ は $A_{i-1}$ の倍数である

ここまで整理すると解法が浮かびました．

各第[text:i]ラウンドの子供の人数 $x$ と $A_i$ と $A_{i-1}$ から $x+p^{(i)}$ として適切な $p^{(i)}$ を全てリストアップして，その中でも最小のものを $p_{min}^{(i)}$ として最終的には $2 + p_{min}^{(K)} + p_{min}^{(K-1)} + \cdots + p_{min}^{(1)}$ を計算すれば，もともといた子供の最小値が求められます．

最大値は適切な $p^{(i)}$ のなかで最大なものを考えていくだけです．

ただし，この解法は正しい答えが出せても時間制限という壁にぶつかります．

この解法だと，プログラムは二重ループになってしまうため答えをだす制限時間である2秒をいとも簡単に超えてしまいます．

コンテストに参加しているときはこのあたりまでわかったところで時間切れになりました．

pをループ無しで求めるには

解説のpdfに書かれているのはここからの話です．しかし，式だけ書かれている感じなのでここではそれをさらに詳しく書こうと思います．

https://img.atcoder.jp/agc020/editorial.pdf

再び具体例で考える

第 $i$ ラウンド終了時における子供の数として考えられる値はいくつかあるはずです．そこで第 $i$ ラウンド終了時における子供の数の最小値を $X_i$ とし最大値を $Y_i$ とします

先ほどまでと文字の使い方は同じにして， $X_{i}=4,Y_{i}=8,A_i = 4,A_{i-1}=2$ としてみます．

$L_{i}$ f:id:kebobokawawan:20180117150254p:plain $R_{i}$

$p$ の候補は0,1,2,3です．それぞれの場合において $X_{i}+p$ は4,5,6,7であり $Y_{i}+p$ は8,9,10,11です．よって， $X_{i-1}$ は4であり $Y_{i-1}$ は10です．

具体例だと直観的にわかってしまいますがポイントは適切な $p$ を考える前にまずは $X_{i}+p$ および $Y_{i}+p$ のとりえる値を考えているということです．

$X_{i}+p$ の最小値を $L_{i-1}$ とし， $Y_{i}+p$ の最大値を $R_{i-1}$ と置きます．

区間 $[L_{i-1},R_{i-1}]$ というのは $i-1$ ラウンド終了時においてあり得るかもしれない子供の数になります．この区間の値で $A_{i-1}$ の倍数となっているものを見て，その中の最小のものと最大のものを選んでそれぞれ $X_{i-1}$ ， $Y_{i-1}$ とするのです．

一般で議論する

第 $i$ ラウンド終了時において子供の数の最小値を $X_{i}$ ，最大値を $Y_{i}$ とします．再び述べますが，組の数が $A_{i}$ であるとき，第 $i-1$ ラウンドにおいてありえるかもしれない子供の数は区間 $[L_{i-1},R_{i-1}]$ で表されます．この区間で $A_{i-1}$ の倍数である最小の数と最大の数を見つけていきます．