DPとはDAGの最短経路を、トポロジカルソート順に埋めていくことで計算する手法という話からそもそもトポロジカルソートってどうやるんだっけ？となり、Pythonで一つのアプローチを実装してみた： from collections import defaultdict, deque v, n = map(int…

昨日のAtCoder ABC101でD問題に歯が立たず非常に悔しかったので、桁関連の問題や解法を少し読んでいる。 その経緯で桁に関する動的計画法（桁DP）について下のすごい記事に遭遇した： pekempey.hatenablog.com 今蟻本でも動的計画法の章を読んでいることだし…

蟻本の貪欲法で「交換しても悪化しないことがわかっている中で最大のものをとる」という考えの例題： 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にリアルタイム参加もしたし、今…

この回はD問題がけっこう面白かった。ちょっとコードも解説も多めかもしれない・・・ abc095.contest.atcoder.jp 第１問 abc095.contest.atcoder.jp abc095.contest.atcoder.jp 700円のラーメンに味玉、チャーシュー、ネギのトッピング（各100円）するか否か…

初リアルタイム参加。言語はPython3。 「ABCって二週間おきにあるのかな？次は6/23か」とのほほんとしていたら 今日は記念すべき100回目のBeginner Contest、AtCoder Beginner Contest 100なので、ぜひぜひ参加してみてくださいな！Hello Worldが出力出来れ…

今日も今日とてAtCoder ABCを解く。 abc096.contest.atcoder.jp 第１問 abc096.contest.atcoder.jp abc096.contest.atcoder.jp 1月1日、2月2日、10月10日といったようにX月X日のようになっている日が年始からa月b日までに何日あったかを数える問題。 a, b = …

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

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

ツイッターでいろいろ流れてきて面白そうだったので競技プログラミングサイトのAtCoderで問題を解き始めている。 手始めに直近のこれをやってみた： abc099.contest.atcoder.jp コンテスト開催中に参加したわけではないのだが、とりあえずPythonで解いてみた…