競プロ記録

問題を解いた際に自分の復習用として使ってます

No.8 N言っちゃダメゲーム

No.8 N言っちゃダメゲーム 解説

 

この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。

自分は必ず先攻で、相手は後攻です。

1〜Kの値までで加算して宣言することができます。

 

解答

この問題は自分がN−1をいうことができれば勝てます。

相手にN−1−K≦X≦N−2を相手に言わせれば良い。

自分はNー1ーKー1「Nー1ー(K+1)」を言えば勝てます。

 

相手にNー1ーKー1ーK≦X≦N−1ーKー1ー1を言わせれば良い

自分はNー1ーKー1ーKー1「Nー1ー2(K+1)」を言えば勝てます。

 

このように続けていくと「Nー1ーM(K+1)」(Mは定数)を言える時自分は勝つことがでいます。逆にこの値を相手に言わせてしまうと負けになります。自分は先攻で自分の初期状態は0であるためこの値が0と等しいと自分はこの値を宣言することができません。そのような場合相手は必勝法を使うため自分は勝てません。

つまり

Nー1ーM(K+1)=0

が成り立つ時

すなわち

N=M(K+1)+1の時

負けます。

したがって

N mod (K+1) == 1の時負けとなります。

 

以上解説でした。

二分探索木:削除

アルゴリズムとデータ構造】二分探索木:削除(解説)

9.4の解説をします。

ある節点Zを削除する時を考えます。

・Zが子を持たない場合

 ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い

 

・Zが子を一つ持つ場合

 Zは親と子供に挟まれているので、Zを削除するためには親の子供の設定をZの子

 供に変え、(Zの子供)の親を(Zの親)に変えてあげればZを削除できます。

 

・Zが子を二つ持つ場合

 Zの次節点とは単にZの上の接点のことを指している。Zが持っている2つの子をZの上の節点に移してあげれば良い。そこでZの次節点の値をZ地震にコピーし、Zの次節点を削除してあげればZを削除したことになる。

 

解説のプログラムの解説をします。

 

二分探索木Tと削除対象Zを受け取ります。

そこで削除対象は、Zが子を持つ場合ではZの次節点でした。そこで削除対象をYに移します。子を持たない、子を1つだけ持つ場合ではY=Zであり、Zが子を持つ場合はZの次節点をYに代入します。

 

次に削除対象の子供を調べます。

左に子があれば左の子をxに代入します。

左に子供がない場合にはxに右の子の値を代入します。この場合実際に右に子供がいなくても構いません。あとで処理します。

 

そしてxがNILじゃないつまり削除対象の子供が存在する場合、削除対象の親を、削除対象の子供の親に設定します。

 

削除対象の親が存在しない時、その削除対象の子供を根とします。

削除対象がその親の左の子供の場合には、左の子供の位置に削除対象の子供を入れます。

削除対象がその親の右の子供の場合には、右の子供の位置に削除対象の子供を入れます。

最後の子供が二ついた場合において次節点が削除された場合

つまり削除対象がZと異なる場合

Zの値に、削除対象の値を代入します。

 

次節点を求めるアルゴリズムの解説

右の子供が存在する場合は値が一番小さい節点が次節点となるので、その節点を調べて返します。

右の子供が存在しない場合には、自身が左の子供になっているような節点の親が次節点となる。

次節点は以下のようにして探索します。まずYにXの親を代入します。

そのYが存在するつまり根ではないかつ、右の子供がXである限り以下の操作を繰り返します。

 

まずXとYを位置関係そのままで上に移していきます。

つまりYはXの親であるから、XにYを代入

YにYの親を代入

を繰り返すことで次節点を探索することができます。

 

次に二分探索木での最小値を求めるアルゴリズムの解説をします。

最小値となる候補はその値かその左の子供であるめ左の子供について一番深い場所にある節点を探索していきます。

Xの左の子が存在するまで繰り返します。

そうすることで二分探索木の最小値を求めることができます。

 

一般的に二分探索木では木の高さをできるだけ低く維持する必要性がある。

バランスのとれた木を平衡二分探索木という。

 

 

 

 

二分探索木:探索

アルゴリズムとデータ構造】二分探索木:探索(解説)

215ページの解説をしていきます。

 

まずどこから探索していくかの基準となるxと調べる値kを引数として受け取ります。

そのあとxをどんどん移していくのですがそのxの値が存在しなくなるまたは、keyにたどり着くまでループ内の作業を繰り返します。

kの値がその基準のxよりも小さい場合にはxを左の子へ移し、大きい場合にはxの子を右の子へ移します。

 

この操作を繰り返すことで、節点を探し出すことができます。

 

以上解説でした。

 

二分探索木:挿入

アルゴリズムとデータ構造】二分探索木:挿入(解説)

9.2の二分探索木の解説をしていこうと思います。

 

209ページのプログラムの解説

 

まずルートから挿入する位置を探索するのでyにNIL(rootを表す)を代入します。

ルートであれば親は持っていないはずです。

そしてまずルートの値と比較するために比較対象にするxにルートを代入します。

以下ループで代入する位置の親となるyを探していきます。

まずどこまで探索できるかわからないためxの値を親としてまず保存しておきます。

 

そのあとxのkeyの値とzのkeyの値を比較し、それよりも小さいならば比較対象をxの左の値に移します。大きいならばxを右の値に移します。

そしてこの作業を続けていき比較対象を移していくと値が入っていない接点にたどり着きます。その時yにはその値が入っていない親が入っています。

それをzの親として代入します。

 

最後にy == NIL、親がいない、つまり xの挿入位置がルートならばTのルートにzを挿入します。そしてzの値が親の値y.keyより小さいならば親の左の子にzを挿入します。

大きいならば親の右のことしてzを代入します。

 

以上擬似コードの解説でした。

 

 

 

競技プログラミング始めました

今年はプログラミング技術向上のために

競技プログラミングを頑張っていくことにした。

 

まあそんなんで今蟻本を解いているのですが、動的計画法がよくわからん、、、

 

なので蟻本に載っている練習問題を解いていくことにした。

 

問題は

POJ3176,2229,2385,3616,3280

 

だそうなので少しずつ解いていく。