Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2005年06月27日(月) ICFP

[][]今年のICFP 今年のICFPを含むブックマーク 今年のICFPのブックマークコメント

今年も(今年は前半が?)終わりました。

私も去年と同じくM氏と参戦しておりました。

(もちろんHaskellで)

今回は、銀行からお金を盗む泥棒とそれを捕まえる警察チームのAI

考えるという課題でありましたが…

はっきり言って方針が立てにくかったです。

私はRobberを作ってたんですがもう全然ですな。

M氏のCopに捕まりまくり。

とりあえず、逃げと盗みを両立させるのは非常に難しい。

盗んだら居所がばれるし、盗まなきゃ点が入らないし、

盗んだら警察が追ってくるのでたいていその後は逃走になるわけですが、

逃走であっさりと逃げるべき道を間違えてくれるし、

ちっとも思ったとおりにならない。

今回の課題の変更に強いコーディングなども知ったことではない。

今年はあんまりかな…


そういうわけで、私には猛省を促す。

もうちょっと頑張ること。

トラックバック - http://d.hatena.ne.jp/tanakh/20050627

2005年06月21日(火) Haskellで書いてみた

家のトイレがいつの間にか新しくなっていた。

扉を開けるといきなり便座が勝手に開いてたいそうびっくりした。

座っているかの検地も前は便座にスイッチがついていたが

今回は光センサーのようだ。

トイレも進化しているんだなぁ、と思った。

[]この前の練習会 この前の練習会を含むブックマーク この前の練習会のブックマークコメント

入出力データが公開されたので、

早速E問題の出力をチェックしてみた。正解だった。

vector<map<string,pair<int,int> > > などの乱舞するプログラム

一発で通せて、なんとなく嬉しい。

Bの誤審がなければぎりぎり間に合ったんではないかとも思うが、

M氏は10分ぐらいどこからでも捻り出せなければだめだというようなことを言った。

確かに全問を2分づつ速く解けばそれで10分が捻出できるし、

問題E解くのに60分強かかったが、これももっとうまいこと解けば

50分ぐらいで出来ないこともなかっただろう。

大体、本番でも何が起こるかわからないので、

全問が解きたかったら、二時間半ぐらいで全問解ける

ぐらいの勢いで望むべきかもしれない。

というか、今年で最後なので是非に全問正解というのをやらかしてみたいのだ。

残った時間、いったいどういう気分になるんだろうか?


そういうわけで、今週末はICFPがあるので、Haskellの練習がてら

Haskellで解いてみた。問題Eはあまりにも面倒なので解いてないけど…

http://fxp.infoseek.ne.jp/icpc2005/practice/icpc-mock-src.zip

しかし、思ったほど短くならなかった。特に問題F。

あと、型推論があっても Map Int (Map Int (Set Int)) とかが出てくると

頭の中がよく分からなくなってくるので、結局型を書いたほうがいいかも知れんなぁ…

というか、typeしろという話なのか。


http://mayah.jp/personal/scratch/archives/2005/06/21/index.html

練習の問題Mの答えですか。うーん。

前の問題とは考えが至らなかった。というか入力とか見ないし…。

しかし、見たとしても分からんかっただろうなあ。

メールエンコード方法がBASE64とか知らないし、

BASE64てなんだったかいな、と検索したりしている私は

きっとコンピュータに明るい人ではないんだろうなぁ…。

[]F# F#を含むブックマーク F#のブックマークコメント

ふとF#とかいう言語があったなぁ、と思い出して、

どの程度実用になるんだろうかと試してみた。

.NETクラスとのやり取りをどうするかが問題になると思われるが、

なんか普通に使えてますね。ウインドウ出したりも出来るし。

何よりVisual Studioで使える。コード補完やデバッガが使えるのが大きい。


とりあえず何か作ってみようと思ったので、

なぜか、モナディックIOを実装してみた。全然F#である意味がないけど。

随分前にMLでもモナドでIOを扱うことは出来るが、意味がないのでやらない

とかいう記述をどこかで見たのだが、そのときは具体的にどうなるかが

分からなかったので、どうなるのかな、とやってみた。

(* IOモナドの定義 *)
type World = World of int
type 'a IO = IO of (World -> (World * 'a))

(* 演算子の定義 *)
let (>>=) (IO m1) f =
  let h w =
    let (w2,r) = m1 w in
    let (IO m2) = f r in
    m2 w2 in
  IO h

let (>>) (IO m1) (IO m2) =
  let h w =
    let (w2,_) = m1 w in
    m2 w2 in
  IO h

let Return a = IO (fun w -> (w,a))

(* IOモナドを実際に実行 *)
let run_io (IO f) = let _ = f (World 0) in ()

(* プリミティブな関数 *)
let put_str_ln (s:string) =
  let psl w = System.Console.WriteLine s ; (w,()) in
  IO psl

let get_line =
  let gl w =
    let s = System.Console.ReadLine () in
    (w,s) in
  IO gl

(* 使用例 *)
let hoge =
  get_line >>= fun s ->
  put_str_ln ("*** " ^ s ^ " ***")

(* IOモナドとの対比 *)
let hage () =
  let s = System.Console.ReadLine () in
  System.Console.WriteLine ("*** " ^ s ^ " ***")

let main = run_io hoge ; hage ()

Cleanに影響されてWorldを作ってみたが、要らなかったかもしれない。

使用例のほうは意外と自然かもしれない。

ただ、評価が遅延されないので、大きなプログラムを作ると

ものすごくでかいIOのデータが生成されるような気がする。

しかし、ひさしぶりにOcamlというかF#を触ったが、

見た目はHaskellとそれほど変わらないのに、

正格評価なので感覚がなんだかおかしくなった。

関数変数が違うものだったり。

Haskellに慣れすぎているのかもしれない。

2005年06月19日(日) 練習会

[]ICPC練習会 ICPC練習会を含むブックマーク ICPC練習会のブックマークコメント

模擬練習会があった。

今日も二人だったけど、今日はちゃんと集まってやった。

キーボード英語キーボードでやった。


結果は、とりあえず一位だったが、どうにもすっきりしない。

というか、こんなんじゃ駄目だ・・・。

最後のほう、完全にぐだぐだだったし。


まず、練習フェーズ。

いつもどおりさくっとトップを確保。

で、最後の解けない問題をがんばる。

きっと何か元ネタがあるんだろうなぁ、と思いつつ、

結局解けなかった。まぁ、これは当たり前というか。


それから本番。

開始と同時にA問題を解きにかかる。

とりあえずA問題に対して言うことはない…。

10分ほどで完成。普通にアクセプト。


次、B問題。

問題のサイズが小さいから全探索してしまいました。

で、終了ー、と思いきや……

なんと、Wrong Answerをくらう。このとき開始28分ほど。

なんでかなあ〜〜と思いつつ、微修正して再送するも駄目。

で、10分ほど経過。今日はもう駄目かなぁ…と思いながら

メールボックスを見てみると、

「問題Bの審判側のテストデータに誤りが発見され、現在修正されました。」

とかいうメールが来ていた。

おいおいおいおいおいおい。なんじゃそりゃ?

とりあえず再送、アクセプト。

こんな問題に30分も食ってしまった。


自明な問題は終わっちゃったらしい。

どれにしようかと思っていると、M氏がFの回答を思いついたようだ。

問題Fはn人の人がn分割された地図を持っていて、

都合のいい日に会いながら誰か一人のもとに全部地図を集めるのにかかる

最短の日数を求める問題。

これは各々がその時点で持てる可能性のある地図をマージしながら計算すると

簡単に答えが求まる。

要するに、地図コピー可能で、みんなにコピーを配ると考えると分かりやすい。

解き方が分かると実装は簡単である。

さくっと実装。さくっと送信。さくっとアクセプト。

とりあえず簡単なほう3問を一時間で処理できた。


次、どれをするか。

M氏はDは幾何だから手を付けにくいとかいっていたが、

どうもそんなことが無いような気がして、Dを解くことになった。

Dは正方形と直線がいくつかあって、

直線によって正方形がいくつに分割されるか、という問題。

三本以上の直線が同一点上で交わらないときの平面の分割は有名な問題だが、

それのちょっとした変形だ。

直線を加えたときに、領域の数は、

(正方形の上で交わる交点の数+1)づつ増加する。

幾何問題なのでM氏が書くということになった。

で、私は残りの問題を考えることに。


残りは問題Cと問題E。

問題Cは魔王の瘴気から逃げながら勇者がクリスタルを集めるというような問題。

(て、よく分かりませんな…)

問題Eはややこしい郵便配達の問題。

問題Cは解けるような気がしたんだけど、

色々考えているとやっぱりよく分からなくなってくる。

最も悩んだのは、クリスタルへ向かうときに直線じゃなくて、

瘴気を迂回するようなルートをとるべき場合があるかということ。

これが分からなくて、結局書けば通りそうな問題Eをよく読むことにした。


そうこうしている内に30分経過。問題Dが解ける。

で、あらかじめ考えておいた問題Eを解き始めることにした。

問題Eは、まず各郵便局から郵便局へ配達するときの

次の中継地点を求める必要がある。

最初読んだときはなんとなくダイクストラ?とか思っていたが、

ダイクストラでは駄目っぽい。

経路の逆から探索しないとだめだなぁ、どうするか。


と思っていると、横でCを考えていたM氏が

瘴気を迂回するルート存在し得ないことを証明した。

そうと分かれば問題Cにチェンジである。

直線の移動しかないとすると、問題のサイズも20までなので、

深さ優先探索すれば答えは求まりそうである。

どういう順番でクリスタルを回収していくかを探索するが、

枝刈りをしないと20までといえど無理っぽかったので、

探索の全時点において、残りのクリスタルに到達不可能なものが出たら

探索を打ち切る、というようなものを入れた。

で、実行。なんかおかしいぐらい早く実行が終わった。

それから回答送信。Wrong Answerを食らう。

なんでかなぁ…と思ってソースを見ていると

探索のところでクリスタルの回収したフラグの扱いがおかしくなっていた。

これだから副作用は嫌いなんだ。

とりあえず修正。実行。今度は3秒ぐらい実行に時間がかかった。

再送。アクセプト。この時点で残り1時間弱。


さて、最後の問題である。

問題読めば読むほどややこしい問題だということがわかってきて、

正直残り一時間弱ではどうなんだろうなぁ。

とおもいつつ、とりあえず書かなきゃ駄目だろということで。

方針は、中継地点テーブル作成=>シミュレーション、だ。

中継地点のテーブルは逆ダイクストラとでも言うべき方法で華麗に作成。

…と行きたい所だったが、もうめちゃくちゃ時間がかかった。

最近こういうコードを全然書いていなかったので時間のかかることかかること。

結局20分ぐらいかかって完成。

サンプルと照合、合ってそう。

残り30分強。正直無理だろうなぁ、と思いつつ。

シミュレーションはイベントドリブンな感じでごりごり書いていく。

で、書いていくはいいんだが…。

規則がめちゃくちゃ複雑なのである。

同じ時刻に来た荷物はあて先の番号が若いものから、とか、

郵便配達の人は同じところに持っていく荷物が複数合ったらまとめて持っていくとか、

出力は到着時刻順、時刻が同じならアルファベット順、とか。


混乱しながら、コードも二転三転しながらコーディング。

で、結局書いている途中に時間が来てしまった。

しかし、ここまで書いてというのも悔しいし、

もしかしたら事故の補正でちょっとぐらい遅れたやつでもアクセプトしてくれるかも、

という淡い希望を抱きつつ作成継続。

結局12分オーバーで完成。

とりあえずサブミットしたが、コンテストは終わりました、という返事であった…。


そういうわけで、なんとも煮え切らない結果であった。

4問ぐらい時からトップかな?と意識していたのだが、

_oopチームがぴったり付けてきてたのは不気味だった。

時間差で勝てるかな、とは思ってはいたが、なんともかんとも。

あと、補正が3000秒ぐらいということであるが、

二回不正解(2400秒)+(実際にアクセプトされた時間-最初に正解を送った時間)なんだろうけど、

実際のところ、10分ぐらい足止めされたわけで、それ以降に正解した問題全問から

(実際にアクセプトされた時間-最初に正解を送った時間)を引いた上で、

試合時間をその分延長してもらうぐらいしてもらわないと割が合わないと思った。


というわけで、なんだか長くなったが、

こういう機会を与えてもらったことはありがたいと思います。

良い練習になったので、本番でもいい成績が取れるといいなぁ。


・おまけ

スコア

なんとなく、採取してみたので。

2005年06月12日(日) コンテストの季節

いろいろ考えていたら、

あっという間に時間が過ぎてしまった…

[]Googleからの招待状 Googleからの招待状を含むブックマーク Googleからの招待状のブックマークコメント

ICPC世界大会の成績を称えて?カリフォルニアGoogle本社に招待された。

…が時期が悪すぎるので、行けないかも…

チームのほかの人たちは皆行くみたいなんで、悔しすぎます。

[]登録した。 登録した。を含むブックマーク 登録した。のブックマークコメント

締め切りがもうすぐそこですね。

うちのチームも登録を済ませました。

なーんか、今年、京大からまだ2チームなんですけど…

いったいどうなってるのかね…?


それはともかく、全然練習してませんよ。

春から一問も解いてなかった。

とりあえず、いくつか解いて感覚を戻しておかねば。

[]練習会 練習会を含むブックマーク 練習会のブックマークコメント

6月19日に練習会があるらしい…がK氏が参加できない模様…

ショックである。

国内予選など私一人で楽々だとかまだ思っているのだろうか。

今年は海外派遣を真剣に狙わないといかんのですよ。

去年の強かった人たちが結構出場資格がなくなっていっているので、

ここで手を抜くわけにはいきませんよ。

[]練習会2 練習会2を含むブックマーク 練習会2のブックマークコメント

GNCの人が企画しておられる練習会が今日あった。

ちょっと前にお誘いをもらったので参加することになった。

これもK氏は出なかったけど…

…ちょっとは三人での練習をさせてくれ。


で、参加したわけであるが、会場は東京だったので、

いつもどおりリモートだ。

二人だったからメッセンジャーリモートアシスタンスで頑張った。

例によって例のごとく訳はM氏に全部やってもらったのだが、

リモートだといちいち質問するのに文字を打たないといかんのがつらいね。

次はどこかに集まってやりたい。


結果のほうはとりあえずトップだった。

ラスト一時間で三問通した。

問題は一問一問解いていったので、これは結構大変なことだ。

最後の問題なんか、残り18分で手を付け始めて

残り3分ごろでノートのバッテリが切れそうになったり

うがーーー、と思っているうちに通った。

残り一分未満で通したのは去年の愛媛を思い出す。

三時間で6問一人で書いて正解したのなんて初めてだったので

びっくりするほど疲れた。

あと今回、制限時間1秒とか、全体的に時間が厳しかった。

2問でTLEを食らった。国内予選本番だと制限時間がないから、

この辺はもっと楽だろう。

あと、本番は日本語があるし、まず間違いなくA問題が超楽勝問題なので、

スタートでぐだぐだにはなりにくいだろうとは思う。

[]ICFPもそろそろ ICFPもそろそろを含むブックマーク ICFPもそろそろのブックマークコメント

ICFPのほうも再来週ぐらいだ。

去年出たので、今年も出ようかと思っているが、

今年はちょっと趣向が違うようだ。

なんか、プログラムの実行環境が指定されているので、

プログラムの提出になるんだろうか。

それと終わったあと二週間後に仕様変更があって、

それからもう一回何かするようだ。

どういう課題がくるのか全くわからない…。

とりあえずHaskellも感覚を戻しておかないといかんなぁ。

トラックバック - http://d.hatena.ne.jp/tanakh/20050612