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)

Types and Programming Languages (The MIT Press)

を借りてきて読んでます。


第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で書くとかもできそうな感じがする。