AOJ-ICPC 1159 - 備忘録

久しぶりにプロコンの問題を解きました。
リハビリとしてA問題を解いたけど思った以上に時間がかかってしまった…。

何人かで円になり、いくつかの小石が入ったボールを回していきます。ボールに石が入っていたら1つとって、入っていなかったら自分の持っている石を全部ボールに入れて次の人に渡します。これを繰り返すと、最終的には絶対に誰か一人がすべての小石を持つことになるので、その人が誰か求めましょう、という問題。
絶対一人にきまる、っていうのは面白いですね。

回答がこちら。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
int main()
{
    int n, p;
    while(1){
        cin >> n >> p;
        if(n == 0 && p == 0) break;
        int candidate[50] = {0};
        int start = 0;
        int bowlin = p;
        while(1){
            for(int i = 0; i < n; i++){
                candidate[i] += bowlin / n;
                if(i < bowlin % n) candidate[(start + i) % n]++;
            }
            int end = (start + bowlin % n) % n;
            while(candidate[end] == 0) end = (end + 1) % n;
            bowlin = candidate[end];
            candidate[end] = 0;
            start = (end + 1) % n;
            if(candidate[start] == p - 1){
                cout << start << endl;
                break;
            }
        }
    }
   return 0;
}

bowlinが現在ボールに入っている小石の数、candidate[i]がi番目の候補が現在もっている小石の数、startは小石を取り始める(startの一個前の人がすべての小石をボールに入れた)人の番号を表します。
まず候補者全員にbowlinをnで割った商だけ小石を渡します。その後startから数えて(bowlinをnでわったあまり)番目の人にもう一個石を渡します。これでボールの中の小石の数が0になった時の状況を再現できます。
endは自分の番が来た時にボールに入っている小石の数が0個だった人の番号を表します。bowlinにend番目の人がもっている小石の数を代入し、end番目の人がもっている小石の数を0にします。このとき、end番目の人がもともと小石を持っていなかった場合は小石をもっている人が見つかるまでendに1を加えていきます。
この後startをendの次の人になるように変更。start番目の人がp-1個の石をもっていれば、start番目の人はすべての石を持つことになるのでこれが答えになります。

startやbowlinを書き換えるところを忘れていたり、ところどころ「% n」が抜けていたりと細かなミスが多かったのでもうちょっとリハビリが必要そうです。