Arantium Maestum

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

Python

PythonでForth処理系を書く! その7(繰り返し処理 DO-LOOP)

繰り返し処理を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも書いた通り、この構文の要素は3つあって: DOでスタックに乗っている二つの整数を分岐のために使う スタックから得たはじめの整数がループカウンタの…

PythonでForth処理系を書く! その6(条件分岐 IF-ELSE-THEN)

条件分岐を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。 上記の記事からの再掲になるが、このような構文で: 1 IF 2 ELSE …

PythonでForth処理系を書く! その5(Read-Eval-Print-Loop)

REPL機能を実装する。 main.pyに引数がなければREPLを実行するようにする(引数としてファイル名が渡されていればそのファイルを実行)。REPLは一行ずつユーザからForthコードを受け取り、今まで受け取ったコードの環境を引き継ぎつつ実行する。 github.com …

PythonでForth処理系を書く! その4(内部状態をPython Dictionaryに保存)

前回の終わりで書いたように、Forth処理系の内部状態、とくにコンパイラ部分とインタプリタ部分のものをデータ構造として抜き出して、保存・出力できるようにしたい。 その変更がこれ: github.com 主要な変更は二点: 内部状態をPythonのDictionaryで表し、…

PythonでForth処理系を書く! その3(最低限の機能)

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestum でも書いた通り、まずは以下の機能を最低限として実装する: 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数…

PythonでForth処理系を書く! その2(実装する機能)

処理系で実装する機能を列挙してみる。 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数をひとつとり、その数を標準出力に表示する 標準出力に改行を表示する REPL機能 分岐構文 IF-ELS…

AtCoder Beginner Contest 094の問題を解いた

第1問 Cats and Dogs abc094.contest.atcoder.jp abc094.contest.atcoder.jp 猫がA匹いることがわかっているのに加えて、追加で猫か犬かがB匹いる場合、猫がX匹いることが可能か。 不可能になるのはX < AかX > A + Bの二ケースなので、A <= X <= A+Bが成り…

PythonでForth処理系を書く! その1(序)

Forthというプログラミング言語がある。分類としては「スタックマシン型言語」になるだろう。 スタックマシンというのは、データやアドレスをスタックに乗せたり取り出したりすることを基本の操作とするプログラム実行モデルで、有名どころでいうとJava Virt…

AtCoder Beginner Contest 103に参加してみた

今回はノーミスで全完したのだが、C問題にあまりにも時間がかかってしまい、実感としてはかなりまずい印象だった。 前回のABCから三週間ぶりで感覚がおかしかった気がする。 第1問 abc103.contest.atcoder.jp abc103.contest.atcoder.jp 「最小→真ん中→最大…

蟻本初級編攻略 - 2-4 Union Find木 後編

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

蟻本初級編攻略 - 2-4 Union Find木 前編

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

蟻本初級編攻略 - 2-4 二分探索木

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

蟻本初級編攻略 - 2-4 Expedition

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

AtCoder Beginner Contest 102に参加してみた

第1問 abc102.contest.atcoder.jp abc102.contest.atcoder.jp 入力値nと2の最小公倍数を求める問題。nが偶数ならn、そうじゃないなら2*n n = int(input()) print(2*n if n%2 else n) 第2問 abc102.contest.atcoder.jp abc102.contest.atcoder.jp Aの(添字…

OCamlでTypical Dynamic Programming Contest E問題を解いてみた

ここ一ヶ月ほどAtCoderをPythonですすめてきて、Pythonの遅さにひやりとすることはあっても基本的にアルゴリズムがあっていて素直な最適化を施していればABCの問題であれば通せそう、という感触を得ている。 しかし少し上の問題を見てみるとそうはいかないよ…

トポロジカル・ソートをPythonで実装してみた

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

桁DPに入門してみた

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

蟻本初級編攻略 - 2-2 Saruman's Army

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

蟻本初級編攻略 - 2-2 ABC009C 辞書式順序ふたたび、ふたたび

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

蟻本初級編攻略 - 2-2 Best Cow Line

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

蟻本初級編攻略 - 2-2 硬貨と区間

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

蟻本初級編攻略 - 2-1 特殊な状態の列挙

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

蟻本初級編攻略 - 2-1 迷路の最短路

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

蟻本初級編攻略 - 2-1 Lake Counting

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

蟻本初級編攻略 - 2-1 部分和

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

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

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

AtCoder Beginner Contest 100に参加してみた

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

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

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

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 入力値二つの和、差、積のうちの最大値を出力する問題。本当に問題…