本履歴

購入した古本の履歴と時々プログラミング

GCJ2012(Google Code Jam 2012 Round 1)

Round 1A GWを満喫するためにどうしてもこのラウンドで通過を決めたいところ。 A,Bの問題文を一瞥し、Aのsmall,largeが同じスコアなのでA,B,Cの順に決定 Problem A. Password Problem 問題の意味がわからず手こずった。幸先悪いなー。 各ストラテジーごとに…

再帰の練習

このあいだ買ったKindle本「Algorithmic Puzzles」より、つーかよくある問題だな。 Cover a 2^n ×2^n board missing one square with right trominoes, which are L-shaped tiles formed by three adjacent squares. The missing square can be any of the b…

GCJ2012(Google Code Jam 2012)

奥さん!今年も始まりましたよGCJ2012。もっちろん参加、で、D.Large以外なんとか解けて、75点。予選通過できました! ニックネームuruで参加していますよ。 Scoreboardの画面でFriendタブに行き、右上のボックスにuruと入れて、Add friendボタン押せばOKで…

競技プログラミング

今月のCodeChef(http://www.codechef.com/MARCH12/)は、5問解けた。簡単な問題が追加されたのでなんとか一問解くという目標が意味なくなったなw Spoon in Matrix(http://www.codechef.com/MARCH12/problems/SPOON) Rubyで正規表現でチェックした。Rubyおせ…

色々比較(アルゴリズム、Ruby v.s. Pascal、optimizationスイッチ)

The Algorithm Design Manualを眺めていたら、Median(wikipedia:中央値)を求めるのはソートして真ん中の値だからO(N*logN)かかりそうだけど、 クイックソートをちょっと変形するとO(N) expected timeで計算できるぜよ、とあったので考えてみた。 競技プロ…

木構造

印象に残ったので書いておく NWERC 2011 Semi-Live online contest(http://www.spoj.pl/NWERC11/) Bird treeより 既約分数a/bが与えられたときに、Bird Tree(http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdf)上でRoot(1/1)からその分数までの辿り…

プログラムコンテストの練習問題

同じくAlgorithms and Programming: Problems and Solutionsより 一本道でn個の駅を持つ鉄道があり、i番目の駅からj番目の駅までの料金a[i,j]が与えられたとする時、1番目の駅からn番目の駅まで行く最小料金は? dp[k]をk番目の駅からn番目の駅までにかかる…

プログラムコンテストの練習問題

Algorithms and Programming: Problems and Solutionsにあった次の問題を考えた。 (Moscow programming contest) ソートされている自然数の配列aが与えられる。 aのある部分集合の元の和として表現されない最小の自然数は何か? うーん、ありがちな問題だ。 …

CodeChefネタ

今月(http://www.codechef.com/NOV11)は、New Restaurant(http://www.codechef.com/NOV11/problems/NEWREST)が考えさせられた。問題文はこんな感じ 自然数N,M,Kが与えられたとする。M個の異なった要素のものをN個重複順列する中で要素の種類が高々K個になる…

動的計画法ふたたび

組合せ論の精選102問 (数学オリンピックへの道)に次のような問題があった。 nを整数とする。{0,1,2,3}のいずれかを係数とする多項式P(x)であって、 P(2)=nとなるようなものの個数を求めよ。 ぱっと見、DPなのでプログラム書いてみた。 require "memoize" inc…

動的計画法を使ってみた

プログラムコンテストをやり始めて一番納得いかないは動的計画法。Dynamic Programming(DP) まず分かんないのは、その名前。全く意味不明。計画ってw 中途半端になんか関係ありそうなのが更に悪い。 名付け親の人には、焼き土下座だな、ぷんすかぷん。 さて…

数学の証明でバイナリサーチ

プログラムコンテストをやり始めて一番感心したのはバイナリサーチ。 32回YES/NO Questionすれば、32ビット整数がわかってしまうなんて。 Q01.その数の最上位ビットは1ですか? (中略) Q32.その数の最下位ビットは1ですか?そして、思ってもみない問題で使…

GCJJ2011決勝

前日深夜のCodeforces#89 (Div. 2)に参加し練習はOK(といってもA,Bしか解けなかったが)。いざ決勝。 問題をA,B,Cと読んで、Bから解くの決定。Aは出力の精度が曖昧だったので保留。 問題B. バクテリアの増殖 まず、powmodメソッドを書いてデバッグOK。b.tim…

A^P mod M

Ladder graph二題 半年ほど前にDiscrete And Combinatorial Mathematics: An Applied Introduction Ralph P. Crimaldi をナナメ読みしてた時期があって、 その中の練習問題にwikipedia:en:Ladder_graphL_nに関する問題があった。当時考えたことを思い出して…

GCJJ2011

震災で延期していたGCJJ2011。もちろん参加、で2問なんとか解けて、(多分)予選通過できました! ニックネームuruで参加しています。問題をざっと読んで(日本語文の競技プログラム初めてかもー)、C,A,Bの順で解くの決定。 問題C. ビット数 まず、10進法で…

GCJ 2011

残念ながらRound1通りませんでした。まあ、楽しかったのでヨシとしますか。 結果 2011→http://www.go-hero.net/jam/11/name/uru (2010→http://www.go-hero.net/jam/10/name/uru) Round 1A 土曜朝。ちゃんと起きられた。Rubyでやる。問題文をざっと読んで、…

GCJ 2011

Google Code Jam 2011 Qualification Round通りました。当日会社があったけど、もちろん休みましたとさ。 結果 2011→http://www.go-hero.net/jam/11/name/uru (2010→http://www.go-hero.net/jam/10/name/uru) 初めての予選全問正解。問題が例年に比べて簡…

GCJ

ニコニコ動画にあったレッキングクルーのTAS動画を見ていたら、なんと! C. Bribe the Prisoners と同じシチュエーションじゃんと気付く。 爆弾叩いて両側に連鎖していくところ。 ロードランナーといい、ディープなファミコン世代が問題を作ってたりして。 …

GCJ 2009

GCJ Round2で負けたので忘れないうちにまとめ(長め)。 結果 2009→http://www.go-hero.net/jam/09/name/uru (2008→http://www.go-hero.net/jam/08/name/uru) 去年はRound2を手を出すことすらできずただ呆然と指を咥えて終わったので、今年Round2で点を取れ…

LEI & PostgreSQL

こちらは何故かInsertがうまくいきません。 Error: ERROR: column "productname" of relation "books" does not exist, Connector 'PostgreSQL Database', Method -Insert- (7) というエラーではじかれます。 pgAdmin IIIからInsertのSQL直接発行してもだめ…

ロータススクリプト

ノーツからこのはてなダイアリーに書き出しするエージェント Sub Click(Source As Button) Dim workspace As New NotesUIWorkspace Dim sess As New NotesSession Dim doc As NotesDocument Dim tempdoc As NotesDocument Dim flag As Boolean Dim dc As Not…

TurboPascal

ボーランドの博物館からターボパスカル5.5がフリーダウンロードできる。僕が大学時代使っていたのは6.0なんだけれど、まぁ、オブジェクト指向の機能は5.5からついているので問題ない。っつーわけで、本棚からターボパスカルの書籍をオモムロに取り出し、プロ…

XML

XMLで設定ファイルを書いてみました。うまく動いています。 読み込ませるだけなのでSAXというAPIで。イベントドリブンな仕様になっていて、へぇーと思いました。 なかなか興味深く、テンプレメソッドやアブストファクトリーなんてデザインパターンが使われて…

i@ppli

前回作ったMINMAXをリファクタリング。 明日に、戦績を保存するのとゲーム終了後バイブすのをつけようと思います。どうやらDOJA3.5で作っちゃうと、API使って無くても古い携帯では動作しないみたいなので。