yukicoder No.78 クジ付きアイスバー

解法

1箱目と最後の箱はシミュレーションし,間の箱はまとめて処理する.
間の箱をまとめて処理するため,以下の事実を使う.
まず,

  • n = 1箱に入っているアイスバーの数
  • s = 1箱に入っている当たりの数の和(2本当たりなら2加算される)

とする.
このとき,

  • n < s なら,2箱目以降の箱でアイスバーを新しく買う必要はない.
  • n >= s なら,間の箱を1箱分買うために,n - s 個アイスバーを新しく買えば良い.
証明

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;
  }
}