本履歴

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

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

マーチン・ガードナーサム・ロイド本の続き 69. The Canals on Mars 火星で発見された水路を通って各町を必ず一回回ってスタート地点に戻ってくる問題。火星の半球面全体に水路を張るのはすごい技術というか無駄な気がするけど、まあプログラム的にはハミル…

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

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

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

マーチン・ガードナーのサム・ロイド本を眺めていたら見つけた問題。解けそうだったので頭の中で組み合わせ考えたけど結局解けなかった。悔しいからRuby書いてしまいました(笑) 56. How can you score exactly 50 points? ようは、与えられた数の集合{25,…

マジ数学本に敢てプログラムで挑戦(1):包除原理(Inclusion-Exclusion Principle)

SpringerのGTMと言えば黄色のカバーで有名ですが、238 A Course in Enumerationに包除原理を使った面白い問題が Ex. 5.7. How many integer solutions \( x_1+x_2+x_3+x_4=30 \) exist with the restriction ? 上限が無ければよくある問題でcombinationで計…

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

チェス盤のタイリング問題に挑戦。この問題はALGORITHMIC PUZZLESではチュートリアルの例題として載っていた。 まあ有名ですからね。 Domino Tiling of Deficient Chessboards 8x8のチェス盤をドミノ(1*2)で隙間なく埋めることを考える。a)左上が欠けてい…

Cracking the Code Interview 16.19 Pond Sizes

もう1題は深さ優先探索の練習問題。長方形の区画の高さ情報(0は水面)が与えられるので全ての池を求めるというもの。池は上下左右斜めで繋がっているという定義。深さ優先探索は再帰で書くと簡単だけど、たまにスタックがいっぱいになったりするので注意…

Cracking the Code Interview 17.21 Volume Of Histogram

「世界で闘うプログラミング力を鍛える本」の最新版の翻訳が出たとのことで暇つぶしに眺めていたら面白い問題を見つけた。ヒストグラム地形が与えられるので雨が降った時に貯まる水の量を求めるというもの。例えば、3,1,5 という入力だと、3と5の間に高さ2の…

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個の連続したパンケーキを一遍に並び替えるフリッパーを使わなきゃい…

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

プログラムといえばシミュレーション。今回のボールの問題はそれにピッタリ。ボールの増減の推移を追えば自ずと理屈が分かってくる 50. Last Ball (a)20個の黒のボールと16個の白のボールが袋に入っている。その中からランダムに2個取り出し同色だっ…

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

これも有名な問題で、Youtubeなどに解説動画がたくさんある。 www.youtube.com 7. Bridge Crossing at Night 4人の人が懐中電灯で橋を夜間渡るのだが、4人それぞれは渡るのに1分、2分、5分、10分かかり、橋は同時に2人までしか渡れない。二人同時に…

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

どんどん挑戦していく。明日GCJ本番なのに目が冴えてしまってあかん。本日もAlgorithmic Puzzlesより。 49. Missionaries and Cannibals(宣教師と人食い部族) 3人の宣教師と3人の人食い族が船で川を渡る時(同時に2人まで)、両岸それぞれで人食い族の…

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

いったん書くとこれがなかなか面白いのがblogの中毒的な所、というわけで今日も昨日の続きでAlgorithmic Puzzlesを解いていこう。 45. A Knight’s Shortest Path(ナイトの最短路) 100*100のチェスボード上の左下コーナーにナイトが居る時、右上のコーナー…

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

Google Code Jamの季節になると活発になるこのblog。今日(今年w)は数学系パズル本であるAlgorithmic Puzzlesの問題を解いてみましょう。この本、出たばっかりの時にKindleで買ったんですが最近日本語にもなったみたいですね。本屋で見かけた、というか、…

1次元配列中の連続した部分配列で和が最大となるものを求める

UVa: 11951 - Area 事の発端はこの問題(UVa Online Judge)。 長方形の数字の配置が与えられた時にサブ長方形で和が最大となるもの(ただしK以下)を求める問題。DP[x, y] = Sum(1, 1, x, y)を使ってO(N^2*M^2)の解法はTLEっぽいので、最終的に長方形の数字…

Rubyで任意の順列の次を求める

next_permutation in Ruby 他言語にはnext_permutationがあるのにRubyに無いのはけしからん、ということでnext_permutationを実装しました。 比較可能なオブジェクトからなる配列を渡すだけです。O(n)なので[*1..n]の全順列をiterateする場合はArrayのpermut…

各種Heap処理速度の比較1

The Heap implementation can make significant difference Google Code Jamも2016 R1BがそろそろということでWEBをさまよっていたらいろいろな人の優先順位付きキューがgemとして公開されていたので、自分の実装と比較してみた。 GitHub - matiasbattocchia…

Rubyだとダイクストラ最短路アルゴリズムはバイナリヒープよりスキューヒープ実装の方が速い?!

Skew Heap might be way faster than Binary Heap in Dijkstra Algorithm in Ruby 気になっていたデータ構造Skew heap - Wikipedia, the free encyclopediaを筆のすさびにRubyで書いてみたら、結構速い。もしやとchange_keyも作ってダイクストラの最短経路ア…

「の」の字形の無限に循環する配列のk番目

K-th Value of Japanese Hiragana Character "の"-like Infinitely Circulating Array コンピュータは有限しか扱えないので前の状態から次の状態が決まる系は最終的に必ず循環します。そんな循環する状態列のk番目をここでは求めたいと思います。例えば、み…

Identifies mirrored and rotated one

したがって面白くするため、回転・鏡像を含めて同一視した場合にどのくらいになるか手で数えてみた。なんとなく偶数になると思っていたが、N=4の場合は7という数字が出てきて不思議な感じ。これは配置によって回転・鏡像変換8通り全てが異なる順列になる場…

N Rooks = N!

チェスにハマったので、8 Queensのカウンターパート的8 Rooksを考えてみた。チェスでRook(ルック、lookと発音は違う)は将棋で言うところの飛車の動きをする駒で、それを8*8のチェスボード上に互いに攻撃しあわないよう置くことを考えることになる。これは…

Faster DP Implementation of Integer Partition Function with the Complexity O(N^2)

そこで色々調べた所、蟻本にO(N^2)の方法が載っている事がわかって一件落着。こちらもDPだけど、分割する数を取るのが違う点。 DP[n,m]=nをm個以下で分割するときの総数とするとDP[n,m]=DP[n,m-1]+DP[n-m,m] nをm個以下の整数の和にするときに0も含めて考え…

Naive DP Implementation of Integer Partition Function with the Complexity O(N^3)

整数を分割したい病に患ってしまった。見る整数はなんでも、4=1+1+1+1=1+1+2=1+3=2+2のように分割してしまう恐ろしい病気だ。ちなみに4の場合の分割数は5である(自身も含める)。Wikipedia(https://en.wikipedia.org/wiki/Partition_(number_theory) )を読…

Pure Implementation of Dijkstra's Shortest Path Algorithm with Priority Queue in Ruby

プログラム言語 Ruby での純粋ダイクストラ最短経路アルゴリズム(優先順位付きキュー利用)です。O(m*log(n))の実行時間です(n:ノード数、m:辺の数)。 外部ライブラリなどに依存していないため、このままコピペすれば競技プログラミングで使えると思いま…

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次元配列の方が短くなることが判…