かわわんの色々

数学とか自転車とか競プロとか音楽とか

AGC020 B Ice Rink Game

skbtkey.hatenablog.com

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

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

目次!

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

  1. 4

  2. 3 4 3 2

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

この時,出力が

出力

  1. 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人とすれば,xA_iの倍数である
  • i-1ラウンド終了時における子供の人数はx+p人である
  • 0\leq p \leq A_i -1である.pとはx+pA_iで割ったときの余りである.
  • x+pA_{i-1}の倍数である

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

各第[text:i]ラウンドの子供の人数xA_iA_{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}f:id:kebobokawawan:20180117150226p:plain

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}の倍数である最小の数と最大の数を見つけていきます.

したがって,区間[L_{i-1},R_{i-1}]内にA_{i-1}の倍数がなければ-1を出力しなければなりません.よって,まずはこれについて判定しなければならないのですがそれは後述します.

i-1ラウンドにおけるあり得るかもしれない子供の数は先ほどの議論より[L_{i-1},R_{i-1}]でした.この区間の中でA_{i-1}の倍数の最小値がX_{i-1}であり最大値がY_{i-1}になります.

すなわち,

\displaystyle X_{i-1} = \lceil\frac{L_{i-1}}{A_{i-1}}\rceil \times A_{i-1}

\displaystyle Y_{i-1} = \lfloor\frac{R_{i-1}}{A_{i-1}}\rfloor \times A_{i-1}

となります.

L_{i-1},R_{i-1}を構成した方法と同様にするとL_{i-2},R_{i-2}はそれぞれ,

L_{i-2} = X_{i-1}

R_{i-2} = Y_{i-1} + A_{i-1} -1

すなわち,

L_{i-2} = \lceil\frac{L_{i-1}}{A_{i-1}}\rceil \times A_{i-1}

R_{i-2} = \lfloor\frac{R_{i-1}}{A_{i-1}}\rfloor \times A_{i-1} + A_{i-1} -1

となり,添え字をずらせば,

L_{i-1} = \lceil\frac{L_{i}}{A_{i}}\rceil \times A_{i}

R_{i-1} = \lfloor\frac{R_{i}}{A_{i}}\rfloor \times A_{i} + A_{i} -1

となり,解説pdf通りの式が完成します.

ゲーム開始時,すなわち第0ラウンドにおける子供数の最小値,最大値であるX_{0}Y_{0}は必ずL_{0}R_{0}となります.

なぜなら,第0ラウンドではA_{0} =1とみることができるからです.

したがって,L_{i}R_{i}に関する漸化式を1からKまで回せばよいことになります.

また,Kラウンドからさかのぼっていくため,各ラウンドにおける組のデータを入れた配列は逆順にソートしておくと扱いやすいと思います.

区間[Li,Ri]内にAiの倍数があることを判定する方法

区間[L_{i},R_{i}]内のすべての数字についてA_{i}で割り切れるかどうかをチェックしていけばよい

というのが,最初に思いついた方法ですが,これもfor文でループを作らないといけないため結局全体として2重ループになります.

区間[L_{i},R_{i}]A_{i}が与えられた時,区間[L_{i},R_{i}]内のA_{i}の倍数の有無を判定する方法で繰り返し処理を用いないものを述べます.(自力で考え付いたので書きたい)

まず

L_{i} \verb|%| A_{i}\, != 0

であるかどうかを調べます.もし,上記Trueならば次に

L_{i} + (A_{i} - ( L_{i} \verb|%| A_{i} )) \in [L_{i},R_{i}]

になっているかどうか,すなわち

L_{i} +(A_{i} -  ( L_{i} \verb|%| A_{i} )) > R_{i}

になっているかどうかを調べます.もしこれがTrueならば,区間[L_{i},R_{i}]内にA_{i}の倍数はありません.

f:id:kebobokawawan:20180117150437p:plain

提出

紆余曲折ありましたが,以上のような議論を踏まえて私は次のようなコードを提出しました.

Submission #1983745 - AtCoder Grand Contest 020

こういうブログ書いてる暇があるならもっと他の問題を解いていきたいなって思いました.