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

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

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

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

前回の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 現在…

第１問 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) 第２問 abc102.contest.atcoder.jp abc102.contest.atcoder.jp Aの（添字…

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