蟻本から。 n個の作業がある。 各作業は開始時と終了時が決まっており、同時に二つの作業をすることはできない。 作業をどう選べば、完了した作業数を最大化できるか。 かなり有名な貪欲法の問題。ポイントは、開始時や長さではなく、終了時を基準に選んでい…

蟻本から。 スタート、ゴール、壁、通路が'S', 'G', '#', '.'で表されている二次元配列の地図で、スタートからゴールまでの最短経路（必ず存在する）の長さを返す。 ざ・BFS。 import itertools as it def solve(map_): def neighbors(i,j): dirs = ((i+i1, …

蟻本&POJから水たまりを数える問題： 2386 -- Lake Counting ナイーブに書くなら： import itertools as it def solve(map_): lakes = {(i, j):set((i,j)) for i, row in enumerate(map_) for j, v in enumerate(row) if v == 'W'} def neighbors(i, j): n =…

06/19/2018追記：コードを書き直した&AtCoderの類題を解いた プログラミングコンテストチャレンジブック、通称蟻本を読み始めてみる。 とりあえずPythonで解いていって、C++の勉強が進んである程度綺麗に書ける気がしてきたらC++でもやってみたい。 まずは部…

例によって競プロの記事から簡単面白そうな問題を解いてみる。 Shredding Company | Aizu Online Judge import itertools as it import heapq def solve(k, n): s = str(n) if k == n: return (n, [s]) a = it.product((0,1), repeat=len(s)-1) b = ([0]+[i+…

最近ちょっと競技プログラミングに興味が出ている。理由としては四つあって、 C++の練習などにいいのではないか アルゴリズムとデータ構造をより身近にしたい 頭脳パズル的なものをもっとしたい 最近インタビューアとしてアルゴリズム関係の質問をする側に回…

Twitterを見ていたらDavid Beazleyがこんなつぶやきをしていた。 Curio abides. https://t.co/cPqEfr6dOD— David Beazley (@dabeaz) 2016年5月30日 Curioってなんだ？とリンクを辿って読んでみたら去年のブラジルPyconで話した内容をさらに進化させたライブ…

stackoverflow.com a, b = a[b] = {}, 5 Raymond Hettingerの過去ツイートを追っていたら、これってどうなるんだ？とわからなかった式があった。 結果はa = {5:(a, 5)}、b=5と再帰的なディクショナリーができる。 肝は代入式の評価順で、a = b = c = dの場合…

素数算出アルゴリズムで最も有名なものは多分エラトステネスの篩だろう。発見した素数の倍数を消していく（篩にかけていく）ことによって、残った数の中で最小のものが素数だとわかる。そのプロセスを繰り返していくことで、一定のn以下のすべての素数が効率…

今週末は約束や予定が５、６個あって大変そうだなぁと思っていたのだが、金曜日から覿面に風邪をひいて全部ブッチするという非常に申し訳ないことをしてしまった。 頭が少し朦朧としつつも暇だったので、映画やら見ながら（そういえば超久しぶりに「アマデウ…

前回からの続き。 そうこうしているうちに、ついにルール追加である。 以下の二つのルールを追加する。 二つの数の和の一番上の桁に関するルール 二つの数とその和の同じ桁に関するルール その前に、足し算と引き算でルールをケース分けするのはめんどうなの…

前回からの続き。 てなもんで、再帰的に書いたソルバーに、各段階で次のステップに使える数字を絞るルールを組み入れる仕組みを作っていく。 方式としては、入力された文字列を引数にして評価関数を返す高次関数create_rule(input_string)を作成する。その返…

前回からの続き。 というわけで総当たり形式をやめて、なるべく制約を加えることで評価する文字：数字マッピングの総量を絞ってみる。 具体的には for numbers in permutations(range(10), len(characters)): この部分をやめるわけである。じつはこの部分も…

前回からの続き。 ということで高速化に取り組んでみる。 が、その前に、とりあえず短く書いたコードが実際どれくらいかかっているのか、数値化しておく。 import time def time_solver(input_string): start = time.time() solve(input_string) end = time.…

以前書いたこのエントリーの最後のコードだが zehnpaard.hatenablog.com H = {0:0} for n in xrange(1, 2016): H[n] = n - H[H[H[n-1]]] print H[2015] 書いた直後から、そもそも数字がkeyならdictionaryじゃなくてlistでよくないか？と気になっていた。（が…

気がついたら前回の更新から四半期が過ぎようとしている。恐ろしいことだ。 IT速報でまた面白そうな問題があった。 blog.livedoor.jp 複数の文字が同じ数字にマップしないと仮定するなら、そもそも問題の大きさが最大で10!（～360万通り）なので、ちょっと時…

IT速報で以下の記事があった。Pythonでの解き方を少し考えてみた。 blog.livedoor.jp 数列Hが以下のように定義されているとき、H(2015)を求める。 H(0) = 0 H(n) = n - H(H(H(n - 1))) (n > 0) 再帰で書くならかなり簡単である。 def H(n, memo={0:0}): if n…

Python関連の映像では、私はRaymond HettingerとDavid Beazley*1のものが最も好きだ。 まず、どちらも非常に話が上手い。ユーモアを交え、あまり急かした感もなく、それでいて聞き手のことを考えた話の運びであるように思う。あと英語が訛っていないので聞き…

時々メモっておきたくなるようなPythonコードを思いつくので備忘録的に「Python Code Snippet」の題で保存していこうと思う。 今回はStackOverflowで一旦質問として提示されて、あまりにも宿題っぽかった上に質問者自身がなんら解決に向けて努力していなかっ…

StackOverflowなどを読んでいて、Pythonの良質サンプルコードの話になると大抵挙がるのがstandard libraryである。*1 Pythonの哲学の一つにBatteries Includedというものがあり、基本的にPython自体のインストールについてくる豊富なstandard libraryで相当…