Arantium Maestum

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

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

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

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

HaskellでLisp to LLVM IRコンパイラ その5 ( LispValの定義、パーサ作成とSSA中間言語への変換)

LispValという再帰的なデータ型を定義して、まずコードをそのLispValとしてパースする。流れはインタプリタを作った時とまったく同じ。 インタプリタの場合はそこでevalを適用したが、コンパイラの場合はそこからSSA中間言語に変換を加えていく。 LispVal型 …

Haskell私的メモ Monadをリストで探る1

今回はHaskell初心者にとって理解が困難だといわれているMonadの話。 駆け足で頑張って抽象的な概念を理解しようとするのではなく、親しみ深い「リスト型」をモナドとして使ってみることで具体的な感覚を蓄積していこう、という考え。 >>= 前回FunctorとAppl…

Haskell私的メモ FunctorとApplicativeをリストで探る

「モナドとはなにか」「Applicativeとはなにか」といった抽象的な共通性の探索からはじめると挫折するのが目に見えているので、いったんそういったことは置いておいて、まずはいくつかの具体的なモナドと戯れて個別に挙動を理解していきたい。そういった具体…

HaskellでLisp to LLVM IRコンパイラ その4 (SSA中間言語)

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。 その中間言語の各行を表現するデータ型がこれ: data SSA = Alloc String | Store String String | Load String String Lispと違ってこの言語は再帰…

HaskellでLisp to LLVM IRコンパイラ その3 LLVM IRへの出力(数字の出力)

前回に続いてLLVM IRで数字を返す方法を考える。 比較的簡単でこのような形になる: %1 = alloca i32 store i32 3, i32* %1 %2 = load i32, i32* %1 スタック上に%1という変数をalloca命令で用意する %1に3という値を代入 %1に含まれている値を一時変数%2に…

HaskellでLisp to LLVM IRコンパイラ その2 LLVM IRへの出力(簡単なテンプレート)

LLVM IRというのはLLVMコンパイラ・フレームワークが定義・利用する中間言語だ。 https://en.wikipedia.org/wiki/LLVM#Intermediate_representation LLVMフレームワークでは、コンパイラのFront Endはソース言語をこのIRに翻訳することに集中し、Back Endは…

HaskellでLisp to LLVM IRコンパイラ その1

とりあえず作り始めた。 github.com 基本戦略としては、まずは数値計算だけのコードをLLVM IRに変換するのを目的に: Lispコード→LispVal型データ構造→SSA IR→LLVM IR の流れでコンパイルしていく。 長期的にはLLVM IR上でLispValを表すStructを作る必要があ…

`foldr`で`dropWhile`と不動点コンビネータ 補足

以下の記事の補足: zehnpaard.hatenablog.com 式をいじっていて気付いたのだが、不動点コンビネータを使った解は: dropWhile p = foldr (const f) undefined (repeat undefined) where f _ [] = [] f g ys@(x:xs) = if p x then g xs else ys に落とし込め…

Haskellで50行以内のミニマルコンパイラ

こんなツイートが流れてきた: A complete #compiler to x86 in one page for my lecture today. pic.twitter.com/PwFl4V5czy— Joe Gibbs Politz (@joepolitz) 2018年4月11日 元となっているのは"An Incremental Approach to Compiler Construction"という論…

`foldr`で`dropWhile`と不動点コンビネータ

前回のブログの問題元は今は亡き?Monad.Reader第6号の"Getting a Fix from the Right Fold"という記事。 私が考えた答えの「失敗例」は出てくるけど、パターンマッチを使わないで遅延評価が無限リストにも効く解は出てこない。 しかし別解は非常にエレガン…

`foldr`を使って`dropWhile`を定義する

Haskellの高階関数のfoldrでdropWhileを定義せよ、という問題を見たのでやってみる。 foldr foldrの定義は以下のとおり: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f e [] = e foldr f e (x:xs) = f x (foldr f e xs) 「わかってるねんで?foldrがred…

HaskellとParsecでLisp REPL その8(変数定義)

今回の変更 github.com 「ユーザによる変数定義」機能を追加する。 これはかなり大きな変更で、変数の内容を保持・評価するために、変更可能な「状態」を導入する必要がある。 Haskellだと状態をStateやSTモナドで管理することも可能(らしい)のだが、基本…

HaskellとParsecでLisp REPL その7(if構文)

今回の変更 github.com 条件分岐のための構文を追加。 (if a b c)という式は、まずaを評価し、もし真ならbを、偽ならcを評価してその結果が値となる。 bとcのどちらかひとつしか評価されないのが重要なので、関数ではなく構文として定義。 実装としてはeval…

HaskellとParsecでLisp REPL その6(数値比較と論理演算)

今回の変更 github.com 前回Bool値を定義できたので、=、/=、<、>などやand/orを実装する。 Functions Functionsモジュールのprimitivesにどんどん追加していく: primitives :: [(String, [LispVal] -> LispVal)] primitives = [ ... ("=", numBoolBinOp (=…

HaskellとParsecでLisp REPL その5(Bool型の追加)

今回の変更点 github.com ブール値の追加。データ型とパーサの拡張のみ。 データ型 data LispVal = Atom String | List [LispVal] | Number Integer | Bool Bool ちゃんとshowできるようにしておく: showVal (Bool True) = "#t" showVal (Bool False) = "#f…

HaskellとParsecでLisp REPL その4(四則演算)

今回の変更点 github.com ついに四則演算の実装。入力をそのまま返すのではなく、入力を評価・変換して出力するようになり、「ちゃんとしたREPL」にちょっと近づく。 データ型とパーサ 今回は変更なし。四則演算ならAtom、List そしてNumber型だけで十分。演…