TCO13 Round 1C

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15585

250に16分。500に46分。チャレンジに1回失敗。511位でTCO13 Round1を通過。Room 34。レートは1323から1347に上がった。

	Problem	Status	Points
250	TheArray	System Test Passed	170.76
500	TheOlympiadInInformatics	System Test Passed	382.96
1000	TheKnights	Unopened

250に16分
500に46分
- 二分探索の理解が足らず、迷走した
チャレンジに失敗した
250に時間をかけ過ぎた
500でまたしても怪しい実装をしてしまった
TCO Round1こそ通過したが反省すべき点が多い
正確な理解を元にした二分探索を実装し提出することを目標とする

TheArray

http://community.topcoder.com/stat?c=problem_statement&pm=12455&rd=15585

16分。170.76点。

問題を読み終わってすぐに全探索の問題であると考えた

与えられた情報から取りうる最大の要素の値を答える問題。与えられる情報は要素の数、要素間が取りうる最大の差、初めと最後の要素の値

ここから頭の中に何となく浮かんでいたのは以下のような図であった(不思議なことにしっかり作図すると印象が違う)

左右から要素間が取りうる最大の差を用いて要素を置いて行く。左右からの要素が中央で出会ったときの差が高々dであれば高いほうの要素は解の候補となる

左右からの要素が中央で出会ったときの差がdより大きい場合は条件に合わない。解の候補にもならない

これを素直に実装した
- 反復の回数と右からの距離の算出方法に手間取り、16分もかかってしまった

class TheArray {
public:
  int find(int n, int d, int first, int last) {
    int ip = std::max(first, last);

    for (int i = 0; i < n - 1; i ++) {
      int f = first +          i  * d;
      int l = last  + (n - 2 - i) * d;

      if (std::abs(f - l) <= d)
        ip = std::max(std::max(f, l), ip);
    }
    return ip;
  };
};

制約違反しているテストケースでチャレンジを行おうとしたが、キャンセルされた
最後の制約を見逃していたのが原因であった

|first - last| will be at most (n-1)*d.

そもそもこの制約がなければ自分の解法は成立しないか...?

自分の実装で試していないテストケースを使ってチャレンジし、失敗した
- 自分の実装でも同じ答えを返した
- 写経しているのにもったいない...

今回のチャレンジの教訓
- 焦ってチャレンジしてもいいことはない
- チャレンジするテストケースは自分の実装で試したものを用いる

TheOlympiadInInformatics

http://community.topcoder.com/stat?c=problem_statement&pm=12456&rd=15585

46分。382.96点。

読み終わってすぐ、二分探索の問題であることに気付く

しかも整数の二分探索だ。過去にばっちり考察したぞ...(Suminator - agwの日記 - TopCoder部)

区間を[l, u]とし、m(= (l + u) / 2)の要素と判定を行う。値が見つからない場合は[l, m-1]もしくは[m+1, u]を新しい区間とし、探索を継続する

アルゴリズムCでの実装例は以下であった

int binarysearch(int v)
  {
    int l = 1; int r = N; int x;
    while (r >= l)
      {
        x = (l+r)/2;
        if (v < a[x].key) r = x-1; else l = x+1;
        if (v == a[x].key) return a[x].info;
      }
    return -1;
  }

当時以下のような作図もしたし、間違いようがない...(図は再掲)

意気揚々と実装を開始

...いつ反復を終了すればよいんだろう?

後で気付いたがアルゴリズムCの例は「単調非減少な数列a₁, ..., a_Nからa_i = kとなるようなiを求める探索」であるのに対し、今回の問題は「単調減少な数列a₁, ..., a_Nからa_i ≦ kとなるような最小のiを求める探索」を実装する問題であった

TCO中はそんなことに気付かず、悩みに悩んで実装した。サンプルのケースを通したところで投稿
- システムテストはパスしたが、何故動作しているかも説明できない実装となってしまった

さて問題を整理しよう。自分より点数の高い人が高々k人いる最小の点数を探したい
- 自分がm点取ったときにm + 1点以上の点数を取っている人が高々k人であればmは有効
- 有効な最小のmを探す

初めの例で考えてみる。4つの部屋それぞれの得点の合計が4点、7点、0点、5点
自分より点を取っている人の数が高々0人、つまりいなくなってしまう最小の得点を求めたい

自分が0点取るとする。1点以上取っている人は最大で16人。これは条件である0人を超えてしまっている

自分が1点取るとする。2点以上取っている人は最大で7人。これも条件である0人を超えてしまう

これを繰り返す。自分がi点取ったときにi + 1点以上取っている人の数をa_iとすると、a_iは以下のような数列となる

自分より点を取っている人の数がいないのは自分が7点以上取っている場合であり、最小の得点は7点だ

個人が取りうる点数の範囲は[0, 10⁹]である
- ここで記載した方法単純な反復だと計算量はO(MN)。収まりきらない
- しかし、単調減少な数列であるので二分探索を用いればO(MlogN)に抑えることが出来そうだ

少し考えるとこの問題で求められているのは有効な区間がどこから始まっているかであることが分かる

うーむ、二分探索をどのように実装してよいかさっぱり想像が付かない

蟻本の二部探索の章を見てみる

載ってた

蟻本では右閉半開区間を用いていた

また、反復を条件は以下だ

興味のある区間が[0, 10⁹]である場合、右閉半開区間の初期値は以下としければならないので注意が必要だ

うーん...
- 左閉半開区間はよく用いるが、右閉半開区間は慣れない...
- 区間の初期値が数列からはみ出ているのも何か不安だ
反復条件もよく分からない

図示してみよう

「単調非減少な数列a₀, ..., a_n-1からa_i ≧ 3となる最小のiを探す」問題を蟻本の手法で実装し、l、uと中央値mの動きを観察する
- mは(l + u) / 2として算出する

数列は「2、2、3、3、5」としてみよう
- nを数列の要素数とする。この場合nは5である
- また、数列はa₀, ..., a_n-1であることに注意しよう

をー、こうなるのか

数列の要素をずらして並べてみたくなる
- やってみた

一貫しているなぁ...

反復の条件も理解しやすいものであった
- 区間内の要素数が1より多ければ反復を繰り返す
- 言い換えると、区間内の要素数が一つである場合、残った要素が求める答えとなる

区間には必ず有効な要素が含まれていることにも注目したい

a_mが区間に含まれている場合(a_mが有効な場合)
- 次の区間、(l, m]には有効な要素が *必ず* 含まれている(少なくともa_m)
a_mが区間に含まれていない場合(a_mが無効な場合)
- 次の区間の(m, u]に有効な要素が含まれている(かもしれない)

少し微妙な言い回しにしたのは、数列が目的の要素を含まない場合を考慮したからだ

例えば「2、2、2、2、2」の数列ではa_i ≧ 3となる最小のiを求めることが出来ない。元々3以上の値が含まれていないからだ
- 同様に図示してみる。この図は初期値として与える区間を誤った失敗例であることに注意

数列に3が含まれていないのに関わらず、最後の要素(2)を示している
- これはよくない

どうすればよいか
- 区間の初期値を少し大きくしておけばよい
- 具体的には区間の初期値を(-1, n]とすればよい

探索が終了したときの区間が(n - 1, n]である、すなわちuがnであれば探索に失敗したことを表す
- これはすごい

先に「区間には必ず有効な要素が含まれている」と記載したが、これは以下のように考えるべきだ
- 「数列に有効な要素が含まれている場合、探索で訪れたそれぞれの区間に必ず有効な要素が含まれている」

さて、区間は最後にたった一つの要素を持つ
そして、区間には必ず有効な要素が含まれている
ここから、求める要素はuであることが分かる((u-1, u]に含まれているのはuだけだ!)

右閉半開区間を伴った二部探索にはさらに利点がある

数列の要素数がnであると考える
- 数列はa₀, ..., a_n-1でアクセスできるとする
- 数列に目的の要素が含まれている場合、設定すべき初期の区間は(-1, n-1]
- 数列に目的の要素が含まれていない場合であったとしても、設定すべき初期の区間は(-1, n]

[0, n-1]以外の添字でアクセスするとセグメント違反するものとしよう
- つまりmが-1やnであるとき、a_mへのアクセスはプログラムを停止させてしまう

だが、右閉半開区間を伴った二部探索ではmが必ず[0, n-1]に収まるため気にしなくてよい
- これは本当にすごいことだと思う

ここまでの考察を元に、再度実装してみた

以下はシステムテストを通る実装。

class TheOlympiadInInformatics {
public:
  int find(std::vector<int> sums, int k) {
    int l = -1, u = 1000 * 1000 * 1000;

    while (u - l > 1) {
      int m = (l + u) / 2;

      long long s = 0;
      
      EACH (it, sums)
        s += *it / (m + 1);

      if (s > k) {
        l = m;
      }
      else {
        u = m;
      }
    }
    return u;
  };
};

すっきりした

まとめ

整数の二分探索では右閉半開区間を用いるとよい。その利点は、
- 数列に求める答えがある場合、区間は必ず有効な要素を含んでいる
- 一貫している。答えも区間で示される
- 反復条件が簡単。区間に要素が一つ以上ある場合は反復を続ける
- 数列に求める答えがない場合でも有効である
- a_mがアクセス違反することがない
区間ではなく要素を求める場合は以前考察した手法~~も変わらず有用である~~のほうが有用である(次節を参照のこと)

@kinabaさんの記事を改めて読み直した
- 簡潔で分かりやすい
- ツィートのまとめも大変参考になる

おまけ

閉空間と左閉半開区間の挙動を図示する

閉区間の例(1)
- 次の区間にmが含まれないようにする
- mが有効な要素である場合は次の区間を[l, m-1]とする(mより左側に有効な要素があるか探索する感覚?)
- mが有効な要素ではない場合は次の区間を[m+1, u]とする
- 答えはlとなるようだが、反復が終わったときの[l, u]は区間として無効である。そのため何故lが答えであるか説明するのが難しい
今回のTCOでの実装はこれであった
- 意外と悪くはない。が、自明ではない

閉区間の例(2)
- 区間に必ず有効な値を含ませるようにする
- mが有効な要素である場合は次の区間を[l, m]とする
- mが有効な要素ではない場合は次の区間を[m+1, u]とする
成立しているように思える。要素が存在していないことを想定して区間を[-1, n]から始めたとしてもmは[0, n-1]に収まる

左閉半開区間
- 区間に必ず有効な値を含ませるようにする
- mが有効な要素である場合は次の区間を[l, m+1)とする
- mが有効な要素ではない場合は次の区間を[m+1, u]とする
m = u - 1のとき、m + 1 = uとなり無限ループを引き起こす
図から見てもかなり不自然だ...

追記(2014/1/14)

右閉半開区間をうまく活用したこの手法では区間の探索を行うのに有用だ
- lower_boundが良例だ
- lower_boundは「ある値以上の要素が出現する初めての位置」を返す

int lower_bound(const std::vector<int>& a, int x)
{
  int l = -1, u = a.size();

  while (u - l > 1) {
    int m = (l + u) / 2;

    (a[m] >= x ? u : l) = m;
  }
  
  return u;
}

しかし、binary_searchのように「値があるかどうかを探索する」ために右閉半開区間を用いると冗長な実装となってしまう

bool binary_search(const std::vector<int>& a, int x)
{
  int l = -1, u = a.size();

  while (u - l > 1) {
    int m = (l + u) / 2;

    if (a[m] == x)
      return true;		// 発見!

    (a[m] > x ? u : l) = m;
  }
  
  return a[u] == x;	// この部分が冗長(未検査の値が一つ残っている)
}

この場合は閉区間を用いた探索を行ったほうが実装がすっきりする

bool binary_search(const std::vector<int>& a, int x)
{
  int l = 0, u = a.size() - 1;

  while (u - l >= 0) {
    int m = (l + u) / 2;

    if (a[m] == x)
      return true;

    if (a[m] > x) {
      u = m - 1;
    }
    else {
      l = m + 1;
    }
  }
  return false;
}