IOI 2009 Bulgaria過去問 Archery

解法

難しすぎる。説明するよりソース見た方が早いところもあるのでとりあえず基本的な方針だけ説明する。ソースにはコメントをしっかり書いておいたのでそれなりに読めるはず。

まず、順位が1の射手について考えると、何ラウンドか経った後に的1に来て、その後はそこにとどまり続ける。次に順位がN+1以下の射手について考えると、何ラウンドか経った後に毎回的を移動してぐるぐる回り続ける。最後に順位がN+2以上の射手について考えると、何ラウンドか経った後にある的の場所からずっと動かない。これらのことから2Nラウンド後には全ての射手が周期的な動きをすることがわかり、その周期はNである。つまり、Rラウンド全てを考える必要はなく、2N + R % N ラウンドだけ考えればよい。

次に、開始位置と終了位置の関係について考える。開始位置xについて、その終了位置をend(x)、的1から的Nへ移る回数をjump(x)と書こう。するとまずjump(x)は明らかにxについて広義単調減少(x < y ならば jump(x) >= jump(y))である。また少し考えればjump(1) - jump(2N)は高々1であることもわかる。

また、jump(x) = jump(y)かつx < yのとき、end(x) <= end(y)であることもわかる。これはつまり、二つの開始位置x, yについて、的1から的Nに移る回数が同じであれば小さい方の位置から開始した方が小さい位置で終わることができるということである。

jump(1) = jump(2N)、つまり的1から的Nへ移る回数が全ての開始位置について同じ場合はend(x)は完全に広義単調減少である。よってend(x)について二分探索をすることができて、end(x)が最小であり、かつxが最大であるようなxを求めることができる。逆にjump(1) ≠ jump(2N)のときは、jump(1) = jump(k)かつjump(k+1) = jump(2N)なるkを見つけてやる。このkを見つけるのにも二分探索を使うことができる(jump(x)が広義単調減少であることから)。そのkを見つけることができたら、1 <= x <= k なるxについてはend(x)が広義単調減少であり、k+1 <= x <= 2Nなるxについてもend(x)が広義単調減少であることから、1 <= x <= k なるxについてと k+1 <= x <= 2N なるxについて、2回の二分探索をしてやって、そのうち良い解を選択すればよい。

さて、後はjump(x)およびend(x)の求め方であるが、普通にシミュレーションをすれば O(NR)、周期を使ってRを減らしてやってもO(N^2) である。できればこれを O(N) でやりたい。そこで最初に述べた周期の内容が使える。順位が1の射手は的1にとどまり続けるのでjump, endともに一瞬でわかる。

順位がN+1以下の射手はぐるぐると回り続けるわけだが、これについては的1についてだけ注目しているとjump, endともに求めることができる。つまり的1にいる射手が分かれば、後は同じ列が回っているだけなのだから他の射手も特定することができる。

順位がN+2以上の射手についてはどこかで位置が固定されて動かなくなるので、この位置を求めてやれば良い。これについては勝利あるいは敗北によって左の的へと移る射手をまとめて処理することで全体でO(N)でjump, endを求めることができる。詳しいことはソースを見た方が分かりやすい。

以上のことを全てまとめると、jump(1) == jump(2N)の場合はkを求めるのにO(N lg N)と答を求めるのにO(N lg N)、jump(1) ≠ jump(2N) の場合は単に答を求めるのにO(N lg N)の時間がかかる。結局のところ O(N lg N) で完了するので N <= 200000 で間に合う。

ソース

/*
  TASK: Archery (IOI 2009 Bulgaria)
  LANG: C++
  NAME: JAPLJ

  Problem URL: http://www.ioi-jp.org/ioi/2009/problems/day1/Archery_jp.pdf
 */

#include<cstdio>
#include<utility>
#include<cstring>

using namespace std;

int N, R;
int S[400050];

// 自分より弱い射手、自分、自分より強い射手がいる場所をヒストグラム的に表す
int weak[600050], me[600050], strong[600050];

// 関数simulateをメモ化する
bool memoized[200000];
pair<int, int> memo[200000];

// 開始位置を受け取って(終了位置, 的1から的Nへ飛んだ回数)を返す
pair<int, int> simulate(int pos)
{
  int starget = pos / 2; // 開始する的
  if(memoized[starget]) return memo[starget];
  if(S[0] == 1) {
    // 順位が1位なので的1で固定
    return make_pair(1, 0);
  } else if(S[0] <= N+1) {
    // 順位が前半なのでぐるぐる回る

    // 的ごとに人数を数える
    memset(weak, 0, sizeof(weak));
    memset(me, 0, sizeof(me));
    memset(strong, 0, sizeof(strong));
    me[starget] = 1;
    for(int i=1; i<2*N; ++i) {
      int target = (i - 1 + (i > pos ? 1 : 0)) / 2;
      if(S[i] > S[0]) weak[target]++;
      else strong[target]++;
    }

    // 的1にいる射手を特定する
    int weak1 = 0, me1 = 0, strong1 = 0; // 的1にいる人数
    if(pos < 2) {
      me1++; 
    } else {
      if(S[2] > S[0]) weak1++;
      else strong1++;
    }
    if(S[1] > S[0]) weak1++;
    else strong1++;

    int me1_round = -1; // 周期の中で何ラウンド目に自分が的1に来るか
    int to_n = 0; // 的1から的Nに飛んだ回数
    int next_weak = 0, next_me = 0, next_strong = 0; // より右側の的からやってくる射手の数
    
    // 3Nラウンド回す(循環に入るまでの2Nラウンド + 一サイクル回すためのNラウンド)
    // 的が3N個あると考えて、対象の的をシフトしていく(敗者は現在の的+Nの的へ飛ばす)
    for(int i=0; i<3*N; ++i) {
      if(i >= 2*N && me1) {
        // 既に循環に入っていて、自分が的1にいる
        me1_round = i;
        break;
      }
      
      // 敗者を決定する
      int lose; // 敗者
      if(strong1) {
        if(strong1 == 2) lose = 0; // 自分より強い射手が負ける
        else if(me1 == 1) {
          // 自分が負ける
          lose = 1;
          to_n++;
        } else lose = 2; // 自分より弱い射手が負ける
      } else lose = 2;

      // 敗者をi+N番目の的に飛ばす
      if(i <= 2*N) {
        if(lose == 0) {
          strong[i+N]++;
          strong1--;
        } else if(lose == 1) {
          me[i+N]++;
          me1--;
        } else {
          weak[i+N]++;
          weak1--;
        }
      }

      // 右の的から射手を左に動かす
      next_weak += weak[i+1];
      next_me += me[i+1];
      next_strong += strong[i+1];

      // 次に的1に来る射手を特定する
      if(next_strong) { // 強い射手が優先
        strong1++;
        next_strong--;
      } else if(next_me) {
        me1++;
        next_me--;
      } else {
        weak1++;
        next_weak--;
      }
    }
    
    // 自分が的1に来て以降もラウンドが続くならもう1回だけ的1から的Nへ飛ぶ
    if(R > me1_round) to_n++;

    // シミュレーションおわり
    memoized[starget] = true;
    memo[starget] = make_pair(N - (R - me1_round - 1 + N) % N, to_n);
  } else {
    // 順位が後半なので位置が固定される

    // 的ごとに人数を数える
    memset(weak, 0, sizeof(weak));
    memset(me, 0, sizeof(me));
    me[starget] = 1;
    for(int i=1; i<2*N; ++i) {
      int target = (i - 1 + (i > pos ? 1 : 0)) / 2;
      if(S[i] > S[0]) weak[target]++;
    }

    // 3Nラウンド回す
    int next_weak = 0, next_me = 0; // 勝利あるいは敗北によって左の的へ行く射手の数
    int to_n = 0; // 的1から的Nへ飛んだ回数
    for(int i=0; i<3; ++i) {
      int j = 0; // いま注目している的
      do {
        // いま注目している的にいる人数を数える
        int weak_ct = weak[j] + next_weak;
        int me_ct = me[j] + next_me;

        if(weak_ct + me_ct >= 2) {
          // 自分とそれより弱い射手の数が2以上のとき
          // j > 0 なら自分より弱い射手1人を残して、あとの射手は左の的へ移る
          // j == 0 で自分が居るなら自分より弱い射手が全員的Nへ移る
          // j == 0 で自分が居ないなら自分より弱い射手1人を残して、あとの射手は全員的Nへ移る
          if(j > 0) {
            // そのまま左へ
            weak[j] = 1;
            next_weak = weak_ct - 1; // 1人以外は左へ
            me[j] = 0;
            if(me_ct) next_me = me_ct; // 自分がいれば左へ
            else next_me = 0;
          } else {
            if(me_ct) {
              // 自分はそのまま的1に残り、後は的Nへ
              me[j] = 1;
              weak[j] = 0;
              next_me = me_ct - 1;
              next_weak = weak_ct;
            } else {
              // 弱い射手1人を残して、後は的Nへ
              me[j] = 0;
              weak[j] = 1;
              next_me = 0;
              next_weak = weak_ct - 1;
            }
          }
        } else {
          // 自分とそれより弱い射手の数が2に満たないとき
          // j > 0 ならその場にとどまる
          // j == 0 なら的Nへ移る
          if(j > 0) {
            me[j] = me_ct;
            weak[j] = weak_ct;
            next_me = next_weak = 0;
          } else {
            if(me_ct) to_n++;
            me[j] = 0;
            weak[j] = 0;
            next_me = me_ct;
            next_weak = weak_ct;
          }
        }
        // 次の的へ
        if(j == 0) j = N-1;
        else j--;
      } while(j); 
    }
    for(int i=0; i<N; ++i) {
      if(me[i]) { // この的に自分がいる
        memoized[starget] = true;
        memo[starget] = make_pair(i+1, to_n);
        break;
      }
    }
  }
  return memo[starget];
}

// lo..hiの中で最良の開始位置となる的と、その終了位置を求める
// lo..hi間について、的1から的Nへ飛ぶ回数を同じと仮定する
// 上の仮定により、終了位置は広義単調増加になるので二分探索が可能
pair<int, int> getbest(int lo, int hi)
{
  pair<int, int> lo_s, hi_s, mid_s;
  int mid;
  lo_s = simulate(lo * 2 - 1);
  hi_s = simulate(hi * 2 - 1);
  while(hi - lo > 1) {
    mid = hi + lo >> 1;
    mid_s = simulate(mid * 2 - 1);

    if(lo_s.first < mid_s.first) {
      hi = mid;
      hi_s = mid_s;
    } else {
      lo = mid;
      lo_s = mid_s;
    }
  }
  if(lo_s.first < hi_s.first)
    return make_pair(lo, lo_s.first);
  else
    return make_pair(hi, hi_s.first);
}

int main()
{
  scanf("%d%d", &N, &R);
  R = R % N + 2 * N; // 2Nラウンド後に周期Nの循環に入る
  for(int i=0; i<2*N; ++i)
    scanf("%d", &S[i]);

  int sol;
  pair<int, int> lo_s, hi_s;
  int lo = 1, hi = N;
  lo_s = simulate(lo * 2 - 1);
  hi_s = simulate(hi * 2 - 1);
  if(lo_s.second > hi_s.second) {
    // 的1から的Nへ飛ぶ回数に差があるので、差のない2つの部分に分ける
    // 的1から的Nへ飛ぶ回数は広義単調減少なので二分探索で求まる
    int mid;
    pair<int, int> mid_s;
    while(hi - lo > 1) {
      mid = hi + lo >> 1;
      mid_s = simulate(mid * 2 - 1);

      if(mid_s.second > hi_s.second) {
        lo = mid;
        lo_s = mid_s;
      } else {
        hi = mid;
        hi_s = mid_s;
      }
    }
    if(lo_s.second > hi_s.second) mid = hi;
    else mid = lo;

    // 1..mid-1とmid..Nに分かれたので、別々に解を求める
    pair<int, int> best1 = getbest(1, mid-1);
    pair<int, int> best2 = getbest(mid, N);
    if(best1.second < best2.second)
      sol = best1.first;
    else
      sol = best2.first;
  } else {
    // 的1から的Nへ飛ぶ回数が全部同じなので全体の解を求めればおわり
    sol = getbest(1, N).first;
  }
  printf("%d\n", sol);
  return 0;
}