No.3 ビットすごろく
yukicoder No.3 ビットすごろくの解説
この問題はある数字Nが与えられ。１〜Nの区間での最小の移動回数を求めます。
位置の数字を２進数で表し「１」のbit数だけ前、後に移動することができます。
まずqueueとしてQを宣言します。Qにはその位置から移動できる場所を入れていきます。前に移動した場合と後に移動した場合の２通りを入れていきます。
そして移動した回数を保存していく配列dを宣言します。
また移動したか、していないかを保存する配列を宣言します。
移動したことがあるばい、前回に保存されている方が移動回数は少ないため更新する必要性はありません。この操作を移動できなくなる。つまりキューが空になるまで続けることで答えを導き出すことができます。
数字の「１」のビット数を数得る場合は__builtin_popcount 関数を使えば求めることができます。
以上解説でした。
以下ソースコードになります。
#include <iostream> #include <queue> using namespace std; const int INF = 100000000; int main(void){ int n, i; int v[10005], d[10005]; //vは移動したかしていないかを判別する配列、dはiまでの最小移動回数を保存する配列 cin >> n; for(int i=1;i<=n;i++){ v[i] = 0; //全て移動していないことにする。 } for(int i=1;i<=n;i++){ d[i] = INF; //全て移動移動できないとしておく } queue<int> que; //queは移動できる場所を格納する que.push(1); v[1] = 1; d[1] = 1; while(!que.empty()){ int bit; i = que.front(); que.pop(); bit = __builtin_popcount(i); //この関数は「１」のbit数を返してくれる if(i+bit >= 1 && i+bit <= n && v[i+bit] == 0){ que.push(i+bit); v[i+bit] = 1; d[i+bit] = d[i] + 1; } if(i-bit >= 1 && i-bit <= n && v[i-bit] == 0){ que.push(i-bit); v[i-bit] = 1; d[i-bit] = d[i] + 1; } } cout << (d[n] != INF ? d[n] : -1) << endl; return 0; }
No.8 N言っちゃダメゲーム
No.8 N言っちゃダメゲーム 解説
この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。
自分は必ず先攻で、相手は後攻です。
１〜Kの値までで加算して宣言することができます。
解答
この問題は自分がN−１をいうことができれば勝てます。
相手にN−１−K≦X≦N−２を相手に言わせれば良い。
自分はNー１ーKー１「Nー１ー（K＋１）」を言えば勝てます。
相手にNー１ーKー１ーK≦X≦N−１ーKー１ー１を言わせれば良い
自分はNー１ーKー１ーKー１「Nー１ー２（K＋１）」を言えば勝てます。
このように続けていくと「Nー１ーM（K＋１）」（Mは定数）を言える時自分は勝つことがでいます。逆にこの値を相手に言わせてしまうと負けになります。自分は先攻で自分の初期状態は０であるためこの値が０と等しいと自分はこの値を宣言することができません。そのような場合相手は必勝法を使うため自分は勝てません。
つまり
Nー１ーM（K＋１）＝０
が成り立つ時
すなわち
N＝M（K＋１）＋１の時
負けます。
したがって
N mod (K+1) == 1の時負けとなります。
以上解説でした。
二分探索木：削除
【アルゴリズムとデータ構造】二分探索木：削除（解説）
９．４の解説をします。
ある節点Zを削除する時を考えます。
・Zが子を持たない場合
ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い
・Zが子を一つ持つ場合
Zは親と子供に挟まれているので、Zを削除するためには親の子供の設定をZの子
供に変え、（Zの子供）の親を（Zの親）に変えてあげればZを削除できます。
・Zが子を二つ持つ場合
Zの次節点とは単にZの上の接点のことを指している。Zが持っている２つの子をZの上の節点に移してあげれば良い。そこでZの次節点の値をZ地震にコピーし、Zの次節点を削除してあげればZを削除したことになる。
解説のプログラムの解説をします。
二分探索木Tと削除対象Zを受け取ります。
そこで削除対象は、Zが子を持つ場合ではZの次節点でした。そこで削除対象をYに移します。子を持たない、子を１つだけ持つ場合ではY＝Zであり、Zが子を持つ場合はZの次節点をYに代入します。
次に削除対象の子供を調べます。
左に子があれば左の子をxに代入します。
左に子供がない場合にはxに右の子の値を代入します。この場合実際に右に子供がいなくても構いません。あとで処理します。
そしてxがNILじゃないつまり削除対象の子供が存在する場合、削除対象の親を、削除対象の子供の親に設定します。
削除対象の親が存在しない時、その削除対象の子供を根とします。
削除対象がその親の左の子供の場合には、左の子供の位置に削除対象の子供を入れます。
削除対象がその親の右の子供の場合には、右の子供の位置に削除対象の子供を入れます。
最後の子供が二ついた場合において次節点が削除された場合
つまり削除対象がZと異なる場合
Zの値に、削除対象の値を代入します。
次節点を求めるアルゴリズムの解説
右の子供が存在する場合は値が一番小さい節点が次節点となるので、その節点を調べて返します。
右の子供が存在しない場合には、自身が左の子供になっているような節点の親が次節点となる。
次節点は以下のようにして探索します。まずYにXの親を代入します。
そのYが存在するつまり根ではないかつ、右の子供がXである限り以下の操作を繰り返します。
まずXとYを位置関係そのままで上に移していきます。
つまりYはXの親であるから、XにYを代入
YにYの親を代入
を繰り返すことで次節点を探索することができます。
次に二分探索木での最小値を求めるアルゴリズムの解説をします。
最小値となる候補はその値かその左の子供であるめ左の子供について一番深い場所にある節点を探索していきます。
Xの左の子が存在するまで繰り返します。
そうすることで二分探索木の最小値を求めることができます。
一般的に二分探索木では木の高さをできるだけ低く維持する必要性がある。
バランスのとれた木を平衡二分探索木という。
二分探索木：挿入
【アルゴリズムとデータ構造】二分探索木：挿入（解説）
９．２の二分探索木の解説をしていこうと思います。
２０９ページのプログラムの解説
まずルートから挿入する位置を探索するのでyにNIL(rootを表す)を代入します。
ルートであれば親は持っていないはずです。
そしてまずルートの値と比較するために比較対象にするxにルートを代入します。
以下ループで代入する位置の親となるyを探していきます。
まずどこまで探索できるかわからないためxの値を親としてまず保存しておきます。
そのあとxのkeyの値とzのkeyの値を比較し、それよりも小さいならば比較対象をxの左の値に移します。大きいならばxを右の値に移します。
そしてこの作業を続けていき比較対象を移していくと値が入っていない接点にたどり着きます。その時yにはその値が入っていない親が入っています。
それをzの親として代入します。
最後にy == NIL、親がいない、つまり xの挿入位置がルートならばTのルートにzを挿入します。そしてzの値が親の値y.keyより小さいならば親の左の子にzを挿入します。
大きいならば親の右のことしてzを代入します。
以上擬似コードの解説でした。
