Arantium Maestum

プログラミング、囲碁、読書の話題

Python

AtCoder Beginner Contest 097に事後参加してみた

とりあえずこれから何週間か、1日1つ以上ABCの4問題を解いていこうと思っている。 D問題は読んでから少し放置して暇なときにつらつら考えて、半日たってから実装したりしているので全然コンテスト形式は再現できていないのだが、とりあえず今は自分で問題に…

AtCoder Beginner Contest 098に事後参加してみた

「事後参加」って変な言い回しだな。「の問題を解いてみた」が正しい・・・ abc098.contest.atcoder.jp 例によってPythonで。 第1問 abc098.contest.atcoder.jp abc098.contest.atcoder.jp 入力値二つの和、差、積のうちの最大値を出力する問題。本当に問題…

ナップサック問題

蟻本から: 重さと価値が, の物体n個から、重さの総和がWを超えない部分集合の最大の価値を求める。 解法としてはメモ化か: def solve(vs, ws, W): def max_v(i, max_w, memo = {}): if i >= len(vs): return 0 if (i, w) in memo: return memo[i, max_w] i…

Fence Repair問題

POJ/蟻本から 3253 -- Fence Repair 蟻本の解説がすごく面白かった。 板を切ることを二分木の枝分かれと考えて、最終的に切られた板一片にかかったコストは板の長さX二分木における深さ。 そう考えると、長さが短い板ほど深くするのが正しいことがわかる。の…

Best Cow Line問題

POJ/蟻本から: 3617 -- Best Cow Line ある文字列の左右どちらかの端から文字を1個ずつ取って、lexical orderが最小になる文字列を作成する、という問題。 最初は舐めていたのだが、bacbなどを正しく処理するためには先読みが必要になる。 しかしbbbbbacbbb…

区間スケジューリング問題

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

迷路の最短路問題

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

Lake Counting

蟻本&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 Paper

例によって競プロの記事から簡単面白そうな問題を解いてみる。 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+…

PachiCockroach

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

PythonのCurioライブラリ

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

Python代入の流れーナンダコレ

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

Alex Martelli版エラトステネスの篩をClojureで書いてみた

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

Design of Computer Programs

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

Python 覆面式ソルバー 終

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

Python 覆面式ソルバー 続続続

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

Python 覆面式ソルバー 続続

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

Python 覆面式ソルバー 続

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

Python、再帰とダイナミック・プログラミング 微調整

以前書いたこのエントリーの最後のコードだが 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でよくないか?と気になっていた。(が…

Python 覆面式ソルバー

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

Python、再帰とダイナミック・プログラミング

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…

PEP8を超えて

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

Python Code Snippet - 最大の三連続

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

Python stdlib reading - antigravity

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