ICPC模擬国内予選
なんだか阪大のほうにお呼ばれしたので行ってきました。
結果は4ACで4位だったらしいのですけど、普通に出てない強いチームもいるし、解いた問題数的には横並びに10チームぐらいいるので、それほどよろしくない感じもする。
以下、解いた順と流れ
とりあえず、自分がA,Bを解いてる間に他の問題を読んどいてもらうという作戦でいくことに。
スタート
Aひらいてやる。
A accepted (4分ぐらい?)
BもただのBFSっぽかったので、適当に500*500ぐらいの配列用意して塗り絵する。
B accepted (13分ぐらい?)
その後、どうやらCがbitDPだというのでCはまかせてDを読む。
Dはどうやら、実装ゲーっぽいのでCが解けるまで紙にだらだらコードを書く。
C accepted (46分ぐらい)
Dを実装し始めるも微妙によく分からん感じになって、どうせ国内予選はTLEもないので、適当にそれっぽい遅いコードを書く。
実際にデータをダウンロードして、実行すると普通に帰ってこないのでとりあえず走らせたまま飲み物買いに行く。
帰ってくると、どうやら1分ぐらいで終わったらしく通ってしまう。
いいのかこれで、と思ったけど通ったもの勝ちなのでまぁよし。
D accepted (90分ぐらい?)
そっからチームメイトがEを自分がFを考えてたのだけど、Fは複数パターンにたいして文字列の一致をみれる何かが必要っぽく、そんなもの(Aho-Corasickとか)はもちろん持ってなかったので投げ捨てる。
で、最後30分ぐらいはEをずっと考えてたのだけど、自分は直線の傾きを決め打ちする方法しか思いつかず、とりあえず実装してみたけどあってなかったので終了という感じ。
どうやら、チームメイトが積分がうんぬんといってたのが正解の方針だったらしい・・・。
反省
Dまで特につまらずするする解けたのはよかった。
でも、安心するためにはやっぱりもう1問ぐらいは解きたいなぁという感じ。
EorFを解くためには、なんか1ステップ登る必要があるようにも感じるので、なかなか厳しい・・・。
打ち上げ
そのあと、焼き鳥屋に行って飲みまくってカラオケで適当にのどつぶして、酔っ払ったままこれを書いているので、文章は支離滅裂なはず・・・。
今日のうちに書かないと、どうせずっと書かないままなのでそのまま上げてしまいます。
A Contest dedicated to Renat Mullakhanov (rem)
なんかRenat Mullakhanovさんという人が亡くなったらしいのでそれの追悼コンテストらしい
正直TopCoderとかCodeforcesとかはコンテストの時間が夜中過ぎて出れないので、
夕方からやってるUVaのコンテストに最近出てます。
1時間遅れぐらいで参加して5問といて25位でした。
解いた問題はH,A,J,E,C(解いた順)
Untyped Lambda Calculas
またまたHaskellで実装してみました。
変数名の衝突を避けるためにde Bruijn indiciesという方法を使ってます。
だいたい内側のラムダ抽象の引数から順に0,1,2...と番号をふる感じの方法です。
詳しいことは本で確認してもらえれば・・・。
{- Untyped Lambda Calculus -} data Term = LVar Int | LAbs Term | LApp Term Term deriving (Eq) newtype Context = Context [String] type Binding = String showTerm (LVar x) = show x showTerm (LAbs t) = "(lambda. " ++ (showTerm t) ++ ")" showTerm (LApp t1 t2) = "(" ++ (showTerm t1) ++ " " ++ (showTerm t2) ++ ")" instance Show Term where show t = showTerm t termShift :: Int -> Term -> Term termShift d t = walk 0 t where walk c td = case td of LVar x | x >= c -> LVar (x+d) | otherwise -> LVar x LAbs t1 -> LAbs (walk (c+1) t1) LApp t1 t2 -> LApp (walk c t1) (walk c t2) termSubst :: Int -> Term -> Term -> Term termSubst j s t = case t of LVar k | k == j -> s | otherwise -> LVar k LAbs t1 -> LAbs (termSubst (j+1) (termShift 1 s) t1) LApp t1 t2 -> LApp (termSubst j s t1) (termSubst j s t2) termSubstTop :: Term -> Term -> Term termSubstTop s t = termShift (-1) (termSubst 0 (termShift 1 s) t) isval :: Context -> Term -> Bool isval ctx t = case t of LAbs _ -> True _ -> False type ErrorMessage = String eval1 :: Context -> Term -> Either ErrorMessage Term eval1 ctx t = case t of LApp (LAbs t12) v2 | isval ctx v2 -> Right (termSubstTop v2 t12) LApp v1 t2 | (isval ctx v1) -> Right (LApp v1 t22) where Right t22 = eval1 ctx t2 LApp t1 t2 -> Right (LApp t11 t2) where Right t11 = eval1 ctx t1 _ -> Left "No Rule Applies" eval :: Context -> Term -> Term eval ctx t = case res of Left err -> t Right u -> eval ctx u where res = eval1 ctx t
使い方は
> let true = (LAbs (LAbs (LVar 1))) > let false = (LAbs (LAbs (LVar 0))) > let ifl = (LAbs (LAbs (LAbs (LApp (LApp (LVar 2) (LVar 1)) (LVar 0))))) > true (lambda. (lambda. 1)) > false (lambda. (lambda. 0)) > ifl (lambda. (lambda. (lambda. ((2 1) 0)))) > eval (Context []) (LApp (LApp (LApp ifl true) true) false) (lambda. (lambda. 1))
って感じです。
関数適用が左結合なのを実装に組み込めてないので、一つ一つ自分で書かないといけないのがちょっとうざいですね。
いよいよ次の章から型が登場するらしいです。わくわく
以下、本に乗ってた関数たち
-- Bools tru = (LAbs (LAbs (LVar 1))) fls = (LAbs (LAbs (LVar 0))) test = (LAbs (LAbs (LAbs (LApp (LApp (LVar 2) (LVar 1)) (LVar 0))))) andl = (LAbs (LAbs (LApp (LApp (LVar 1) (LVar 0)) fls))) orl = (LAbs (LAbs (LApp (LApp (LVar 1) tru) (LVar 0)))) notl = (LAbs (LApp (LApp (LVar 0) fls) tru)) -- Pair pairl = (LAbs (LAbs (LAbs (LApp (LApp (LVar 0) (LVar 2)) (LVar 1))))) fstl = (LAbs (LApp (LVar 0) tru)) sndl = (LAbs (LApp (LVar 0) fls)) -- Church Numerals c0 = (LAbs (LAbs (LVar 0))) scc = (LAbs (LAbs (LAbs (LApp (LVar 1) (LApp (LApp (LVar 2) (LVar 1)) (LVar 0)))))) plus = (LAbs (LAbs (LAbs (LAbs (LApp (LApp (LVar 3) (LVar 1)) (LApp (LApp (LVar 2) (LVar 1)) (LVar 0))))))) times = (LAbs (LAbs (LAbs (LApp (LApp (LVar 1) (LApp plus (LVar 0))) c0)))) iszro = (LAbs (LApp (LApp (LVar 0) (LAbs fls)) tru))
chapter3
春休みに入って時間に余裕ができたので図書館で
Types and Programming Languages (The MIT Press)
- 作者: Benjamin C. Pierce
- 出版社/メーカー: The MIT Press
- 発売日: 2002/01/04
- メディア: ハードカバー
- 購入: 5人 クリック: 86回
- この商品を含むブログ (53件) を見る
第3章まで読み終わったので、第3章の言語を実装してみた。
この言語は、if構文,bool値,自然数,succ,pred,iszeroのみを持つ。
なんか、パターンマッチングできる言語のほうが実装しやすいよーと書いていたのでhaskellで。
{- Simple Arith Expressions (Untyped) -} data Term = MTrue | MFalse | MIf Term Term Term | MZero | MSucc Term | MPred Term | MIszero Term deriving (Show,Eq) isnumerical :: Term -> Bool isnumerical MZero = True isnumerical (MSucc x) = isnumerical x isnumerical _ = False isval :: Term -> Bool isval MTrue = True isval MFalse = True isval x = isnumerical x eval1 :: Term -> Term eval1 (MIf MTrue x y) = x eval1 (MIf MFalse x y) = y eval1 (MIf t1 t2 t3) = MIf x t2 t3 where x = eval1 t1 eval1 (MSucc t) = MSucc x where x = eval1 t eval1 (MPred MZero) = MZero eval1 (MPred (MSucc t)) = if isnumerical t then t else error "badnat" eval1 (MPred t) = MPred x where x = eval1 t eval1 (MIszero MZero) = MTrue eval1 (MIszero (MSucc t)) = if isnumerical t then MFalse else error "badnat" eval1 (MIszero t) = MIszero x where x = eval1 t eval1 _ = error "No Rule can apply" eval :: Term -> Term eval t = if isval t then t else eval $ eval1 t
> eval (MIf (MIszero (MPred (MSucc MZero))) MTrue MFalse) > MTrue
みたいな感じでとりあえずうごく。
eval1にvalueを与えたときにvalueを返すようにして、evalをfixで書くとかもできそうな感じがする。