前回のUnion Find木実装を踏まえてAtCoder ABC/ARCのD問題や蟻本の元の例題に取り組んでみる。 ABC049 D問題 - 連結/Connectivity abc049.contest.atcoder.jp abc049.contest.atcoder.jp 道路ネットワークと鉄道ネットワークが走っている国で、街ごとに道路…

「ある集合の二つの要素が繋がっているか」を効率的に判定できるデータ構造であるUnion Find木の話。 非常に簡単でエレガントな実装のわりに非常に強力な概念だという印象で、個人的にはとても好き。 蟻本の例題が一番特殊で面白いので後回し。まずはAtCoder…

蟻本の章名である「二分探索木」というサブタイトルを付けたが、Pythonなので二分探索木使わない。setもdictもハッシュマップだ。 ABC085 B問題 Kagami Mochi abc085.contest.atcoder.jp abc085.contest.atcoder.jp 上に乗せる鏡餅は下の餅より直径が小さく…

動的計画法関連のところはPythonでやるとTLEする問題もいくつかあり、OCamlでやることも視野に入れつつ少し寝かせておく。 というわけで先にPriority Queueを使った問題３つ。まずは蟻本に載っているPOJ問題から： POJ - Expedition 2431 -- Expedition 現在…

蟻本の貪欲法で「交換しても悪化しないことがわかっている中で最大のものをとる」という考えの例題： Saruman's Army - POJ 3069 - Virtual Judge 直線上に配置された人のうち最小何人選べば、すべての人が選ばれた人の一定距離内におさまるかを求める問題。…

zehnpaard.hatenablog.com 昨日の続き。 AtCoderの「辞書式順序ふたたび」の解法がまだややこしかったのでいろいろといじり続けたら最終的にコードが短くなり、処理速度も三倍ほど上がった。 abc009.contest.atcoder.jp 昨日の時点でのコード： from collect…

POJからのBest Cow Lineという辞書順についての問題。 Best Cow Line - POJ 3617 - Virtual Judge 牛まったく関係ない。文字列の先頭か後尾から一文字ずつとっていって、辞書順で最小の文字列を作るというもの。 例によって以前も記事を書いていた： zehnpaa…

ようやく全探索章を終え、貪欲法の章に進む。 貪欲法に関して蟻本で出てくる最初の２問はあまり適当なAtCoderの問題がないようだ。とりあえず蟻本の問題を解いていく。 硬貨の問題 1円から500円までの硬貨を特定の数ずつ持っているとして、ある金額に合計す…

蟻本ではちゃんと例題めいたものが載っていなかった話題。 Pythonだとitertools.permutationなどで簡単に実装できる。 ABC054C - One-stroke Path abc054.contest.atcoder.jp abc054.contest.atcoder.jp 重み無し無向グラフを、特定の始点「１」からはじめて…

ここらへんは全部今年の三月に記事を書いているなー。 zehnpaard.hatenablog.com このころは map_をdict化すればかなり綺麗になるが、競プロ的にどうなんだろう・・・ などと言っていたが、現在は躊躇なくdictionary化するなあ。実際そこのO(N)が問題になる…

やはり以前もブログに記事を書いた問題。 zehnpaard.hatenablog.com やはりコードが長い、というかごちゃごちゃしている・・・ 今だったらこう書く： from itertools import product n, m = map(int, input().split()) lake = [input() for _ in range(n)] l…

定期的に「蟻本を全部読むぞ！」と思って読み始めては放置、を繰り返している。 そもそもAtCoderやCodeForceに参加することなく「ある程度読んでから競プロ試してみよう」と思っていたのが間違いだったのではないか。 ABC100にリアルタイム参加もしたし、今…

蟻本から： 重さと価値が, の物体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…

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

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, …

蟻本&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++でもやってみたい。 まずは部…