問題概要
N人の子供がいて、
K回A_iの倍数に人数が切り捨てされる
最終的に2人残る
Nとして考えられる最大値、最小値を求めよ
解法
後ろから見ていき、もとの値として考えられる最大値、最小値を復元していく
例えばA = {4, 3, 4, 3, 2}とすると
最後から一つ手前の子供の人数は2以上3以下になる
なぜなら子供の人数が2よりも少ないか3よりも多いと、最後の人数が2人になることに矛盾するからである
その中で最小の3の倍数が最小値、最大の倍数が最大値になる
つまり最小値は3、最大値は3になる
その前を考えると、子供の人数の範囲としては
(前の最小値)以上、(前の最大値+(4-1))つまり3 \le x \le 7となり、
その中で最小の4の倍数4が最小値、最大の4の倍数4が最大値になる
一般に
min以上max以上のA_iの倍数をA_{i}dとおくと
min \le A_{i}d \le max
min/A_{i} \le d \le max/A_{i}
dは整数なので
\lceil min/A_{i} \rceil \le d \le \lfloor max/A_{i} \rfloor
\lceil min/A_{i} \rceil \cdot A_{i}が最小値、\lfloor max/A_{i} \rfloor \cdot A_{i}が最大値となる
仮に\lceil min/A_{i} \rceil \cdot A_{i} > \lfloor max/A_{i} \rfloor \cdot A_{i}ならばこの範囲にA_{i}の倍数は存在しないということで、-1を出力する
この結果より次の人数の範囲がわかり、\lceil min/A_{i} \rceil \cdot A_{i} \le x \le \lfloor max/A_{i} \rfloor \cdot A_{i} + A_{i} - 1となる
毎回の人数のありうる範囲を変数にもち、後ろからループを回していくことで答えが求められる
提出コード
https://atcoder.jp/contests/agc020/submissions/19692835
Discussion