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年04月17日(日) 終わっても楽にならない

変わる日常 変わる日常を含むブックマーク 変わる日常のブックマークコメント

いやはや、上海でも反日デモですか。

一週間ずれてて良かった。人民広場とか観てきましたよ…。


帰ってきて色々いつの間にか進んでいた。

  • 5回生になった。新しい学生証をもらった。でも、写真は18歳のときのままだった。若い…。
  • そこのM1に多分私と同じ年に入学した人がいた。ぐほ。
  • 必修の授業の一回目が終わってた。なので、事情(ICPC)を説明したところ、なんと、2000文字以上の活動の概要を要求された。これってレポートのほうが楽なんじゃ…。
  • レポートがつらい。私の弱点は出席&レポートだ。出席→できない。レポート→めんどくさい。一回生の時レポートを無視しまくっていたらさくっと留年してしまいましたよ。なので書かないわけにはいかないんだけどなぁ…はぁ。

今年は院試卒業研究ICFP、ICPCと色々やることが。

未踏とかに応募している余裕はなさそうだなあ。働く余裕もなさそう。

趣味プログラミングに割く時間だけは確保したいところであるけど、

どうなんだろうなぁ…最近やるきも起きないし。うーむ。

ネタはぼんやりとあるんだけどね。

Cマガ電脳クラブ Cマガ電脳クラブを含むブックマーク Cマガ電脳クラブのブックマークコメント

応募しようかと思って問題見てみたんだけど、

今月の問題微妙に難しくは無いですかね?

なんだか異常に探索空間が広いような。

コードはまだ書いていないけど、ナイーブに書いたら終わらないような。

普通に考えると全探索するしかないので、

あとはどれぐらい枝刈りが出来るか、だろうけど、

書きながらこつこつと高速化していくしかないのかな。

h_sakuraih_sakurai 2005/04/25 22:48 新年度ってことで、いろいろたいへんでしょうけど、がんばってくだちい

tanakhtanakh 2005/05/01 23:54 いやはや、お心遣いありがとうございます。

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

2005年04月12日(火) World Finals 参加記

と…いうか、旅行記録みたいになってしまったけど。

本体サイトに追加。

まぁ、参加したつもりになって読んでくださいな。

[]World Finals 問題解説 World Finals 問題解説を含むブックマーク World Finals 問題解説のブックマークコメント

上の文章が良く分からん感じになってしまったので、

問題についての説明だけこっちにも書いておきます。

http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf

問題はここから参照できます。


  • 問題A

一方の図が他方の図の一部になっているかを判定する問題。

難問。はっきりと捨て問題でしょう。

  • 問題B

いくつか無線アクセスポイントがあって、

その最も近いところと通信を行いながら町を移動する。

ある町からある町へ移動するときに、最も少ない切り替え回数を求めよ、という問題。

グラフを作ってダイクストラ。

グラフを作るのは…がんばれ。

  • 問題C

無限に相乗りできるタクシーを使って複数の人が一箇所に集結したいとき、

最もコストを小さくせよ、という問題。

最小全域木の部分木を求める。

  • 問題D

ある人がカードを何回か(10回以下)シャッフル(パーフェクトシャッフル)する。

シャッフルが成功すると前半と後半が完全に一枚ずつ交互に並ぶ。

シャッフルは失敗するかもしれない。失敗すると本来あるべき位置が

どこか一箇所入れ替わってしまう。

シャッフル済みカードの列が与えられたとき、何回シャッフルしたか、

何回目にどこを失敗したか、を求める問題。

深さ優先探索+枝刈りで解けてしまいます。

  • 問題E

いくつかアパートが与えられ、指定された部屋に対して

日光が当たる時間を求めよ。という問題。

簡単な問題。特に書くことはなし。

  • 問題F

家から大学までなるべく道を横切らずに行きたい。

最低何回横切らなければならないか?

解き方は…まだ考えていない。

これもグラフ生成+ダイクストラかな?

  • 問題G

与えられた図形が無限に敷き詰め可能な図形か判定せよ。

本文中にヒントがあるらしいが、それでも難問。

これも捨て確定。

  • 問題H

万里の長城ゲームという、n*nの盤面に適当にn個の石が配置された状態から

石を動かして一直線に並べるというゲームを考える。

石を一ます動かすのを一手とするとき、最短手数を求めよ、という問題。

手数は各石の出発地点から到達地点へのマンハッタン距離の合計に等しくなる(多分)

ので、各石がどこに行くのかを求める二部グラフマッチング問題となる。

マッチング自体はハンガリー法というのを使えば解けるらしい。

(私は知らないけど…)

  • 問題I

いくつかのイベントが開かれ、いくつか部屋が用意される。

部屋には入れる人数と使える時間が決められていて、

イベントの参加人数と時間が部屋の条件に収まっていればその部屋が使える。

なるべく多くのイベントが部屋に入るように、

イベント数が同じなら参加人数が一番多くなるようにするにはどうすればいいのか。

…おそらくこれもマッチング。

  • 問題J

アンテナを立てる場所がいくつか(<20)あって、それぞれカバーできる人口がちがう。

複数のアンテナカバーされる領域もある。

アンテナを立てる本数が与えられるので、カバーできる人口を最も多くせよ。

20C10が非常に小さい数なので、全探索すれば終了。


…ちなみにうちのチームが本番で解いたのはBDEJ、です。

yaneuraoyaneurao 2005/04/12 23:57 レポート、お疲れさまです。

ぱっと見、問題Gが一番面白そうですナ。回転と鏡像を考慮しなくていいなら、与えられたblockより少し大きな横幅と縦幅を持つ四角形(上下,左右が空間的につながっていると仮定する)を考えて、そこに敷き詰められるかを判定する問題に帰結するんですカナ?4角形だけでなく、ハニカム構造もあるナ..こりゃ難問だ。

tanakhtanakh 2005/04/13 03:21 問題Gはですね、本文中にヒントが書いてあります。
1.ポリゴン境界上に点ABCDを順に取った時、
AからBまでの輪郭とDからCまでの輪郭が相似、かつ
BからCまでの輪郭とAからDまでの輪郭が相似
であるようなとき、スクエアタイリングが可能。
2.ポリゴン境界上に点ABCDEFを順に取った時、
…(略)…
なとき、ヘキサゴンタイリングが可能。
で、タイリングは四角か六角のどちらかしかないようなので、
これを調べればよいらしいのですが。

…どうやればいいんでしょうね?

yaneuraoyaneurao 2005/04/13 08:07 ああ、なるほろ。輪郭が相似ってのを効率よく判定するというのは面白い問題ですネ。力技なら出来なくもないですけど..。

tanakhtanakh 2005/04/13 13:17 相似かどうかは線分を切り出して、回転している量が決まっているので、回転させて長さをあわせて一致するかどうかを調べれば良くないですかね?むしろ問題となるのは、境界上のどこに点を取れば相似になるような輪郭が切り出せるのか、でしょう。まさか微小距離ずつ動かして全部調べるわけにもいかないだろうし…

tanakhtanakh 2005/04/13 14:21 相似じゃなくて、合同だ…勘違いしていました

2005年04月09日(土) 帰国

む〜ん… む〜ん…を含むブックマーク む〜ん…のブックマークコメント

むむむむむ…

大して力も無いのに調子に乗るなという話ですな…

情けない。

結果はあんまりよくなかったけど、

そのうち反省文(?)とか書きますわ…

救いがあるとすればパラレルチャレンジかな…ああ。

yaneuraoyaneurao 2005/04/10 00:13 ど、、どうなったのカナ??(´ω`) > 結果

結果はともかく土産話などお待ちしてますm(_ _)m

tanakhtanakh 2005/04/10 00:28 http://icpc.baylor.edu/icpc/Finals/Standings.html
結果はここにあります。
完全な勉強不足です。
解くためにやらなければならないことは分かったのに、
そのアルゴリズムを勉強していかなかったなんて…。
あと2問は解かなきゃならなかったですなぁ…ああ。

yaneuraoyaneurao 2005/04/10 02:24 ほほー(゜Д゜) 良かったら、問題の解説とかプリーズ(´ω`)人

h_sakuraih_sakurai 2005/04/11 22:16 おつかれさんでつ

tanakhtanakh 2005/04/12 21:11 どうも。折角なんでいろいろ文章書きました。近々公開しますので、よろしければ読んでくださいな。

yaneuraoyaneurao 2005/04/12 21:14 楽しみにしてますー!(´ー`)

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

2005年04月01日(金) 光陰矢のごとし このエントリーを含むブックマーク このエントリーのブックマークコメント

もう明後日出発なんですね…。

時の過ぎるのは本当に速い。

愛媛のときから四ヶ月以上経っているのだが、

正直なところ充分な準備が出来ているとは思えない。

大会に持ち込むためのリファレンスを作るのが大変だった。

結局丸一週間ぐらいかかってしまった。

というのも、プログラムを書いてもそれが本当に正しいのか

字面だけからは判断できないし、結局ちゃんとチェックする必要があったりして

えらいこと時間がかかる。

ここで極めて幸いなことにacm.uva.esという

強力なプログラム検証機構を用いることができるので、

自分でチェックするよりは断然お手軽にある一定の信頼性を手に入れることが出来る。

とはいえ使える問題を探すのが大変だし、見つけたとしても

ちゃんと通さないといけないのでやっぱり大変なのだ。


…というわけで、いろいろコードを書いたのだが、

今回全体的に短いコードが書けた。

凸包のプログラムなんてびっくりするほど短くなった。

このように同じプログラムを書いてみてもそれが

毎回変化していっているということはやはり私も

まだまだ進歩の過程にいるということが判って若干の安心を覚える。

が、ここ一年で私を変えたものは間違いなくHaskellなので、

来年以降も変化し続けることが出来るのかどうかはわからない。

とはいえ高校生ぐらいの時だって、もうこれ以降何をやることがあるのか、

とか思っていたので、私もまだまだやり残していることがあるんだろうとは思う。


あと…四月一日号の京都大学新聞に私どもの記事が載るようです。

私も文章をちょっと書きましたので機会があればご覧ください。

yaneuraoyaneurao 2005/04/02 13:12 ご健闘をお祈りしてます!(`ω´)

tanakhtanakh 2005/04/03 01:59 ありがとうございます。行ってまいります。

h_sakuraih_sakurai 2005/04/03 03:09 『ご健闘をお祈りしてます!(`ω´)』
(ただのまね)

h_sakuraih_sakurai 2005/04/03 03:28 いってらっしゃいませ。m(_ _)m

tanakhtanakh 2005/04/03 08:05 どうもありがとうございます。(まだ行ってなかった)
行ってきます!