シャンテン数計算と有効牌計算

シャンテン数計算と有効牌計算のプログラムを書いてて思ったんだけど、 123456789m北北北北みたいな手牌はイーシャンテンと見なすのが普通なのかな。今のプログラムはテンパイ(空テン)と判断してしまうんだけど。

2009-12-16

12/15-16

PKU

12月15日 16. PKU 1217 DP。dp[r][a][b]を、「rラウンド後にAの得点がa、Bの得点がbである確率」としてやる。 17. PKU 1226 全探索。 12月16日 18. PKU 2914 無向グラフの全域最小カット。 19. PKU 2920 やるだけ。 20. PKU 2922 経路中最も低い部分の高さを…

2009-12-14

久々にPKU記をつけることにしました

PKU

JOI予選で満点がとれなかったのでPKUを年内に100問解く決意をしたのですが、解法の復習はやはり勉強になるということで記録をつけます。

2009-12-13

情オリ予選

Algorithm

たぶん116点。凡ミスで4点落とすのはもう嫌だお……。というか2でミスったの俺だけだろ……。

2009-11-16

パソコン甲子園2位でした

俺「パソコン甲子園2009の賞金として30万円(1位の賞金)が欲しい。」仕分け人「国民の目線で言うと日本一にこだわる必要はあるのか。」俺「大会の順位と賞金には費用対効果がなじまないものがある。」仕分け人「日本一を目指す理由は何か。2位ではだめなのか…

2009-11-11

エラトステネスの篩

Algorithm Mathematics

1億(108)まで篩ってみると1秒ほど差が出た。アセンブリの方が1.762秒で普通の方が2.772秒。(Core2Quad Q9450) #define MAX 100000000 #define SQRT_MAX 10000 char flags[MAX/8+1]; void Eratosthenes() { __asm__ ("movl $2, %%ecx \n\t" "erloop1: \n\t" "…

2009-11-01

アルゴリズム・イントロダクション第2章第2節の練習問題

Algorithm

2.2-1 Θ(n3) 2.2-2 def selection_sort(A): n = len(A) for i in range(n-1): minimum = i for j in range(i+1, n): if A[minimum] > A[j]: minimum = j A[i], A[minimum] = A[minimum], A[i] ループ不変式は、「第3-8行のforループが開始されるとき、部分配…

2009-11-01

アルゴリズム・イントロダクション第2章第1節の練習問題

Algorithm

2.1-1 2つの41の順序関係が維持されている(安定である)ことに注目するぐらい。 2.1-2 def insertion_sort(A): for j in range(1, len(A)): key = A[j] i = j-1 while i >= 0 and A[i] < key: A[i+1] = A[i] i -= 1 A[i+1] = key 2.1-3 def linear_search(A, …

2009-10-30

WAとAC

neta

WAで萎えてACで興奮するのではなくWAで興奮してACで絶頂を迎える程度の精神力

2009-10-25

ベアストウ法を実装した

Python Algorithm Mathematics

以下の高次方程式の解を全て求められる。試しにを解いてみると >>> solve([16, -152, 324, 162, 80, 50]) [(1.7058483573106117e-15+0.5000000000000019j), (1.7058483573106117e-15-0.5000000000000019j), 4.999999960549872, -0.5000000000000036, 5.00000…

2009-09-02

Knuth's Algorithm XとDancing Linksの解説

Algorithm

Exact Cover Problem 今回解説するKnuth's Algorithm Xは、Exact Cover Problemという問題を解くためのアルゴリズムです。Exact Cover Problemについてはうまい日本語訳が分からない(「敷き詰め問題」とか？)ので英語のまま書いています。数学で言うと、ある…