読者です 読者をやめる 読者になる 読者になる

SRM 619 Div2 Medium ChooseTheBestOne

問題

SRM 619 - TopCoder Wiki

N人を円上の椅子に座らせる.ステップii3番目の人を円から外す. 次のステップは外された人の次の人から始める. 最後に残った人を答える問題.

解答

本当に愚直にシミュレーションすると,N=5000の時,最後には49993の移動をシミュレーションするハメになるためよろしくない.

円上なので今いる人数のmodを取れば,各ステップの移動のシミュレーションはO(1)で完了する.

Nステップで同様に行うことで最後の人を求めることが出来る.

class ChooseTheBestOne
{
public:
  int countNumber(int N)
    {
      vector<int> people(N, 0);
      for (int i = 0; i < N; i++) people[i] = i + 1;
      long long cur = 0;
      for (long long i = 1; i < N; i++){
        long long idx = (cur + (i * i * i - 1)) % people.size();
        // int idx = ((((i % people.size()) * i) % people.size()) * i) % people.size();
        // cout << "erase " << people[idx] << endl;
        people.erase(people.begin()+ idx);
        cur = idx;
      }
      return people[0];
    }
};