ホームに戻る
 TopCoder の傾向と対策2(C++編:応用)

0、はじめに

div2 の mid もしくは div1 の easy を解く為のアイデア集です。
簡単な例を細かく解説してしてあるつもりです。

後半の動的計画法はどちらかというと
div2 の hard もしくは div1 の mid で良くでる気がしますが、
div2 の mid もしくは div1 の easy でもたまにでるので書いておきます。

また、div2 の mid もしくは div1 の easy ではグラフはあまりでません。
よって、ここにはグラフのことは書いてありません。

1、圧縮探索

まず条件を確認し単純な探索でループが回るかを確認する。
ループが回るのであれば単純な探索でループを書いて問題無い。
もし、ループが回らなければ何らかの工夫が必要になる。
まずはループ回数を圧縮するために次のような問題を考える。

1 <= A,B <= N (1 <= N <= 40000) の整数 A,B がある。
A*B が 7 の倍数である A,B の組み合わせは何通りか?

これを次のように書くと失敗する。

int count = 0;

for(int A = 1; A <= N; A++){
  for(int B = 1; B <= N; B++){
    if((A*B) % 7 == 0){
      count++;
    }
  }
}

これは N が 40000 であった場合に、
1600000000 回のループを回しているからで、
この回数のループは当然2秒間で終了しない。

次のようにすれば N が 40000 であった場合にも、
40000 回のループで回る。

int count = 0;

for(int A = 1; A <= N; A++){
  if(A % 7 == 0){
    count += N;
  }
  else{
    count += N / 7;
  }
}

これは、
A が 7 の倍数であれば B はすべての値であること。
A が 7 の倍数で無ければ B は N までの 7 の倍数の個数あること。
の2つの条件を利用している。

さらに言うなら次の式でも答えはでる。

int count = (N / 7) * N + (N / 7) * N - (N / 7) * (N / 7);

これは A が 7 の倍数である場合と B が 7 の倍数である場合を足して、
そこから A と B がともに 7 の倍数である場合を引いている。

このように A の場合全体と B の場合全体を足して、
A と B の重複する場合の部分を引くと重複しないすべての場合が求まる。
これは「包除原理」という原理を利用している。

この問題は結局ループ無しでも解ける問題であったが、
回らないループを圧縮して回す問題は比較的多く出ている気がする。
圧縮する場合はどのように圧縮するかが問題になる。

2、2分探索

2分探索は値の範囲が例えば 0 から 1000000000 でも高速に探索する。
ただし、探索する値がある1点で分かれている必要がある。

例えば n < 2000 のとき 0 を返し、 n >= 2000 で 1 を返すとき。
これは 1999 と 2000 で結果が分かれているので探索可能である。
このとき 1 を返す最小値の 2000 を求めることが可能である。

解の可能性が 0 から 1000000000 の間にあるとき、

最小値を求める2分探索

int check(int n){
  // 123456789 を解とする場合
  if(n >= 123456789){
    return 1;
  }
  return 0;
}

int low = 0;
int high = 1000000000;

while(low < high){
  int mid = (high + low) >> 1;

  if(check(mid) == 1){
    high = mid;
  }
  else{
    low = mid + 1;
  }
}

答えは low に入っている。

最大値を求める2分探索

int check(int n){
  // 123456789 を解とする場合
  if(n <= 123456789){
    return 1;
  }
  return 0;
}

int low = 0;
int high = 1000000000;

while(low < high){
  int mid = (high + low + 1) >> 1;

  if(check(mid) == 1){
    low = mid;
  }
  else{
    high = mid - 1;
  }
}

答えは low に入っている。

3、2のn乗探索

N の要素がそれぞれ「ある」、「なし」の2通りをとるとき。
全探索すると 2 の N 乗探索することになる。

単純に考えるとまず N の要素数の配列を考える。
各要素に 0 と 1 を入れて「ある」、「なし」を管理する。
まず、最初にすべてに 0 を入れて試す。
最下位の要素に 1 をして試す。
現在の要素を 0 にし、1つ上の要素を 1 にして試す。
最下位の要素を 1 にして試す。
このように下から繰り上げて探索する。
これを要素がすべて 1 になるまで試す。

しかし、この更新の方法は非常に面倒である。
ここでビットを使うと探索が驚くほど簡単になる。

すなわち、要素が5つであった場合、
2進数で 00000 から 11111 までの探索を行えばいい。
これを for ループで書くと次のようになる。

for(int i = 0; i < (1 << 5); i++){

}

こうすると i の値は、

00000
00001
00010
00011
00100
00101

と増えていき、

11111

になったときループが終わる。

要素の「ある」、「なし」を調べるには、
次のようにする。
下位から j 番目のビットが 1 であるかを調べる。

for(int i = 0; i < (1 << 5); i++){
  for(int j = 0; j < 5; j++){
    // j 番目の要素が 1 であれば
    if(((i >> j) & 1) == 1){

    }
  }
}

このようにすれば実装が簡単で速度も速い。
ビットを使うので理論的には int なら最大32要素が可能である。
ただし、最上位ビットが符号に使われることや、
(1 << 31) という表現が適切か?という問題がある。

無理に32要素を使おうとすると以下のようになる。

for(unsigned int i = 0U;; i++){
  for(int j = 0; j < 32; j++){
    // j 番目の要素が 1 であれば
    if(((i >> j) & 1) == 1){
      
    }
  }
  if(i == (unsigned int)((1LL << 32) - 1)){
    break;
  }
}

ただ、2の32乗は全探索するとタイムオーバーする。
よって、TopCoder で32要素使う可能性はほとんど無い。

4、3のn乗探索

3のn乗探索も2のn乗探索と同じようにすれば良い。
ただし、この場合はビットは使えないので乗数と余りで実装する。

int a = 3;
int n = 4;

for(int i = 0; i < (int)pow((double)a, n); i++){
  for(int j = 0; j < n; j++){
    // j 番目の要素が 0 であれば
    if(i / (int)pow((double)a, j) % a == 0){

    }
    // j 番目の要素が 1 であれば
    else if(i / (int)pow((double)a, j) % a == 1){

    }
    // j 番目の要素が 2 であれば
    else{

    }
  }
}

このときオーバーフローしない n の最大値は19である。
要素数の最大値は次の数式の結果を超えない数値になる

log(a)2147483647  ()内は底

底の変換を使えば底の指定できない電卓でも計算できる。

log(b)c = log(a)c / log(a)b

5、順列

順列とは例えば要素数が5のとき、

01234
01243
01324
01342
01423
(以降、続く)

と増えていく方法のことである。

C++ では next_permutation を使うと簡単である。

vector<int> v;

for(int i = 0; i < 5; i++){
  v.pb(i);
}

do{
  // v には順列が入っている
}while(next_permutation(v.begin(), v.end()));

このとき next_permutation は、

「現在ある配列の要素を順列の順で次の要素に変える」

という意味あいであることを忘れてはならない。

vector の要素が最初から昇順でなければ全探索できない。
よって、vector の要素が昇順でなければ sort が必要。

また、必ずしも全探索で使う必要は無い。
例えば、次のような問題があったとする。

順列で 12345 を1番目としたとき100番目の要素は?
という問題がある場合には next_permutation を
99回呼び出せば100番目の要素がわかる。

6、順列の応用

n個の中からk個を選ぶ総探索は順列で書ける。
5個の中から2つ選ぶ場合を総当りする。
このとき配列の最初の要素を 00011 とする。
このとき next_permutation で更新すると次のようになる。

00011
00101
00110
01001
01010
(以降、続く)

これで5つの要素のうち2つを選ぶ場合の総当りができる。
この場合の探索回数は 5C2 である。

コードを書くと次のようになる。

#include <algorithm>

vector<int> v;

for(int i = 0; i < 5; i++){
  v.push_back(i < (5 - 2) ? 0 : 1);
}

do{
  // v には順列が入っている
}while(next_permutation(v.begin(), v.end()));

また、5個の中から1つと2つ選ぶ場合を総当りなら、
00122 として順列を回せばよい。

7、再帰関数

再帰関数とは関数の中から自分自身を呼び出す関数である。
再帰関数は可変回数の分岐や更新ループを短く書けるので便利。
もし正確に書ければかなり強力な手法になる。
TopCoder での使用頻度はかなり多いと言って良い。
スタックオーバーフローには気をつける。
簡単な例を書いてみた。

 問題

1回に1歩か2歩進める。
ちょうど10歩進むやり方は何通りか?

これを再帰で書いてみる。

int f(int n){
  if(n >= 10){
    if(n == 10){
      return 1;
    }
    return 0;
  }

  int ans = 0;

  ans += f(n + 1);
  ans += f(n + 2);

  return ans;
}

これを f(0) で呼び出せば回数が返る。

8、メモ化再帰

次のような関数 f がある。

f(0) = 1, f(1) = 1, f(x) = f(x-1) + f(x-2) のとき、

この関数 f を再帰で書いてみる。

int f(int x){
  if(x == 0 || x == 1){
    return 1;
  }

  return f(x - 1) + f(x - 2);
}

例えばこれを次のように呼ぶと時間に無駄がある。

int main(){
  int ans = 0;

  for(int i = 0; i < 100; i++){
    ans += f(i);
  }

  return 0;
}

これは f(98) を呼ぶときも、f(99) を呼ぶときも、
両方とも f(97)、f(96)、f(95)・・・と遡る。
この無駄をはぶくために再帰を次のように書く。

int flag[100]; // 最初はすべて 0 を入れておく
int memo[100];

int f(int x){
  if(x == 0 || x == 1){
    return 1;
  }

  // 数値があればそれを返す
  if(flag[x] == 1){
    return memo[x];
  }

  // メモに書き込む
  flag[x] = 1;
  memo[x] = f(x - 1) + f(x - 2);

  return memo[x];
}

このように書くと 2 から 99 までの結果は
memo[100] に記録されているのでそのまま答えを返せる。
配列 memo[100] は答えを記録しておくメモとして使う。
flag[100] はメモに書き込まれているかどうかを調べるのに使う。
この方法はメモ化再帰と呼ばれる。

9、終わりのない探索の終わらせかた

探索に終わりが無いと思える探索がある。
終わらせ方の発想はメモ化と同じ。
例えばこんな例題をやります。

問題

A と B からなる文字列があります。
A は B に反転し、B は A に反転させることができる。
この問題では3つの連続した文字列を選び反転させます。
例えば ABBA の場合 BAAA や AAAB にすることができます。
もう1回反転させることで BBBB や AAAA を作れます。
操作を何回か行うとき全て A にできる最小回数を答えよ。
ただし、答えが無い場合は -1 を答えとする。

文字列:ABAAABBBABABA

解き方、
最初の配列を記録しておく。
set に insert するので良いと思う。
次にこの場合に要素は13個あるので、
1回目に反転させるパターンは13−2で11通りある。
11通りの反転を行いこれも全て記録する。
次に、2回目に反転するやりかたを11通り行う。
すると以前に記録した配列に戻る場合がある。
戻ったかどうかは set の count で調べることができる。
以前に記録した配列に戻れば探索を終了する。
以前に記録した配列に無ければまた記録する。
これを繰り返す。
この方法を使えばいずれ探索はすべて終了する。

終了したときに全て A になる場合がいくつかあれば、
そのうちの回数の最小値が答えである。
答えが無ければ -1 を答えにすれば良い。

10、動的計画法

動的計画法は発想は再帰でメモ化を書くのと同じ。
ループと配列を使う点で異なる。
英語で Dynamic Programing なのでDPとも呼ばれる。

まずはこのような問題を考える

1から9までの数字を昇順に並べて数字を作る。
例えば、「1249」とか「35678」である。単に、「1」もOK。
ただし、「3256」や「113」は上昇していない箇所があるのでNG。
できる数字は何通りあるか?

数学的に考えれば 2^9 - 1 なので 511 通りであるが、
あえて再帰で書いてみる。

int f(int n){
  if(n == 9){
    return 1;
  }

  int count = 1;

  for(int i = n + 1; i <= 9; i++){
    count += f(i);
  }

  return count;
}

int main(){
  int count = 0;

  for(int i = 1; i <= 9; i++){
    count += f(i);
  }

  printf("%d", count);

  return 0;
}

この再帰だと関数 f は 511 回呼び出される。
これをメモ化再帰にしてみる。

int flag[10];
int memo[10];

int f(int n){
  if(flag[n] == 1){
    return memo[n];
  }

  if(n == 9){
    flag[9] = 1;
    memo[9] = 1;
    return 1;
  }

  int count = 1;

  for(int i = n + 1; i <= 9; i++){
    count += f(i);
  }

  flag[n] = 1;
  memo[n] = count;

  return count;
}

int main(){
  int count = 0;

  for(int i = 1; i <= 9; i++){
    count += f(i);
  }

  printf("%d", count);

  return 0;
}

こうすると関数 f は 9 回しか呼び出されない。
これを動的計画法で書いてみる。

int main(){
  int dp[10];

  memset(dp, 0, sizeof(dp));

  dp[9] = 1;

  for(int i = 8; i >= 1; i--){
    dp[i] = 1;
    for(int r = i + 1; r <= 9; r++){
      dp[i] += dp[r];
    }
  }

  int count = 0;

  for(int i = 1; i <= 9; i++){
    count += dp[i];
  }

  printf("%d", count);

  return 0;
}

再帰をそのまま置き換えてみた。

終了条件を初期条件、
現在の値を現在の dp 値、
関数 f をその他の dp 値

と、単純に置き換えることができる。
この場合 36 回のループが必要になる。
ただし、動的計画法が再帰のメモ化よりも劣っているわけでは無い。

int main(){
  int dp[10];

  memset(dp, 0, sizeof(dp));

  for(int i = 1; i <= 9; i++){
    dp[i] = 1;
    dp[i] += dp[i - 1] * 2;
  }

  printf("%d\n", dp[9]);

  return 0;
}

このようにすれば 9 回のループで終了する。

ちなみに、

dp[i] = 1; 

は、その数値のみを使う場合、

dp[i] += dp[i - 1] * 2;

は、今までの結果に現在の値を使う場合と使わない場合があるので、
今までの結果に2を掛け算している。

動的計画法の重要な点は次の2点。

初期値をどうするか?
何をメモするか?

再帰で書ける場合はまず再帰で書いてみるのも方法のひとつ。

11、動的計画法の練習

 問題

原点(0,0)から(15,15)へ移動する。
移動は x 方向もしくは y 方向に +1 ずつ進める。
この間に1ポイントもらえる地点がいくつかある。
(ただし(0,0)と(15,15)にポイントはない。)

例えば下の8地点があったとき最高何点得ることができるか?

(2,5),(4,13),(4,9),(7,15),(8,9),(10,13),(11,9),(13,9)

これを再帰で総当りを書いてみる。

int point_x[8] = {2, 4, 4, 7, 8, 10, 11, 13};
int point_y[8] = {5, 13, 9, 15, 9, 13, 9, 9};

int map[16][16];

int f(int x, int y, int score){
  if(x == 15 && y == 15){
    return score;
  }

  score += map[y][x];

  int mx = 0;

  if(x < 15){
    mx = max(mx, f(x + 1, y, score));
  }
  if(y < 15){
    mx = max(mx, f(x, y + 1, score));
  }

  return mx;
}

int main(){
  memset(map, 0, sizeof(map));

  for(int i = 0; i < 8; i++){
    map[point_y[i]][point_x[i]] = 1;
  }

  printf("%d", f(0,0,0));

  return 0;
}

場合の数を計算すると n = 30、r = 15 で nCr を計算するので、 
総当りをすると関数 f は 155117520 回呼び出される。

これを動的計画法で書いてみる。

int point_x[8] = {2, 4, 4, 7, 8, 10, 11, 13};
int point_y[8] = {5, 13, 9, 15, 9, 13, 9, 9};

int map[16][16];
int dp[16][16];

int main(){
  memset(map, 0, sizeof(map));
  memset(dp, 0, sizeof(dp));

  for(int i = 0; i < 8; i++){
    map[point_y[i]][point_x[i]] = 1;
  }

  for(int y = 0; y <= 15; y++){
    for(int x = 0; x <= 15; x++){
      if(y - 1 >= 0){
        dp[y][x] = max(dp[y][x], dp[y - 1][x] + map[y][x]);
      }
      if(x - 1 >= 0){
        dp[y][x] = max(dp[y][x], dp[y][x - 1] + map[y][x]);
      }
    }
  }

  printf("%d", dp[15][15]);

  return 0;
}

動的計画法であると 15^2 回すなわち 225 回で終了する。

これはある地点について、
まず y 座標方向に -1 の地点の値を調べ、
現在地点がポイントをもらえる地点であれば 1 を足す。
この値が現在地点に既にある値より大きければ更新する。

また x 座標方向に -1 の地点の値を調べ、
現在地点がポイントをもらえる地点であれば 1 を足す。
この値が現在地点に既にある値より大きければ更新する。

この作業をすべての地点で行えば最終的に、
(15,15)の地点に最大値が入っていることになる。

このときに更新していく順番は重要である。
特に既に確定した過去の値を更新してしまうと、
結果がおかしくなる原因になる。

別の問題をやってみる。

 問題
 
0〜3枚のカードが入る箱がN個(1 <= N <= 20)ある。
いまK枚(1 <= K <= 3*N)のカードを適当に箱に振り分ける。
最後に箱に入れなかったカードが余ってはならない。
箱のカードの枚数によって得点が決まっている。
得点表は score[4] で定義されている。
得点の取り得る値は 0 以上 100 以下であるとき、
獲得できる最高得点を求めよ。

#define N 20
#define K 30

int score[4] = {15, 10, 30, 20};

int dp[N][K + 1];

memset(dp, -1, sizeof(dp));

for(int i = 0; i < 4 && i <= K; i++){
  dp[0][i] = score[i];
}

for(int i = 1; i < N; i++){
  for(int r = 0; r <= K; r++){
    for(int t = 0; t < 4; t++){
      if(r - t >= 0){
        if(dp[i - 1][r - t] != -1){
          dp[i][r] = max(dp[i][r], dp[i - 1][r - t] + score[t]);
        }
      }
    }
  }
}

答えは dp[N -1][K] に入っている。

動的計画法はメモリをたくさん使う。
ただ div2 の mid もしくは div1 の easy の問題では、
メモリが足らなくて困るということはあまり無い。

12、ゲーム問題

ゲーム問題は複数のプレーヤーがゲームをし、
勝者は誰かを判定する問題のこと。

ゲームで確率や場合の数を求める問題もあるが、
確率や場合の数の問題であってここでは書かない。

まず、初期配置で勝敗が決まる問題がある。

 問題

N個の石(1 <= N <= 1000)がある。
AとBの2人が1〜3個の石を交互に取っていく。
パス(石を0個取る)は禁止されている。
最後に石を取れなくなったほうが負けである。
AとBは勝つために最善をつくすものとする。
Aが先手のときどちらが勝つか判定せよ。

こういう問題は石が少ないほうから考える。
Nが1〜3であればAが0になるまで取れば勝つ。
Nが4であればAが何個とっても1〜3個残ってしまう。
よって、Bは1〜3個とって0にできるのでBの勝ち。
石が4個のときに自分の順番であれば負ける。
Nが5〜7であれば残り4個になるまで石を取れる。
残り4個であれば負けるのでBを負かすことができる。
よって、この場合はAが勝てる。
Nが8のときはAが何個とっても5〜7個残る。
よって、Bに残り4個にされてしまうのでBが勝つ。

すなわちNが4の倍数であればBが勝ち。
それ以外であればAが勝つという判定で良い。

よって、

if(N % 4 == 0){
  return "B";
}
return "A";

と書けば良い。

よって、勝ち負けの法則さえわかれば、
初期状態を判定して答えを返すのみの問題もある。

もっと複雑な場合に対応するためにDPで書いてみる。

Aが勝てれば 0 Bが勝てれば 1 とする。

int dp[1001];

memset(dp, -1, sizeof(dp));

dp[0] = 1;

for(int i = 1; i <= 1000; i++){
  int flag = 1;

  for(int r = 1; r <= 3; r++){
    if(i - r >= 0){
      if(dp[i - r] == 1){
        flag = 0;
      }
    }
  }

  dp[i] = flag;
}

初期値は N=0 のときBが勝つので、

dp[0] = 1;

としておく。

更新は自分の手から -1、-2、-3 したときに、
いずれかの手がひとつでも自分が勝てる手に行き着けばよい。
よって、フラグをたててフラグをチェックする方法が良い。

答えは dp[N] に入っている。

DPを使えば取れる石の数が、
1個、5個、10個であっても解くことができる。

また、特殊なゲーム問題に Nim 問題がある。

 Nim 問題

石の山が複数あり、AとB交互に好きなだけ石を取るゲーム。

例えば、

{3、10、5、7、2、8}

という6つの石の山があったとき。
A、Bがひとつの山を選び交互に1つ以上の好きな数だけ石をとる。
石を取れなくなったほうの負けである。
Aが先手とする。

この勝敗はすべての石の数のXORをとる。
結果が0であるか0でないかで勝敗を判断できる。

山が{1、1}であればBの勝ち。
山が{3、4}であればAの勝ち。
山が{3、5、6}であればBの勝ち。

Nim には最後の石を取ったほうが勝ちになる場合と、
最後の石を取ったほうが負けになる場合の2通りがある。
このとき勝ち負けの判定が逆になるので気をつける。

このように石をとる問題はすぐに Nim の問題とわかってしまう。
実際には一見 Nim では無いような問題として出題される。

 grundy 数

grundy数とは対決問題で役に立つ概念。
「grundy数は移動できる0以上のgrundy数の中で最小のもの」です。

例えばN個の石から交互に1個もしくは2個取り自分が取れなければ負けとする。

grundy[0] = 0; // 石が0個のとき負け0とする。

石が1個のときgrundy数が0の状態に移動できる。
grundy数は移動できる0以上のgrundy数の中で最小のもの、なので。

grundy[1] = 1; // 石が1個のときgrundy数は1。

石が2個のときは0,1に辿りつけるので、

grundy[2] = 2; // 石が2個のときgrundy数は2。

となります。

石が3個のときは1,2に辿りつけるので、

grundy[3] = 0; // 石が3個のときgrundy数は0。

となります。

すなわち最初の石が0とか3個なら先手が負けると言えます。

石の山が複数あるときはgrundy数のXORとれば良い。

3個、2個、5個の石があってどれか1つの山から1個もしくは2個の石をとるとき、

grundy[3]^grundy[2]^grundy[5]

としてやれば良い。

Nim も結局はgrundy数の一部といえる。

例えば、

{3、10、5、7、2、8}

という6つの石の山があったとき。
A、Bの2人がひとつの山を選び交互に1つ以上の指定された数だけ石をとる。
例えば、1個もしくは4個取れるとする。
石を取れなくなったほうの負けである。
先手がAのとき、Aの勝ち負けを判定せよ。

まず、grundy数を求める。

int grundy[11];

grundy[0] = 0; // 石が 0 のとき自分の番であれば負け。

for(int i = 1; i < 11; i++){
  set<int> se;

  if(i-1>=0)se.insert(grundy[i-1]);
  if(i-4>=0)se.insert(grundy[i-4]);

  int g = 0;
  while(se.count(g)!=0)g++;
  grundy[i]=g;
}

grundy[3]^grundy[10]^grundy[5]^grundy[7]^grundy[2]^grundy[8]

非0であれば先手の勝ち、0であれば先手の負けとなる。

 別の問題

N個の石からなる1つの山がある。
AとBの2人が交互に1つの山を2つもしくは3つに分ける。
割り切れない場合もできるだけ均等に分ける。
例えば、5個を2つに分けると2と3、3つに分けると1と2と2である。
石が1個の山は分けることができない。
自分の順番で分けることができなくなったら負けである。
Aが先手で分けていくとき、Aの勝ち負けを判定せよ。

このように分けていく問題でも以下のように grundy 数が使える。

int f(int n){
  if(n == 1)return 0; // 石が 1 のとき自分の番であれば負け。
  set<int> se;
  if(n >= 2)se.insert(f(n/2)^f(n/2+(n%2==1 ? 1:0)));
  if(n >= 3)se.insert(f(n/3)^f(n/3+(n%3==2 ? 1:0))^f(n/3+(n%3!=0 ? 1:0)));
  int g = 0;
  while(se.count(g)!=0)g++;
  return g;
}

cout << f(25) << endl;

最初の山の石が25個のときAが勝つ。

13、Union−Find木

Union-Find木を使ってグループ管理ができる。

例えば、0 〜 10 の数字があったとき、
Union-Find木で 1, 3, 7 を結合しておくと、
1 と 3 が結合していることを調べることができ、
2 と 7 が結合していないことを調べることができる。

結合はできるが分離はできないので気をつける。

//int nc;                   // 現在の総グループ数
void init_uf(int n);        // n要素(0 〜 n-1)の木を作る
int find_uf(int a);        // 要素aの親を探す
void union_uf(int a, int b); // 要素aと要素bを結合
int check_uf(int a, int b); // 要素aと要素bが結合されていれば 1 を返す
int get_size_uf(int a);     // 要素aの含まれるグループの要素数

vector<int> uf, sz;
int nc;

void init_uf(int n){
  vector<int> uf_(n);
  vector<int> sz_(n, 1);
  uf = uf_;
  sz = sz_;
  nc = n;

  for(int i = 0; i < uf.size(); i++){
    uf[i] = i;
  }
}

int find_uf(int a){
  return (uf[a] == a) ? a : uf[a] = find_uf(uf[a]);
}

void union_uf(int a, int b){
  a = find_uf(a);
  b = find_uf(b);

  if(a != b){
    if(sz[a] >= sz[b]){
      swap(a, b);
    }
    uf[a] = b;
    sz[b] += sz[a];
    nc--;
  }
}

int check_uf(int a, int b){
  return (find_uf(a) == find_uf(b)) ? 1 : 0;
}

int get_size_uf(int a){
  return sz[find_uf(a)];
}

 問題

白マスと黒マスでできた最大50×50のマスがあり。
白マスは道、黒マスは壁である迷路とみなす。
移動は上下左右に移動可能、斜めは移動できない。
スタートとゴールがあるが壁があり繋がっていない。
ここに最大10組のワープゾーンが与えられる。
ワープゾーンはあるマスからあるマスへワープできる。
スタートからゴールへ到着できるか判定せよ。

 この問題はUnion-Find木を使って次のように解ける。

1、各マスにUnion-Find木の番号を割り当てる。
2、上下左右に移動できれば木を結合する。
3、ワープゾーンの組どうしで木を結合する。
4、スタートとゴールでグループが同じか調べる。

int d[n];
d[find_uf(a)] = 1;
などとしてグループに値を割り振ったりもできる。

Union_Find は状態を管理するのにとても便利に使用できる。
Union_Find を使わないと解けないという問題は出ないが、
実装に便利でミスも減らせるのでぜひ使えるようになりたい。

14、RMQ

RMQ は Range Minimum Query の略です。

簡単にいうと、

「指定された範囲の中から最小値を高速に探す。」

方法のことです。

例えば、バラバラの数字が入った d[10000] の配列があり、
要素 1234 から 6789 までに入っている数字の最小値は?
という問題があるときなどに高速に検索ができます。

ただ、要素が 10000 あるのだから、
最小値をさがすのにすべての値を見ないというのはあり得ない。
どう考えても最低でも 10000 のループが必要のように思える。
その答えは正解で、最低でも 10000 のループが必要です。
では、なぜ高速に検索できるといえるのか?

この答えは 10000 のループで下準備しておくと、
次からは sqrt(10000) 程度のループで検索ができるようになる
ということです。

よって、10000 の領域で 50 個の範囲で最小値を調べるとき、
普通にやると最悪 10000 * 50 = 500000 回程度の探索が必要になる。
ここで高速化を行うと 10000 + 50 * 100 = 15000 回ですむ。

まずは、RMQをバケット法でやってみる。
バケット法は領域を 100 程度の単位で分割する方法。
0-99,100-199,200-299,・・・1900-1999 の範囲で分けて、
その区間で最小値をメモしておく。
例えば 98-1921 までの区間で最小値を求めるとき。
100 単位の区間ではメモを使いそれ以外は実際の値を使う。
この方法は1次元以外でも2次元、3次元でも適応できる。
ただ、発想は簡単であるが実装が難しい。

セグメント木でもRMQを実現できる。

セグメント木はRMQの実装を木構造を使って行う方法。
できることはバケット法と同じ。
ただし、速度は log n でありかなり高速になる。
また、下準備をした後も値の更新が可能である。

セグメント木の制限は n が 2 の累乗であること。
下準備に必要な領域が n * 2 - 1 必要であること。

原理は全体の最小値を記録する。
これを左右に分けて左と右の領域で最小値を記録する。
これを要素が1つになるまで繰り返し続ける。
例えば、大きさ8の領域で以下のようになる。

  111111111111111   親
     |       |
  2222222 1111111   ↑
   |   |   |   |
  333 222 111 444   ↓
  | | | | | | | |
  6 3 5 2 1 1 7 4   子

このとき子の値が 6 から 7 の領域を調べたいとき、
本来なら 6 と 3 と 5 と 2 と 1 と 1 を見る必要があるが、
木の構造を利用すれば 2222222 と 111 の2つを見れば良い。

要素数が 2 の累乗でなければならいないという制限は、
ありえないくらい大きな値を入れた要素を追加すればクリアできる。
もし要素が10個であれば大きな値を入れた6個の要素を追加する。

セグメント木は最小値だけでなく最大値にも使える。
また、1 の中の 0 をフラグとし、フラグの検出にも使える。

セグメント木は頻繁に範囲を変えて最小値を算出するとき、
たとえばDPで巨大な区間の最小値を使って値を更新する
といった問題を解く場合にも利用できる。
テンプレを使えばバケット法で解くよりはミスを減らせそう。

#define N 256     // 可能な最大の要素数 2 の累乗であること
#define INF 10000 // ありえないくらい大きな値

int n;            // 実際に利用する領域
int d[2 * N - 1]; // 使用するメモリ

void init(int n1){
  n = 1;
  
  while(n < n1)n *= 2;
  
  for(int i = 0; i < 2 * n - 1; i++){
    d[i] = INF;
  }
}

void update(int k, int a){
  k += n - 1;
  d[k] = a;
  while(k > 0){
    k = (k - 1) / 2;
    d[k] = min(d[k * 2 + 1], d[k * 2 + 2]);
  }
}

int query(int a, int b, int k, int l, int r){
  if(r <= a || b <= l)return INF;
  
  if(a <= l && r <= b){
    return d[k];
  }
  else{
    int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
}

init(10); // 要素で初期化 最大値は N まで可能

update(x, a); // x の位置に a を代入

query(4, 8, 0, 0, n); // 4 <= x < 8 の範囲で検索

BIT木は発想はセグメント木と似ているが用途が違う。
BIT木は指定された範囲の最小値では無く。
lon(n) の回数で指定された範囲の総和を求める。

BIT木はセグメント木と違い2の累乗で無くて良い。
使用する領域も N + 1 しか使わない。
求める領域の和は 1 <= x <= 8 であり、
左端は 1 <= で固定であり、
右端が < と <= で違うので注意する。
BIT木を使って 5 <= x <= 8 の領域の和を求めるなら、
1 <= x <= 8 の和から 1 <= x <= 4 の和を引けばよい。

BIT木は以下のようであり、
原理は左端の 1 から 2 までの和を
4444444 と 222 と 2 を足して求める。

  999999999999999   親
                |
  4444444       |   ↑
        |       |
  222   | 222   |   ↓
    |   |   |   |
  1 1 1 1 1 1 2 1   子

なお、領域は N + 1 個だけ用意するが、
使用するのは 1 から N までを使用する。
0 を使うと無限ループになる。

#define N 10

int n = N;
int bit[N + 1];

int sum(int i){
  int s = 0;
  while(i > 0){
    cout << i << endl;
    s += bit[i];
    i -= i & -i;
  }
  return s;
}

void add(int i, int x){
  while(i <= N){
    cout << i << endl;
    bit[i] += x;
    i += i & -i;
  }
}

memset(bit, 0, sizeof(bit));

add(1, 5); // インデックス 1 に 5 を追加
add(3, 6); // インデックス 3 に 6 を追加
//add(0, 7); // インデックス 0 は無い!

sum(7); // 1 <= x <= 7 の要素の和を計算

和のスタートが 1 しか選べないが、
3 から 6 であっても sum(6)-sum(2) とすれば範囲の和になる。
BIT は 0 の中にフラグを 1 で埋めることでフラグの計数にも使えたりする。

RQMを実現するアルゴリズムは最小値のみを求めるものでなく、
幅広い応用が可能なので仕組みを知っておくと良い。

15、小数点切捨て問題

 問題

n 人の生徒が100満点のテストを受けた。
テストは1問1点で全100問である。
平均点は小数点2位未満を切り捨てる。
60.64点が平均点であるとき、
最低何人がテストを受けたと判断できるか?

この手の問題はたまにでる。

まず n 人の得点の総和を K とおきます。
すると点数は、

6064 <= (k * 100) / n < 6065

となる。
すべてに n をかけて、

6064 * n <= k * 100 < 6065 * n

になります。

n = 1 のとき、

6064 <= k * 100 < 6065

となるような整数 k は存在しません。

n = 2 のとき、

12128 <= k * 100 < 12130

でも整数 k は存在しません。

n = 14 のとき、

84896 <= k * 100 < 84910

であり整数 k は 849 がはじめてありうる。

よって、n は 14 になる。

応用で四捨五入問題などもでる。

inserted by FC2 system