素因数分解の方法の一つ。根本的な原理は、ランダムに選ばれた２つの整数a, b(＜N)で GCD(a - b, N)≠1, N となればいいなぁ、ってことで、それ故に「モンテカルロ法」の別名もあるわけです。その「ランダムに選ぶ」方法をアルゴリズムとして定義しましょう。…

N 因数分解する数 p,q 素数 GCD(a,b) aとbの最大公約数。GCD(30,45)=15。

はてなダイアリー内で検索すると、ICPC-Fと似たような解法は何人かの人に思いつかれているので、新しい方法を考えてみた。数値解だ（解析解ではない）けど多分完全解答できる…気がする。 刻み幅 dθ←π/1000 くらいにしてループを回す F(θ)＞F(θ−dθ) かつ F(θ)…

2つアルゴリズムを考えて、片方を実装してみて思ったが、この問題で重要なのはアルゴリズムではないのではなかろうか。いくら問題が難しいとはいえ、自分が挙げた2つの方法や、他の人が提唱している方法のいずれかはMakegumiやclax、kitsune-などの上位選手…

影を動かすアニメーションGIFが面白いかも。あと、先に断っておくけど、この考え方は一般論として通用するかといえば通用しないと思う。サンプルI/Oは通ったけど。大雑把な方法論としては、範囲を少しずつ狭めて探索。θについて影の長さを求める関数 f(θ) な…

今年のICPCは選手資格がないので、コーチ役をしながら脇で自分もチャレンジ。解いた順番はA→F→D→Bの途中でTimeOver。Fのしょうもないデバグで時間くった。コードは…次学校に行った時に乗っけるかも。書き換えて。とっても気になるんだけど、この文言、誰が書…

そういや、全く書いていなかった、一番重要な点。これまで述べたような点も、場合によってはこれ1個で超えられるかも。ということで、今回はコンパイルオプションについて。 一般的に知られてるgccなら % gcc hoge.cとやるのが一番楽なの。そして多少慣れて…

とりあえず、問題設定としてはNxNサイズの正方行列A,B,CについてC=ABと積を計算すること。 C=Oの初期化は別にされてるとして、それ以降の計算。基本的にはこうなる。 for( i = 0 ; i < N ; i++ ) { for( j = 0 ; j < N ; j++ ) { for( k = 0 ; k < N ; k++ )…

オセロの世界チャンピオンが棋譜や考え方などを紹介してくれるらしいブログ。 こっちの参考になればいいなぁ、というのが本心だが、単純に面白そう。 http://blog.goo.ne.jp/becky2002jan

実際に打つ時点に限れば、打つ場所が見つからない場合にはすぐパスを返す。これは打てる箇所が一箇所の場合と同じで、そこから先をどんなに探索しようと結果は同じなので余計な時間を使わない様にすること。それで重要なのは探索中のパスの処理。ここではゲ…

上記のままのアルファベータの実装では評価値は返ってくるけど、どの手を指した結果なのかが全く分からない。かといって、実際指し手の情報が必要になるのは再帰呼び出しの一番上のレベル。ということで、面倒だけどそれだけのための関数を作った。ついでに…

理論は抜き。Min-Maxも、純粋な意味でのアルファベータ探索も抜きにして、最初から Negamax + αβ。さっさと実装に。 int αβ(CELL 色, int α, int β, int 残り深さ) { if( 残り深さ == 0 ) return 評価値(); @打てる場所リスト = 打てる場所を列挙する(色); i…

とりあえず、今のところは #define BLACK (1) // 黒石 #define WHITE (-1) // 白石 #define NONE (0) // 空きマス #define WALL (3) // 枠外黒石と白石が±1なのは、裏返す時に単純にマイナスを取ればいいから、という理由ではなく、評価関数を書く場合に、最…

色々あるが、今回自分が実装するのは超素直な2次元配列の次に下手な1次元配列。具体的には以下のようにインデックスを振ることになる。 00010203040506070809 09101112131415161718 18192021222324252627 27282930313233343536 36373839404142434445 4546474…

研究室の内部でオセロ大会やることになったんで、暫くぬりかべは休み。

浮動小数点の四則演算を速度で比較すると、加算＝減算＝乗算＞＞除算(一般論)、ということになるので多少他の演算が増えようが除算は減らす方がいい。ただし実際には試行錯誤が必要。ということで、上記のプログラムを2倍アンロールして除算を減らしてみる。…

そのまま、ループを展開すること。普通はコンパイラがやってくれるけど、アンロール以上のことを手作業でやれば高速化が期待できる。 元のプログラムがこんなんだとする。 /* Σ[i=1..n](1/i^2) を求める。無論極限値は π^2/6 */ sum = 0.0; for( i = 1 ; i s…