yukicoder No.78 クジ付きアイスバー
解法
1箱目と最後の箱はシミュレーションし,間の箱はまとめて処理する.
間の箱をまとめて処理するため,以下の事実を使う.
まず,
- n = 1箱に入っているアイスバーの数
- s = 1箱に入っている当たりの数の和(2本当たりなら2加算される)
とする.
このとき,
証明
1箱目の箱を全て「買った」か「当たりとして貰った」後に,
「買った数」と「当たりとして残っている数」をそれぞれ,x, y とする.
例えば,"2100"なら,(x,y)=(1,0),"0021"なら,(x,y)=(3,2)である.
このとき,
- x + s = 「買った数」+「1箱の当たりの数の和」 = 手に入れた(手に入れる予定の)アイスバーの数
- n + y = 「1箱のアイスバーの数」+「当たりとして残っている数」 = 手に入れた(手に入れる予定の)アイスバーの数
であることから,
x + s = n + y
が成り立つ.
n < s のとき
1箱目,すなわち,前の箱からの当たりの繰り越しが0なとき,x 回アイスバーを買う必要があった.
2箱目では,当たりの繰り越しが y である.
y - x = s - n > 0 から,y > x であることより,
1箱目で買う必要があった x 回のタイミング全てで,繰り越し分 y を利用する事ができる.
よって,2箱目で新たにアイスバーを買う必要がない.
3箱目における2箱目からの繰り越し分は y よりも大きくなるので,3箱目以降も同様にアイスバーを買う必要がない.
n >= s のとき
このとき, y < x となることから,
2箱目において,1箱目で買う必要があったタイミング全てで,繰り越し分 y を利用する事はできない.
しかし,x 回のうち,y 回分は利用できる.
よって,
x - y = n - s
回だけアイスバーを新たに買えば良い.
3箱目における2箱目からの繰り越し分は y のままであるから,3箱目以降も n - s 回アイスバーを新たに買うことになる.
ソースコード
テンプレ略
int n,k; string s; int solve() { int sum = 0; FOR(it, s) sum += *it - '0'; int x = 0, y = 0; REP(i,n) { if (i >= k) return x; if (y == 0) { x++; } else { y--; } y += s[i]-'0'; } k -= n; if (n < sum) return x; x += (k / n) * (n - sum); k %= n; REP(i,k) { if (y == 0) { x++; } else { y--; } y += s[i]-'0'; } return x; } int main() { while(cin >> n >> k) { cin >> s; cout << solve() << endl; } }