AGC020 B Ice Rink Game
↑こちらも読んでみてください.
AGC020 B問題について書きます.
目次!
B : Ice Rink Game
問題概要
- 子供が人いる.
- ラウンドからなる「n人組作って~♪」ゲームをする.
- 「n人組」を作ると中にはあぶれちゃう子も出てしまう.そのような子は脱落する.
- ラウンド終了したとき,残った子供は二人だったという.
- あなたはこのゲームを傍から見ていたので,「このゲームが何ラウンド行われたか(の値)」と「各ラウンドにおいて作る『n人組』のnの値」を知っている
- あなたはこの情報からもともといた子供の数を推測してみたくなった
答えるべきもの
- の最小値と最大値
- として適切なものがない場合はと出力
制約
- ただし,とは第ラウンドにおいて作る『n人組』のnの値
解説
僕がこの問題を解いたときの思考過程をなぞりながら書きます.
具体例で考える
まずこの問題文を読んだ時に思ったのが「よくわからん」だったので,例で確認してみました.
入力例1
4
3 4 3 2
全部で4ラウンドあり,『3人組』→『4人組』→『3人組』→『2人組』の順でグループを組んでいきます.
この時,出力が
出力
- 6 8
でした.実際に計算してみると, となります.確かにあっていそうです.
求めるものはなので今度はこの例を用いて6,8を出す作業をやってみようと思いました.
の最小値は6だったので,6を求める作業をしていきます.
この表は各ラウンドにおいて「ラウンド終了時の子供の人数」と「ラウンド開始時の子供人数」と「作る組の人数」を表にしたものです.
赤色の文字は与えられた数値です.ゲームを開始する前は第0ラウンドということにしました.
最終ラウンドである4ラウンド終了時の子供の人数が2なので,4ラウンド開始時には子供は2人いるか3人います.
もし,4ラウンド開始時に子供が2人いたなら,それはすなわち3ラウンドの終了時に残った子供が2人ということです.
しかし,これはありえません.3ラウンド終了時に残った子供が2人だけという状況がありえないからです.
3ラウンドでは『3人組』を作れという指示だったので,少なくとも3人は子供が残ります.(後の重要な伏線)
では4ラウンド開始時に子供が3人いたとしましょう.
これは正しいです.
では次に3ラウンド開始時(2ラウンド終了時)の子供の人数を考えてみます.候補は3人,4人,5人のいずれかになります.
6人以上だとすると3ラウンド終了時に6人以上残ってしまいます.
6人以上はあり得ない
今回の場合,4人の場合のみありえます.
2ラウンドでは『4人組』を作れという指示だったので,残る子供の数は4人以上ですし,必ず4の倍数になっていないといけません.
こんな感じで表の数字を埋めていくと次のようになりました.
一般的に考えてみる
具体例でこの作業をしているとこのゲームの仕組みが分かってきました.一般的に論じてみます.
- 第ラウンド終了時の子供の人数を人とすれば,はの倍数である
- 第ラウンド終了時における子供の人数は人である
- である.とはをで割ったときの余りである.
- はの倍数である
ここまで整理すると解法が浮かびました.
各第[text:i]ラウンドの子供の人数ととからとして適切なを全てリストアップして,その中でも最小のものをとして最終的にはを計算すれば,もともといた子供の最小値が求められます.
最大値は適切なのなかで最大なものを考えていくだけです.
ただし,この解法は正しい答えが出せても時間制限という壁にぶつかります.
この解法だと,プログラムは二重ループになってしまうため答えをだす制限時間である2秒をいとも簡単に超えてしまいます.
コンテストに参加しているときはこのあたりまでわかったところで時間切れになりました.
pをループ無しで求めるには
解説のpdfに書かれているのはここからの話です.しかし,式だけ書かれている感じなのでここではそれをさらに詳しく書こうと思います.
https://img.atcoder.jp/agc020/editorial.pdf
再び具体例で考える
第ラウンド終了時における子供の数として考えられる値はいくつかあるはずです.そこで第ラウンド終了時における子供の数の最小値をとし最大値をとします
先ほどまでと文字の使い方は同じにして,としてみます.
の候補は0,1,2,3です.それぞれの場合においては4,5,6,7でありは8,9,10,11です.よって,は4でありは10です.
具体例だと直観的にわかってしまいますがポイントは適切なを考える前にまずはおよびのとりえる値を考えているということです.
の最小値をとし,の最大値をと置きます.
区間というのはラウンド終了時においてあり得るかもしれない子供の数になります.この区間の値での倍数となっているものを見て,その中の最小のものと最大のものを選んでそれぞれ,とするのです.
一般で議論する
第ラウンド終了時において子供の数の最小値を,最大値をとします.再び述べますが,組の数がであるとき,第ラウンドにおいてありえるかもしれない子供の数は区間で表されます.この区間での倍数である最小の数と最大の数を見つけていきます.
したがって,区間内にの倍数がなければ-1
を出力しなければなりません.よって,まずはこれについて判定しなければならないのですがそれは後述します.
第ラウンドにおけるあり得るかもしれない子供の数は先ほどの議論よりでした.この区間の中での倍数の最小値がであり最大値がになります.
すなわち,
となります.
を構成した方法と同様にするとはそれぞれ,
すなわち,
となり,添え字をずらせば,
となり,解説pdf通りの式が完成します.
ゲーム開始時,すなわち第0ラウンドにおける子供数の最小値,最大値である,は必ずとなります.
なぜなら,第0ラウンドではとみることができるからです.
したがって,,に関する漸化式を1からKまで回せばよいことになります.
また,Kラウンドからさかのぼっていくため,各ラウンドにおける組のデータを入れた配列は逆順にソートしておくと扱いやすいと思います.
区間[Li,Ri]内にAiの倍数があることを判定する方法
区間内のすべての数字についてで割り切れるかどうかをチェックしていけばよい
というのが,最初に思いついた方法ですが,これもfor文でループを作らないといけないため結局全体として2重ループになります.
区間とが与えられた時,区間内のの倍数の有無を判定する方法で繰り返し処理を用いないものを述べます.(自力で考え付いたので書きたい)
まず
であるかどうかを調べます.もし,上記がTrue
ならば次に
になっているかどうか,すなわち
になっているかどうかを調べます.もしこれがTrue
ならば,区間内にの倍数はありません.
例
提出
紆余曲折ありましたが,以上のような議論を踏まえて私は次のようなコードを提出しました.
Submission #1983745 - AtCoder Grand Contest 020
こういうブログ書いてる暇があるならもっと他の問題を解いていきたいなって思いました.