本履歴

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

数学パズル本に敢てプログラムで挑戦(7)

今日も今日とて、マーチン・ガードナーのMy Best Mathematical and Logic Puzzlesを眺めていたら見つけた問題。 39. The Game of Hip 6x6のチェッカーボードに先手後手が黒石、白石を置いていく。自分の石で正方形(斜めも可)を作ったら負け。この時、引き…

Google Code Jam Qualification Round 2017 C

C Bathroom Stallsは横一列にトイレの個室がN室並んでいて、そこにK人が現在使用中の個室から遠くなるように未使用個室入っていくというシチュエーション。漏れると思うんですけど・・・。問題文読んだ瞬間すわDPか?と思ったが全く違っていた。いわゆる電線…

Google Code Jam Qualification Round 2017 B

B Tidy Numbersは数字(の10進数表現)が1123456など非減少列になってるものをtidyと定義し、与えられたN以下で最大のtidy数を求めるもの。まずはtidyかどうかを判定するメソッドtidy?を作る。次に、与えられたNがtidyならそれを出力して終了なのでtidyで…

Google Code Jam Qualification Round 2017 A

待ちに待ったGoogle Code Jam。今年もやっていきますよー。 A. Oversized Pancake Flipperは上下逆さまになったパンケーキがN枚与えられるので全部表を向くよう並び替えるもの。ただし、K個の連続したパンケーキを一遍に並び替えるフリッパーを使わなきゃい…

CodeIQ

CodeIQで出題されていたマヨイドーロ問題を解いてみました。出題者は数学ガールでお馴染みの結城先生です! 使ったアルゴリズムは動的計画法ですが、どういう風に私がこの解に到達したのかを時系列を追って説明したいと思います。問題文を読んですぐに思いつ…

CodeIQ

CodeIQで開催されていた@cielavenirさんのRestricted WordsのRubyで提出した自分のソース公開。わーい、評価5頂きました。 方法はmethod_missingでメソッド名を取得する方法。 それだけだとつまんないので、本文を英語の文にしてみました。 後で、スペース出…

競技プログラミング

昨日参加できなかったAtcoder#014の問題をRubyで解いたので。全部解けたのは初めてかも。 A. 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう 偶奇性を問われてる。ワンライナーで。 puts gets.to_i%2<1 ? "Blue" : "Red" B. あの日したしりとりの…

コードゴルフ

そういえば、前に参加していたCodeIQのこっちのゴルフコンペもソースコード公開。最初のCゴルフの2次元連立方程式の問題。 C言語は通常まったく書かないけど(=ゴルフ専用)、頑張ってみたら、なんとか上級超えられた。わーお。 scanfする時に&a,&b,&c,..と…

コードゴルフ

CodeIQのid:Ozyさん開催コードゴルフコンペに参加していたので、自分のコード公開。 提出期限の月曜の明け方に縮めてた。縮まりまくって、徹夜だよ・・・あるあるーw 最初にハッシュにx,yでの値を保存していたけど、結局、1次元配列の方が短くなることが判…

GCJ2013(Google Code Jam 2013 Round 2)

さあて、Google Code Jam 2013 Round2。目標は1000位に入ってTシャツをゲットすること。 夕方から仮眠を取り、1時間前に起きて、幅優先探索と深さ優先探索とダイクストラのアルゴリズムを復習し、 日本時間土曜日23時からいざスタート。問題Aを読んだ瞬間、…

競技プログラミング

Golf関係でCodeIQのアカウントを取ったのだが、計算幾何学の問題があったのでちょっと解いてみた。 https://codeiq.jp/ace/stakemura/q296 フィードバックが返ってきてるので、ソースコード公開してもいいんだよね。 Computational Geometry: Algorithms and…

競技プログラミング

最近codechefサボってたんだけど、GCJ(Google Code Jam 2013)が開催中なので、腕試しに出てみたら五問解けた。あれあれ?簡単になってる?? Rubyで解くよう頑張った。 Matchsticks(http://www.codechef.com/MAY13/problems/MSTICK) 今月の中ではMatchsticks…

GCJ2013(Google Code Jam 2013 Round 1C)

Round 1Cは練習でponanza戦を観戦しつつ参加してみた。ラウンド中はinputを落とせないので、紙と頭のなかで解いて、後日コーディングしてみた。 Aは問題文を読み間違いして全然見当違いのコードになってた・・・ので後で解く。 ([1,0,1,1,1,0,1,0]なる1,0か…

GCJ2013(Google Code Jam 2013 Round 1B)

Round 1Bは毎回深夜回。土曜夕方、なぜか成分献血して、その後20時から仮眠を4時間取ってAM1時スタート。 前回からの変更点はTextEditorがsublime(registered!!)になったこと。買っちゃいました。てへぺろ。問題Aが吸収ゲーでSとLで点数に差がない、Bは…

プログラミングコンテストの練習

とっておきの数学パズルから次の問題。 一列に50個のコインが並んでいて、先手後手が両端いずれからか一つコインを取っていきそのコインに書かれている金額を得る。最後のコインを取った時に総金額が多いほうが勝ちとする。この時、先手が負けない戦略を考…

GCJ2013(Google Code Jam 2013 Round 1A)

今年のGCJ Round 1は、ひとつの週末に固まっていないのがうれしいなと思ってのんびりしていたら、あっという間に当日になり、GW初日の土曜日10時から開始。 8時に起き、いい天気なので部屋を掃除してたら開始5分前になっていてびっくり。急いで準備して30秒…

プログラミングコンテストの練習

http://rubygems.org/gems/algorithms の中からHeapwikipedia:ヒープを使ってみよう!そもそもHeapってPascalでしか書いたことないし、配列で2分木を表現するBinary Heapで今まで十分だった。 必要な操作は、pushと(最大値/最小値)のpop、sizeくらいかな。…

プログラミングコンテストの練習

Google Code Jamが通常のプログラムコンテストと違うのは、ローカルで答えを出せばいい点、 つまり標準ではないライブラリが使える!!!わおー ということで、役に立つかはわからないけど、自分が知っているRuby gemを紹介させてください。 今回はmemoize。…

GCJ2013(Google Code Jam 2013 Qualification Round)

さあて、今年もやってきたGCJ 2013! ハンドルuruで参加しています。(http://www.go-hero.net/jam/13/name/uru) 当日は電王戦第四局を観つつ解こうと思っていたら、将棋が大変なことになって、GCJどころではなかった。 それでも問題文はひと通り眺めていて、…

プログラミングコンテストの練習

Puzzles for Hackers:スクリプトキディから大人のハッカーへ (IT Architects' Archive 知の連環)に載っていた覆面算をRubyで。 HACKER+HACKER+HACKER=ENERGY 一般の覆面算は総当りでやるしか無いのだろうけど、これは3*HACKER=ENERGYで両辺6桁の数なので、 …

プログラミングコンテストの練習

二分探索木をRubyで書いてみた。極悪データの追加とランダムデータの追加で処理時間を比べてみた。 バランスを取ることの重要性がわかるなあ。 次は乱択アルゴリズムのTreapを実装して、極悪データに対処してみる。 class Node attr_accessor :value,:parent…

プログラミングコンテストの練習

NxNのチェス盤にクイーンN個を互いに攻撃し合わないように置く置き方は何通りか? Rubyで書いてみた。再帰の問題だけど、木をDFSしてるわけだし、途中で探索やめてるし(枝刈り?)、なかなかいい問題じゃん。 N=12 $column=Array.new(N,false)#横方向 $up=A…

プログラミングコンテストの練習

ハノイの塔をRubyで。塔といえばこれが一番有名かもしれない、ハノイの塔。(バベルも有名か・・・あ、天国の塔もBGMで)最初に書いたコード #move n-th disc from x to y with using z def hanoi(n,x,y,z) if n==1 puts "Move disc %d from %d to %d"%[n,x,…

プログラミングコンテストの練習

トポロジカルソートをWikipediaを参考にRubyで書いてみた。 トポロジカルソートとは、(これも名前がいけてない気がするが・・・)、DAGを左から右に進むように一列に並べること。一意ではないが、存在は示せる。 数学的には、DAG(半順序)を拡張し、すべて…

プログラミングコンテストの練習

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~に載っていた問題をRubyで。 こういうパズル的な問題面白いなあ。 class Stack def initialize @stack=[] end def push(n) @stack.push(n) end def pop @stack.pop end en…

プログラミングコンテストの練習

この動画のおねえさんが好きすぎて困ってしまうのですが、、大好きすぎて日本科学未来館の展示にも思わず行ってしまったほど。 TAOCPが全巻揃っていた・・・あの声が館内に響きわたっていたなあ。 ちなみに、Knuthのコンピュータ科学者がめったに語らないこ…

プログラミングコンテストの練習

ポリアの組合せ論入門(-組合せ論入門)に面白い問題があったので、ちょっと考えよう。 二項係数の偶奇性を求めるアルゴリズムを考えよ 二項係数はn個の中からk個選ぶ組合せの数n_C_kだったね。n_C_k%2、なんだ簡単じゃんといかないのが面白い。 愚直に まず検…

競技プログラミング

今月のCodeChef(http://www.codechef.com/JULY12)は、5問解けた。どこかで見たようなのが多かったなあ。 Gift Rift(http://www.codechef.com/JULY12/problems/SAD) 行列が与えられるので、行の中で最小かつ列の中で最大となっている数値を答えろ、な問題。 …

GCJ2012(Google Code Jam 2012 Round 2)

結局、Round 1は999位でぎりぎりパスできたのだが、Round2で撃沈。Rank: 1863 Score: 6 Round 2 土曜の23時スタート。ドデカミンストロングを飲んで頭をすっきりさせ挑んだ。 まず、点数と問題文を眺めてDは迷路っぽので後回し。Aが点数的に簡単そう。Cは図…

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

Algorithms and Programming: Problems and Solutionsにあった次の問題を考えてみた。 ソートされた2つのn次配列xとm次配列yと整数qが与えられる。 i,jをうまく選んでx[i]+y[j]をqに近くせよ。計算量O(n+m) わからなかったのでヒントを参考に・・・ 新しい…

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直接発行してもだめ…