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 |
本体サイト

2006年03月25日(土) ぶらり京都二人旅

[]京都日帰り旅行(2) 京都日帰り旅行(2)を含むブックマーク 京都日帰り旅行(2)のブックマークコメント

長くなりそうなので、

ご覧になりたい方は下をクリックて下さい。

続きを読む

2006年03月24日(金) 卒業、そして

[]卒業式 卒業式を含むブックマーク 卒業式のブックマークコメント

ついにこの日が来た。

"自由な学風"の意味を曲解したあまりにも自由すぎる

学園生活を送ってきた私も今日で晴れて大卒である。

毎日どうやって生きていこうか途方に暮れていた高校時代から

考えるとこれでも信じられないぐらい立派になったものだ。

笑って話せる日がくるさ、とはよく言ったもので、

まさに今となってはこれまでのことは、

辛かった高校時代のことでさえ微笑ましく思える。

正直言って、大学の5年間で知識や技量はそんなに向上していない。

学部の授業なんてはなから受けるつもりが無くて、

その通りに一切授業に出なかったら、

レポート単位が出る科目を全て落として、

いきなり一年目で留年が確定してしまった。

おそらくこのとき初めて私は世間の厳しさというものを知って、

やらなければどうにもならないものも有るのだということを知った。

しかし、それもまた今となっては良い(苦い?)思い出だ。

そういうわけで、数えるほどしか授業に出ていないので、

大学勉強をしたという感じは全く無いのだが、

それでも一つ大きく変わったと思うことがあって、

それはLispをはじめとする関数型言語との出会いだ。

私はプログラミングというものに対しての考えを大きく変えられ、

その異質なる概念は現状の閉塞したプログラミング環境を変革する

可能性を秘めているものと悟り

最終的に私の興味対象自体も徐々にそのような

プログラミング言語理論へと傾いていった。

このように、考えが全く転換されたということで、

この五年は意味があったということができそうだ。


他に特筆すべきはICPCだろうか。

回生の時から参加しているので、もうずいぶん長くになる。

しかしこれももうほんの数週間後には終わりを迎える。

本当にもう終わってしまうのかと思うと寂しくもあり名残惜しくもあり、

それでも最後まで頑張らねばなと思う。

今こう振り返ってみて改めて思うのは、ICPCに出場して本当に良かったということだ。

世界レベルで自分のプログラミング能力を試すことの出来る機会というのは

それだけで貴重なもので、出るというだけで得られるものは大きいのだが、

それに加えて、合宿や練習会を通じて他の大学のいろいろなすごい人と

知り合いになって、交流が持てたことや、

世界大会に出場して世界中のトッププログラマの集まる、

その独特の雰囲気を体験できたことや、

さらにはそれを受けて総長に挨拶に行ったり

あろうことか賞までもらえることになったりと、

本当に色々と貴重な経験ができた。

ICPCに出場していなかったらこれら全てが無かったのだと思うと、

この大会とチームメンバーの二人には感謝してもしきれない。


なにはともあれ、今日で私は卒業する。

これは一つの区切りの終わりであり、また始まりでもある。

重要なのはこれから自分が何を為すことができるのか。

まだまだ先の見えない日々は続くが、

出来ることをとにかくやっていこうと思う。


そして、最後に自分へ。おめでとう。

Chun@GNCChun@GNC 2006/03/26 02:28 おめでとうございます。東京でチーム一同お待ちしております!

tanakhtanakh 2006/03/29 06:16 どうもありがとうございます。どうぞ、お手柔らかに(?)

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

2006年03月21日(火) Last Digits

[]Last Digits Last Digitsを含むブックマーク Last Digitsのブックマークコメント

別のネタを先に書こうと思っていたのだが、

リクエストがあったので、こっちを先に書くことにします。

問題はこちら


http://acm.pku.cn/JudgeOnline/showproblem?problem_id=2720


問題の要求はシンプルで、

整数入力 b i n (1<=b,i<=100, 1<=n<=7) が与えられたとき、

b^b^b^ ... ^b (つまりbのi回乗) の下n桁を求めよというもの。

Haskell的に書くと

f b 0 = 1
f b i = b ^ f b (i-1)

g b i n = f b i `mod` 10^n

なるgを求めよというものだ。

当然ながらこんなコードをそのまま書いていては

計算がいつまでたっても終わらない

…というかそもそも桁数が宇宙の粒子数をゆうに越えてしまうような気がする。

そこで、intに収まる範囲で下位桁だけ計算してやるということが必要になるが

これがなかなかの曲者である。


そこで、ここではとりあえずだまされたと思って

次のコードを見て頂きたい。

f _ 0 _ = 1
f b i mask = powi b (f b (i-1) mask) mask -- mask は 10^n

powi a b mask :: Int -> Int -> Int -> Int -- a^b `mod` mask を計算する

ご存知の通り累乗の計算というのはlognのオーダで計算できるので、

powiはbがどんな数であろうとほぼ一瞬で計算できる。

そのため、f b n mask も短時間で計算することが出来る。

このfは元のfを各計算ごとに下n桁の計算のみをするというものであり、

元と比べてもかなり単純な処理のままである。

これで答えが計算できれば素敵でしょう?


しかし、残念ながらというか当然ながらというか

この関数では正しい答えを計算できない。

というのもf b i mask の値をmaskで剰余をとってしまっているので、

要するに、a^b (mod n) と、a^(b+10^n) (mod 10^n)が等しいとは限らないので、

結果的に答えが合うとも限らないのである。

実際にf 10 3 1000 を計算してみると、

f 10 3 1000
= powi 10 (f 10 2 1000) 1000
= powi 10 (powi 10 (f 10 1 1000) 1000) 1000
= powi 10 (powi 10 (powi 10 (f 10 0 1000) 1000) 1000) 1000
= powi 10 (powi 10 (powi 10 1 1000) 1000) 1000
= powi 10 (powi 10 10 1000) 1000
= powi 10 0 1000 -- powi 10 10 1000 が 0 になる
= 1

これは0になるべきなのでおかしくなる。

しかし、ここであきらめてはいけない。

実は次に示すような性質がこの式にはあるのだ。

定理1:累乗の下位桁の周期に関する定理

∃a, ∀b>=a, ∀n>=2, ∀x, x^b ≡ x^(b+10^n) (mod 10^n)

定理2:累乗の下位桁の周期の下限に関する定理(1)

∀b, ∀n>=2, ∀x, x^(b+10^n) ≡ x^(b+2*10^n) (mod 10^n)

定理3:累乗の下位桁の周期の下限に関する定理(2)

∀b,x^(b-5)>=10^n, ∀n>=2, ∀x, x^b ≡ x^(b+10^n) (mod 10^n)

定理1は任意のxの累乗の下位桁nに対して、10^nの周期が存在するという

かなり大胆な定理…というか予想だ。

周期の最大値は明らかに10^nなので、

任意の周期はその約数になるということか。

n>=2となっているのは、n=1には簡単な反例があり、成り立たないからである。

定理2は定理1が正しいなら即座に導くことが出来る。

定理1におけるaは10^n以下として良いということがいえる。

定理3は定理2より強力な周期の下限の存在(というかこれも予想…)定理である。

"-5"というマジックナンバーがいかにも怪しいが、

正確な下限は良く分からないので、これで勘弁。

少なくともそんなに大きくは無いはずだということ。

定理1のaがかなり小さくても成り立つということがいえる。


証明であるが、ちょっと数学的には無理だった…ので

四色定理よろしく計算機にさせてみることにした。

といっても完全に証明するのは無理なので、

とりあえず今回必要な範囲に限って証明することにした。

x^b>=10^n,x^(b-1)<10^n なるx,b,nに対して

x^(b+5) `mod` 10^n = x^(b+5+10^n) `mod` 10^n であれば

定理1〜3はすべて証明されるので(これは…自明ですよね)

そのようなコードを作成すれば良い。

import Control.Monad

main = do
  res <- mapM proofProcess $ [(a,b) | a <- [2..100000], b <- [2..7]]
  let ok = and res
  putStrLn $ "the theorem is " ++ if ok then "TRUTH" else "FALSE"

proofProcess (x,n) = do
  let res = proof x n
  when (not res) $ putStrLn $ "x = " ++ show x ++ " , n = " ++ show n ++ " : NG"
  return res

proof x n = powi x b mask == powi x (b+mask) mask where
  mask = 10^n
  b = searchb 0
  searchb b | x^b >= mask = b+5
            | otherwise = searchb (b+1)

powi _ 0 _ = 1
powi a b mask =
  let t = powi a (b `div` 2) mask
      u = (t*t) `mod` mask
      v = if b `mod` 2 == 1 then (u*a) `mod` mask else u
  in v

とりあえずx<=100の範囲で証明が出来ればいいのだが、

せっかくなので100000まで証明してみた。

実際に実行して確かめていただきたい。

というわけで、上の定理はx<=100000,n<=7という条件を付けていただくと

正しいものだということができる。


さて、この定理を用いると、f b n mask の定義は

ごく一部のパラメータ以外に対してはほとんどうまく動くことが分かるだろう。

動かないものに対して補正をしてやるなりすれば正しいプログラムが出来る。

それを書くのは大した手間では無いと思うので、ここでは実装の詳細までは触れない。

-----

☆あらかじめお断り☆

私には整数論の素養などほとんど無いので、

上の定理は一般には全くのでたらめであるかもしれません。

もし数学的に証明できた/誤りが証明できた、あるいは

こういう定理はとっくの昔に発見されているなどありましたら

情報をお寄せいただければ幸いです。

OzyOzy 2006/03/23 10:19 質問でーす。
私は累乗計算に__int64を使ってAcceptされたのですが、C++だけです。G++とかGCC(unsigned long long)だと、ローカルでは通るのにWAです。tanakhさんはint型onlyで累乗計算出来てるのですか???

tanakhtanakh 2006/03/24 23:18 計算の途中にはlong longを使っています。10^7*10^7はintには収まらないので、intだけだと無理だと思います。しかし、普通にG++で送ってもAcceptしてますね…

nucnuc 2006/03/28 06:19 地下へのお土産ありがとうございました。

その定理はちょっとした反例があるようです。
たしかにそれを潰せば正しくなりますが、これは激しく十進法依存でまったく美しくない系になりました。
あと、出題者想定回答は違うと思うので、証明と一緒に Haskell で書いて、あとでトラックバック打っておきますね。

tanakhtanakh 2006/03/29 06:30 うーん、やっぱり反例がありますか。
あとでじっくり読ませてもらいます…。

2006年03月20日(月) 第1回京都大総長賞

[]総長賞 総長賞を含むブックマーク 総長賞のブックマークコメント

http://www.kyoto-u.ac.jp/uni_int/01_sou/060320.htm

http://www.kyoto-np.co.jp/article.php?mid=P2006032000089&genre=G1&area=K1D

というわけで総長賞をもらいました。

f:id:tanakh:20060321034059j:image:w320

17日から19日まで東京に行っていろいろ準備をしていたので

帰って寝て起きて行って、となかなかに大変なスケジューリングで、

しかし、第一回総長賞というたいへん珍しいものを頂いて良い記念になりました。

報道関係者としてKBS京都とかも来てましたが、

うちにはKBS京都は入らないので、残念ながら見られず。

(略) どうか、今後とも、ますます学習研究をすすめ、京都大学学生の一人として、皆さんがそれぞれに自分らしさを見せながら、やがて近い将来、世界で活躍する姿を見せてくださることを祈って、お祝いの言葉とさせていただきます。

もう京大出るけどね…

[]生活準備 生活準備を含むブックマーク 生活準備のブックマークコメント

東京に行って借りた家に家具を買ったり、

入学手続きをしてきたり、色々と準備をしてきた。

こうなってくると東京に移住するということが

にわかに現実味を帯びてきて、

生まれてから一度も京都以外に住んだことも、

そもそも引っ越したことも無いのに、

こういう状況を思いのほか自然に受け入れることができているような、

あまりにも落ち着いた感覚だ。

ここ最近頻繁に東京との間を往復していたせいだろうか。

とはいえ引越しというものをしたことが無いのは間違いないので、

なかなかこういう勝手というものが良く分からない。

それに加えて、なんとも言いようの無い不安というものに

駆られたりもするが、その辺はもうなるようになれとか、

なんとかなるだろうとか、そう思うしか無い。


ところで私は根っからの優柔不断なので、

家電とか家具とかを選ぶのになかなか苦労した。

いや、選ぶだけなら苦労はしないかもしれないが、

家のお金で支払われるものなので、

あんまり高いものは言えないし、

かといって安いものはしょぼいし、でなかなか選び辛い。

そんなこんなでヨドバシAkibaにて選定をしていると、

突然"Nintendo DS Liteが緊急入荷"というアナウンスが流れて、

行ってみたらあんまりにもあっさりと買えてびっくりした。

近所の店ではもう発売からずっと店頭発売していた形跡すら

見かけたことが無かったので、

やはり日本最大級の店舗は違うのだなぁと思った。


東京に数日住んで思ったのは、

全体的にかなり騒がしいところだなというのと、

全体的にかなりごちゃごちゃしたところだなというもの。

京都は中心部に行っても結構おとなしいし、

街も東京ほどいろいろ詰めこめられていたり

区画が不規則だったりしないので、

住み慣れているからかもしれないが、

正直京都のほうが住みやすそうだという印象は拭えない。

ただ、不便はしなさそうなので、そこのところは問題なさそうだ。

いずれにせよ、あと数週間で完全に移り住まなければならないので、慣れていくしかない。

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

今週はこのような理由で東京に出払っていたので、

私は一人で東京から参加、あとの二人は京都から参加という

チーム内対決が実現した。

…負けました。

自力で英語を読むという時点で地獄が待っているのは目に見えていたのだが、

やっぱり地獄なのだった。


問題セットは http://acm.pku.cn/JudgeOnline/showcontest?contest_id=1173


軽く各問題について触れておく。

  • 2719 どう見ても簡単です。
  • 2713 どう見ても嫌がらせです。問題自体は超易。
  • 2718 全部調べて解いた。調べ方を工夫しないと間に合わなかった。あとでもっと速い方法があることが分かった。
  • 2717 どうみてもDP。問題の仕様をたくさん読み落として(というか、読まずに解いて)11回も間違った。ちゃんと読めば簡単。

他の問題は時間中に読めなかった…。

以下、本日のチームでの復習による成果。

  • 2714 ベクトルを順方向、逆方向に決定する方法は180度ごとにまとめても最適解をもらさないことが分かれば実装するだけだろうか。私はx,y軸方向のみに最適化してそのどちらかが最適解であると思ってそれで実装したら通らなかった。今日K氏に反例を指摘されたのでこれは誤りであることが分かった。
  • 2715 練習会でのGNCの人の言うところによるとイテレーションを忠実に計算するとdoubleの桁落ち誤差が蓄積して正しい結果が出ないということだったのだが、私にはどうにも計算式を見ても誤差が蓄積するようには見えなかったので、今日普通にイテレーションするプログラムを書いて送ったら普通に通った。うーむ…。ちなみに、漸化式を数式的に解くととても大変なようで。なぜか実行速度もあんまり変わらず。
  • 2721 英語が難しくて、何を計算したらいいのかがさっぱりわかっていなかったが、実際のところは簡単な問題のようで。特に言えることはなし。
  • 2720 この問題も時間内には読んでいない問題で…。問題を聞くと、どこからどう聞いても難しい問題には聞こえない。M氏のコメントには"最難問か"とか書いてあって困惑。問題は"a^(a^(a^(...))" mod (10^n) をというシンプルなもの。とりあえず自分のカンを信じて実装してみるとサンプルが大体あってて、微妙に間違ってるような感じ。なんで間違っているかを考えるにつれて私の最初のカンが大きな見落としを含んでいたことに気づいたが、それでも部分的に正解しているという事実から私はとんでもない(?)整数の法則を見出すことになって、結果的に最初に書いたソースを少し変更することによりアクセプトさせることに成功した。できたものは簡単なアルゴリズムで、速度的にも申し分ない。さらに、図らずしもCode Length最短をマークした。アルゴリズムの詳細については明日あたりに書くかもしれない。
  • 2716 一見易問。実は難しい?普通に書いたらTLE。効率の良い実装方法は分からない。通ってない。

というわけで、今回はなかなかに興味深い問題が多かったように思う。

あと、やはり一人では駄目だということを痛感。

目となり耳となり頭となる人が居てくれないと自分の力が全然出せない。

うちのチームは型にはまれば強いと思うので、

なるべくいい状態にもっていけるようにしたいところだ。

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

19日に世界大会の壮行会が行われた。

丁度そのときに東京に居るのに行かないのはもったいないような気がしたので、

参加させてもらった。どうもご馳走様でした。

しかし、こういうのを開くといって20人も集まるというのはなかなかすごいというか

私も人望があるというものだなぁ。ハハハハハ。

うそです。

とりあえず抱負はなんとしてでもメダルを持ち帰る。

もちろん金色のな!

そのためにも残された僅かな時間を必至に頑張るのです。

ちゅんちゅん 2006/03/21 20:07 イテレーションで誤差が蓄積するのではなくて、漸化式での計算の途中に出てくるある分数を使うとだめ、という物だった気がする。
イテレーションは最初から計算量が×だから、といってうちのチームでは考えもしなかった。
それにしても、時間に差が出ないっていったいどういう入力なんだろう???

tanakhtanakh 2006/03/22 03:01 うーん…分数がだめというのはちょっとどういうことなのか分からないです…
計算回数は誤差が指数的に小さくなるはずなので、そんなに多くならないという判断です。実際のところ、一番多くなるケースで5000弱ですし、平均的なデータが来れば一回あたり数百になってしまうのでは無いでしょうか?それに加えてデータが巨大だと入出力時間に計算時間が吸収されてしまうんですかね。

OzyOzy 2006/03/22 07:14 ↑インプットの数が100万以上あるので、アルゴリズム云々ではなく単なる演算回数の問題だと思います。色々コードをSubmitしてためしてみましたが、例えば無意味な割り算とか比較を一回ループの中に入れてみただけで数百msの差が出ます。

ちゅんちゅん 2006/03/22 19:09 100万 x 5000 = 50億でアウトなのかな、と思ってたわけですよ。
scanfのみならずprintfが指定されるというのは相当な出力サイズなわけで、全部5000回来たらアウトだろ、イテレーションで解いたらTLEだろ、数学的に求めるんが正しいはずだ! と信じていたわけです。まぁ実際に全部5000来たらアウトだと思います。
あと、分数がダメって言うのは漸化式を解くと出てくる
B(B+Wr)/(W+B+Wr) - B^2 / (B+W) の値が r << 1で桁落ちする(だからちゃんと分子分母計算しないと×)、と言う意味で、繰り返しによる解法とは全く関係ないです。
今思えば結果をmemoしてイテレーションならとても安全に事が済んだのかな。

tanakhtanakh 2006/03/22 23:12 50*50*50*16=200万ということでそのぐらいのテストケースが来ることは予想されますが、この問題の場合同じものがたくさん来るのはあんまり意味が無いので、そういうものは来ないと予想して、サンプルの数値からの予想で平均的なデータでは上限よりもかなり少ない、というあたりから考えてそのまま実装してみる価値は十分にあるでしょう。万一落ちたら最初に全部計算するコードを書いて送るまでで。全部計算するコードがローカルで遅ければその時は式を解くしかありませんけど。

2006年03月15日(水) いろいろ

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

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1886

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1887

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1888

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1889

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1890

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1891

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1892

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1893

の8問。12年も前のWorld Finalsの問題。

ムーアの法則によるとCPU性能が1/256のころの問題なので、

あまりCPUを食いそうな問題はない…のか?

入力がオフィシャルじゃないのか知れないけど、

とにかく通らない。こりゃ参った。


まず簡単そうな1988を渡されるので解く。

これは問題なくAccept

次に1887を渡される。これは最小"非増加"列を求める問題。

無論アルゴリズムなんて覚えていなかったが、

二乗のアルゴリズムはすぐに思いついて、

それから仕切りのみ考慮してSetを用いることにより

nlognのアルゴリズムを構築。そのままでは最小"減少"列が求まるので、

うまく弄って非増加列長が計算できるようにする。

これも書いたら通った。

次に1890がなんだかサイズが小さいということなので、

これを解くことに。

すぐに思いつくアルゴリズムの計算量は階乗オーダ。

これで入力はn=8まで。

今の時代だったら最低10は来そうな感じ。

これも普通に実装したら普通に通った。

次に、どうやら簡単そうな1893を書く。

書くの自体はすぐに終わったけど、

なんとこれが全然通らない。

誤差の処理とかかなりまともに実装しても通らない。

何度送っても通らないので、

他のチームがぼちぼち通り出した1886に切り替え。

問題のスペシフィケーションがかなりあいまいらしいのだが、

適当に解釈して実装。

かなり適当だったけど、書いたら通ってしまった。

さて、1893はやはり通らない。

1892は誰も通っていない問題なので、とりあえず回避しようという方向になる。

1891か1889のどちらかをやろうということになったのだが、

もし入力サイズが小さければ1889の方がさっくりと実装できそうだったので、

入力サイズがある程度を超えていないかどうか、assertをかけて調べる。

(なんか酷いやり方だけど…問題に載ってないんだもん)

結果想定内のサイズだったので、こちらに特攻することに。

(今気づいたんだけど、PKUって出力が遅延評価?されて、

間違い一個目でプログラムの実行がストップするから、

一個目の入力しかチェックできてなかったかも?)

プログラム自体はすぐできるものの、

なんとMLE。これはおかしい。(今思うと、ちゃんとチェックできてなかったからか)

メモリを削減して再投稿。今度はWA。

なんか良く分からないけど微妙希望が。

ごちゃごちゃ修正。

WAがTLEに変化。ショック。

それから後はごりごり線形の最適化を続ける。

TLEの連発。もうだめだ…終了。

1891に行っていたほうが良かったかも。

1891はとても難しそうには見えない。

しかし、Accept率が異様に低いのが気になる。

終了後どこかのだれかが練習用に作ったらしい入力を拾ってくる。

1983を通してみる。たくさん相違が。

いろいろ直してみるもどう考えてもおかしな入力が来る。

結局どう直しても通らず。この問題は怪しすぎる…。

良く分からず。コンパイラG++からC++に変えれば通るという話も有ったが、

少なくともうちのソースは通らなかった。

あと、1889はDPではなくて、枝刈探索でExpオーダのアルゴリズムだったみたいだ。

これが探索って…私の感覚もまだまだだな…。

ちなみに、DPによるプログラムは最終的にテスト入力を

ローカルで1.7秒で処理できるまでに高速化されたが、

PKUのタイムリミット一秒はさすがに厳しかったようで。

もう少し最適化すれば通らないことも無いような気がするんだけど…。


というわけで、今回は全体的にいまいち。

問題もいまいちな様な気が…

これが昔のWorld Finalsなのか。

[]ついでに ついでにを含むブックマーク ついでにのブックマークコメント

先日の Maximum Winter Contest 2006 のソース微妙インプルーブしてた。

http://www.aise.ics.saitama-u.ac.jp/~t_koh/PastProblems/Winter-Contest-2006/index.html

せっかくなので、晒してみる。


http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/a.cpp

最初からこれが書ければ30秒かからないのに

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/b.cpp

純粋関数的に

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/c.cpp

この問題はヒューリスティックが正解に違いない。

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/d.cpp

仕様さえ分かればさして難しくないはず…。

文章から仕様は理解しづらいと思う。

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/e.cpp

んまぁ、これも普通。

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/f.cpp

これも普通か。連結かどうかのチェックを忘れないようにしないと。

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/g.cpp

これも普通なのか。

テーブルは時間*駅で持ちつつ、

計算は電車*駅で抑えるのが楽するコツ。

http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/h.cpp

最後も普通。

[]部屋の掃除 部屋の掃除を含むブックマーク 部屋の掃除のブックマークコメント

部屋を掃除しているのだが、もう何年も掃除していなかったので、

なかなか進まない。とても大変。

しかし、すごく懐かしいものがたくさん出てきて困る。

中学高校までの私はとんでもない文章を書いていたのだなぁとか。

今ほどでない?そうですね…。

[]安楽椅子探偵 安楽椅子探偵を含むブックマーク 安楽椅子探偵のブックマークコメント

うーん、解答編を見たが…

まさか本当にテロップの無い人から犯人を持ってくるとは思わなかった。

しかし…あの二人ならやりかねないということか。

そういうわけで、まともに検証してなかった。

一度聞いた声を忘れない、という消去法の前提にしても、

サイン会で声をかけただけなのを覚えているというのは

なんだかムリがあったような気がするし、

あの出題編では、ノートを破った人が犯人と同一、

インターホンでのやり取りで知らない声が聞こえてきたという保障

両方厳しいような気がした。

うーん。

今度のことで、この辺のヒントは素直に用いるものだということが分かった。

たとえその結果が今回のようになったとしても。

あんまりあら捜しをするなということですな。


解答編終了後に本の告知みたいなのがあって、

え、、?び、びっくり館の殺人

館シリーズ新刊ですか?

なんというか、前作から一年半だし、

まさか一年半で出ると思っていなかったし、

一年半でもずいぶん早いと思ってしまうし、

そもそもタイトルでびっくりだし、

読む前から驚かせるとは、さすが綾辻氏だなぁ…。

まぁ、出たら読ませてもらうことにします。

wdwd 2006/03/15 16:52 犯人については、むしろ、叙述トリックの新パターンとして評価します。

それよりも、今回の問題には、推理クイズとしてはOKだけど推理ドラマとしてはNGな点がひとつあります。それは、第二の殺人の犯人が第一の殺人の犯人であることの証明が弱いことです。第一の殺人の被害者の所持品が第二の殺人の現場に残されていたことから、第二の殺人の犯人が第一の殺人またはそれに伴なう死体遺棄の現場にいたことまでは推測できます(それも、ちょっと穴があるけど、それはおいときます)。しかし、そのことは、第一の殺人の犯人であることを帰結しません。

今回は、問題のルールとして「単独犯である」が入っているので、このルールにより解答編は推理クイズとしてはOKになります。しかし、推理ドラマとしてはNGです。「殺人犯は死体も証拠も放置して現場から逃亡したのだが、別人が事後になんらかの理由(殺人犯をかばうためとか、自分が疑われると思ったとか)で死体遺棄と証拠隠滅を行った」も、「連続殺人だと思われていたものが、実は便乗殺人だった」も、推理小説ではよくあるパターンです。推理ドラマとしては、これらの可能性をつぶす必要がありますが、今回のドラマでは言及がありません。

tanakhtanakh 2006/03/21 01:16 叙述トリックですか…うーん。
単独犯という条件をつけても釈然としないところもありますが…うーん。

2006年03月14日(火) 後期試験に想う

[]後期試験 後期試験を含むブックマーク 後期試験のブックマークコメント

今日、明日にわたり、後期試験が行われているようだ。

何を隠そう、私も後期試験で入った一人なので、

後期試験というものには特別な思い入れがある。

その後期試験も今年を最後に終了してしまうらしい。


少し前にドラゴン桜なる東大合格を目指すストーリードラマが放映されていた。

そこにおいて、"東大など簡単だ"などという台詞を耳にしたのだが、

なら京大はもう寝てても入れるぐらい簡単だな、と思ったりしていた。

いや、東大が簡単というのは否定しない。

優秀な学者になるべき人材などやすやすと東大に入れるはずだし、

現にそういう人を私は何人も知っている。

要は東大生だってピンきりなのだ。

しかし、それでも東大はある程度のレベルを保っていると思うし、

底のレベルは低くないと思う。

その根拠は東大入試システムにあると考える。

東大入試の区分が(理/文)1〜3の6種類しかなく、

特に理系に限ると異様な合格最低点を誇る理3を除いて

理1と理2、どちらかが極端に入りやすいということも無い。

受験生を大きなプールに集めてそこから選別するというのは

学生の質を安定させるのに有効なのだと思う。


そう、なんだかんだ言っても東大の合格最低要件はある程度高い。

そこで京大の話になるのだが、

京大東大のように大きな区分で受験を行わず、

(他の多くの大学がそうであるように)最初から学部・学科単位受験が行われる。

受験生を細分し、そこから個々に選別するという方式なので、

どうしても学部・学科間格差が生まれる。

たとえば工学部内だけでも、合格最低点の高いところと低いところでは

100点ほども差が有り、これはどう考えても無視できるオーダではない。

我が情報学科も私が入った年は難しい方だったのだが、

去年のデータを見てみると平均点はそこそこ高いが

合格最低点は最低レベルという良く分からない状態になっている。

(これはむしろ同一学科間ですら学力格差が生まれているということなのだが、

とりあえず今はこれはどうでもいいのでおいておく)

工学部内だけでもかなり格差があるのだから、

これが全学となるとさらにレベルはまちまちとなる。

その最たる例が○○部○○学科が定員割れに近い状態、とかで、

もはや京大は学部を選ばなければ

ほとんど誰でも入れる状態だと言っても過言ではない(…のかな?)。


しかし、やはりそういうのはあまり嬉しくないというか、

興味のもてない分野を最低4年も勉強しなければならないというのは

拷問に近いものであるので、

望まない学部を選ぶというのはやめることにする。

私は工学部に行きたかった…ので、以下ではとりあえず工学部について考える。

(工学部に行きたくない人にはちょっとどうでもいい話になります)

工学部もピンきりとはいえ、やはり最低レベルはそこそこで、

あるいは年によりまちまちで、また自分の行きたい学科が

今年レベルが下がるかどうかも分からない。

結局正面から入ろうと思うと京大にしてもある程度は勉強しないと難しい。

しかし、私ははじめに寝てても入れるぐらい簡単と書いた。

そう、京大工学部にはとんでもない抜け穴があるのである。

それこそが後期試験であり、ろくに受験勉強もしていなかった私が

あろうことか滑り止めに受けろと高校の担任の先生に言われて

実際に滑り止めになった脅威の試験なのである。


ここで工学部後期試験について軽く説明しておこう。

試験については基本的には各学科異なるのだが、

おそらく共通だと思われることは一つ。

"変な試験"であるということ。

後期試験においてはこれまでやってきた受験勉強というものを徹底的に否定される。

嫌がおうにも皆が同じスタートラインに立たされる。

センター試験の成績すらリセットされる。

頼りとなるのは己が思考力のみ。

他人より秀でた思考力を示せた者がみごと敗者復活を果たせるのだ…。


…というとえらく大層に聞こえるし、実際に普通の受験生がするような

受験勉強しかしてこなかった人にとってはあながち間違いではなかろう。

ところが実際には皆同じスタートラインとはいえない。

各学科の試験においてはそこで研究を行うにあたって

適性になると思われる能力を重点的にチェックされる。

たとえば建築試験だと空間認識能力を問われるようなものが出ていたような気がするし、

情報だと主にアルゴリズム的発想力を問う試験が出される。

これは直接的に知識は問われないとはいえ、

実際のところかなり経験がものを言うものだ。

たとえば、アルゴリズムのアの字も知らないような人と

日々プログラムを作りまくって、色々なアルゴリズムを実装している人、

どちらがアルゴリズム的発想に長けているかは一目瞭然なわけで、

こういう試験はそういうあらかじめ特定の学科に適性のある人にとっては

非常に有利なものだったりするのだ。

もちろん私はここでいうプログラムばかり作っていた人なので、

あたかも当然のように試験パスすることができた。

これは有る意味当然で、こんな試験

プログラムを書いたことの無い人に負けていては、

まったくもって何をやってきたのかということになる。


このように京大工学部にはかなり裏っぽいというか、

抜け穴というか、実にすばらしいものがあった。

今年受験生プログラム馬鹿の人が居て、情報系学科に行きたいなら、

ひたすらその能力を鍛えて京大情報に行くのも一考では?

あるいはそうでなくとも今からアルゴリズムを考える訓練を繰り返して

一点突破を狙うのも一考では?やっていない人を超越するのは容易いはず?

…ということを今年の9月ごろに書こうと思ったのだけど、

結局書くのを忘れていた。何のアドバイスにもなっていない。

まぁ、こんな文章をアテにされて受験生から苦情が来ても困るので、

事後ぐらいでちょうどいいか。


とにもかくにも、どうやらその後期試験が今年で終わってしまうということなのだ。

確かに問題セットを考えるのは大変だろうし、

教授総出で面接を行うのも大変だとは思う。

しかし、後期試験廃止の理由として労力のほかに

才能ある学生の選抜に役立っていない、などとあったのはショックだった。

まさに私は京大に入らなくても良かった人材というか、

間違って入れてしまったような人材だというか、

そういうことなのだと言われたようなもので、

このことは私が京大から離れようと思った遠因でもある。

これはまったく酷い言われようで、

私の努力が足りなかったのか、

京大学生評価がおかしいのか、

どちらにせよ、外に出て名を上げて

京大にはせいぜい後悔をしてもらおうと

そう反骨心を燃え上がらせている次第なのである。


何の話だか良く分からなくなってきたが、

要するに、後期試験の終了は非常に残念である、と

元後期試験合格者から言わせて頂きたい。

"京大らしさ"というものがまた一つ失われたのではないかと

そう思われて仕方がない。

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

2006年03月08日(水) 逆ポーランド記法

[]逆ポーランド記法および、ツリーの preoder/postoder traversal 逆ポーランド記法および、ツリーの preoder/postoder traversalを含むブックマーク 逆ポーランド記法および、ツリーの preoder/postoder traversalのブックマークコメント

今日、もうすぐ廃刊になるかわいそうなCマガジン電車の中で読みながら

ぼーっと考えていたら、ふと逆ポーランド記法の記事が目に入ってきた。

曰く、Infixで書かれた数式を計算するのは難しくて、

逆ポーランド記法で書かれたものなら簡単だということだ。

Infixだと優先順位の処理とかが大変で(…本当か?)

逆ポーランド記法ならスタックを用意するだけで計算ができて、

いずれにせよ簡単だということなのだが、

ちょちょちょ、、、ちょっと待てよ?

逆ポーランド記法だとスタックで計算ができるって自明なのか?

少なくとも私は今までずっと、”そういうもん”だと思ってきて、

よく考えたことが無かった。


逆ポーランド記法とは言い換えると

計算式をツリーで表現したときのpostoder traversalということで、

これをスタックで計算できるということは、

前からスキャンすることにより、確定的に、線形オーダで、

元のツリーが復元できるということになる。

計算式のツリーは二分木で、リーフが数、ノードオペレータと決まっている。

トークン列中、オペレータが出現すると、

それよりも前に二つ以上のツリーをあらわす列が必ず存在しており、

そのツリーがリーフのみなら数字で、

そうでなければオペレータ終端のトークン列であるはずである。

オペレータ終端の列はさらにそこでツリーを構成しているはずで、

そうならば、トークン列を前から見ていく途中で、

構成できるツリーを全てリダクション(ここでは単一の数字にするとする)するとすると、

結局、各オペレータの出現において、必ずその前に二つの数字が現れることになり、

そのオペレータが構成するツリーはそのオペレータルートに、

直前二つの数を子に持つツリーでしかありえない。

そういうわけで、確かに逆ポーランド記法を前から見ていくことにより

確定的に線形オーダで一意にツリーが構成可能である。


と、これだけではいまさらながらに逆ポーランド記法の仕組みを理解したに過ぎないが、

実はこのことはもっと一般的に応用できるような気がする。

先の説明をきわめて一般的な言い方をすれば、

ある隣接三トークンを見て、それが確実にツリーをなすということができるような

規則が有るとすれば、そのようなツリーのpostoder traversalが与えられたら、

それを前から見ていき、リダクションできるところを発見し次第リダクションすれば、

確定的に一意に線形オーダで復元可能、ということになる。

そしてこれはスタックを用いて簡単に実装可能である。

また逆にpreoder traversalが与えられたら、

今度は後ろから見ていくことにより同様にツリーが復元できる。


(これは微妙にこのまえの合宿でやった問題に絡んでいるが…)

ツリーのpreoder traversalが与えられたら後ろから見ていくとか、

これはかなり定石になるのではなかろうか。

あるいはこれは有名なことだったりするんだろうか。

ともかく、これからツリーの問題が来たら、

これが適用できないか考えてみても良いと思った。

それに気付かせてくれたCマガジン感謝…。

rerorero 2006/03/09 16:06 preorder を前から見ていくのは「確定的に一意に線形オーダで復元可能」にはならないの?前から見るか後ろから見るかの違いは,再帰を使うかスタックを使うかの違いに過ぎない,本質的には変わらないような気がするけれど….

tanakhtanakh 2006/03/09 16:46 ここでの例のような計算式のpreoder表記ならば、記号の出現でそのままリーフでないノードと確定できるのでどっちでも一緒ですが、トークンの種類だけではどちらともいえない場合、たとえば、ルートからリーフへのパス中の数の和が全て等しいようなツリーというもののpreoderが与えられて、そこから元の木を復元するようなものですと、簡単な例として、1 1 1 1 2 のような列を与えたとき、これの元のツリーは (1 (1 1 1) 2) になりますが、これを前から確定的に復元することは不可能です(…多分できなさそうです)。しかし、後ろからたどれば確実に(ノード リーフ リーフ)ということのできる列の出現の一つ目はValidなので、これを帰納的に適用すると確定的に復元できます。よって一般的には、本質的に異なると思います。

rerorero 2006/03/10 03:43 なるほど.そういう例を思いつきませんでした.
ただ,
1. まず入力列を全て左子ノードと見なして再帰的に繋ぐ.
 例:入力列 1 1 1 1 2 の場合,(1 (1 (1 (1 2 0) 0) 0) 0)
2. 左子ノードと右子ノードの数が異なるとき,親ノードに伝播して2分木を再構築.
 例:(1 (1 (1 (1 2 0) 0) 0) 0)
  →(1 (1 (1 1 2) 0) 0)
  →(1 (1 1 1) 2)
とすると,再帰版でも一意に線形オーダで復元可能にはなります.
ただ,手順が複雑で面倒ですし,「確定的」とは言わないのかなあ….

tanakhtanakh 2006/03/11 00:27 うーん、確かにそれでもいけそうですね。
後ろから三近傍の構築できる部分木を見つけつつ構築していくということになって、本質的にはスタックを用いるのと同じような感じですね。ステップ1を再帰的にやるのは簡単ですが、ステップ2の処理は再帰的にうまく書けますでしょうか?それと、木の再構築の処理が入るので、前から見ていって再帰的に処理しているという感じではないような気もします。

rerorero 2006/03/12 00:52 > 前から見ていって再帰的に処理しているという感じではないような気もします。
まさにその通りで,後ろから見ていくのをわざわざ再帰でややこしく書いているだけっぽいですね.

2006年03月07日(火) 駄目だ…

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

PPLに行って、ワインを飲んできました(?)。

私はなんだか直接発表はしないような感じになったので、

気楽といえば気楽だったけど、何をしに行ったのか良く分からない状態で…

ひとつ言いたいのは、ご飯が多すぎる。

[]安楽椅子探偵 安楽椅子探偵を含むブックマーク 安楽椅子探偵のブックマークコメント

そういうわけで、一応解答を送付。

しかし…今回はだめっぽいなぁ…。

前回は存分に考える時間があったのに、

今回はPPLに行っていたおかげで、

推理期間4日間のうち実に3日間がつぶれてしまったわけで、

言い訳がましくなってしまうけど、

正直本当に全然考察が足りない。

ああ…、三年ぶりだというのに、

十分に楽しめなかったのが本当に悔やまれる。

できれば次回はもう少し短いスパンでやってもらえると

ありがたいのですが…。

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

2006年03月04日(土) 年度末のばたばた

最近驚くほど忙しくて、体が三つぐらいに分裂しそうです…

[]近場に宿泊 近場に宿泊を含むブックマーク 近場に宿泊のブックマークコメント

なんだかどういうわけなのだか知らないのだが、

ホテルグランヴィア京都の宿泊券が有ったらしいので、

使わぬのももったいないということで宿泊してきた。

(私こんな近くのホテルに泊まったの初めてです…)

場所はいわゆる京都駅ビルなので、

もう何百回、あるいは千回以上も来ている場所かもしれないが、

そんなところに宿泊するというのも、

なんというか、日常の中の非日常というか、

なかなかなんともいえない気分であった。

内装はかなり立派で、部屋も広く、

ベッドにはなぜか枕が三つも積んであったり良く分からないところに豪華で、

トイレにはウォッシュレットもあって痔の時も安心だし(?)、

全体的にみてもかなりクラスの高いホテルだと思った。

そのためか内蔵のレストランなどは目が飛び出るほど高いので、

なかなか終始リッチに行くのは厳しいような感じで。


写真をいくつか。

f:id:tanakh:20060302180240j:image:w320

南向きの部屋だったので、窓の外は京都駅

でも、反対側は駅内部に包まれているので、

たぶん、景観はましなほう…

f:id:tanakh:20060303002000j:image:w320

怪しい場所

f:id:tanakh:20060303102111j:image:w320

ひな祭り

[]Maximum Winter Contest 2006 Maximum Winter Contest 2006を含むブックマーク Maximum Winter Contest 2006のブックマークコメント

Maximum Winter Contest 2006オープン参加した。

日本語文章でしかも個人戦ということで、

チーム内で争うのは実はこれが初めてだったかもしれない。

これで万一他のメンバーに負けたりしたら

私はコードを全部書くという役割をおろされかねないところだったが、

まぁ、それは危惧に終わって一安心だ。

しかし、現役はもちろんOBの人にも負けるわけには行かないなぁと

思っていたのだが、どうやら最終成績では駄目だったようで、

なんというか残念。

というか、問題Cがかなりモヤットした。

問題Cの難易度は超易しいとされていたが、そんなことは無いよね?

未だに効率的なとき方分からないし。

通ったアルゴリズムは間違ってるし。

間違ってるけど、他の人たちがこんなにさくさく通るということは

これが想定解か?と適当アルゴリズムで送ったら、

しっかり通るのなんの。

結局もやもや。

O(n^3)なら自明な解が有って、

一つの円に対するほかの円の交点を列挙して

レンジを計算してごちゃごちゃすると

O(n^2)で解けるような気がするけど、

こんな実装が簡単なはずが無い。

うーむ。

途中でサブミッションレスポンスメールが帰ってこなくなって、

ちゃんと動いてるのか分からなかったから適当に山ほどサブミットしたら

WA19回ということになってしまった…。

なんかショック。時間もかなり使ったし。

そのときのレスポンスはなぜか終わって6時間ほどあとになってから

19通まとめて送られてきた。一体どうなっていたんだろうか。

そのほかの問題は、気付けば一瞬で書けるような問題ばかりだったので、

そこそこいけたような感じ。

問題Dはクラリフィケーションしないと解けなさそうだった。

全体としてはこんな感じ。

しかしなぁ、問題Cがなぁ…。

うーむ。

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

2006年03月01日(水) コンテストを勝ち抜くために必要だと思われるもの

何が書きたかったって、すっかり忘れてましたがな。

三月三日の深夜に http://www.asahi.co.jp/anraku/ これがあるのです。

いやぁ長かった。前作から二年九ヶ月ですかね?

前作応募してエレガントな解答10個にまで選ばれながらも

抽選で50万を逃した悔しい思いをしてからずっとずっと待っていましたよ。

前回抽選のところとかテレビで見ていてばくばくもんでしたよ。

50万がーー、もう、なんというか、やばかったですよ。

そういうわけで、私の本サイト(最近全然更新してないけど…)の

名前の由来にもなっている安楽椅子探偵がいよいよ明後日ですよ。

皆さん是非とも観て解答を送りつけましょう。

[]コンテストを勝ち抜くために必要だと思われるもの コンテストを勝ち抜くために必要だと思われるものを含むブックマーク コンテストを勝ち抜くために必要だと思われるもののブックマークコメント

・今回の合宿

2/24〜27日に合宿があったのだが、

その際にどういう心積もりで望むかというのが内心テーマだった。

経験の少ないチームだと、このような集まって問題セットを解くという経験だけでも

非常に刺激になって、絶大な効果が期待されるのだが、

うちのチームはおそらくこういう問題をもう解き慣れているし、

5時間で8〜10問のセットを解くと言うのも幾度となく経験しているので、

もはやそれだけでは効果薄だと感じているところだった。

それでも合宿というのは貴重な機会だし、

それに、私個人としてもうちのチームとしてもここ数ヶ月は

ろくに練習ができていないので、ここで何かを掴んでおきたかった。

ただ漫然と問題を解くだけではいけないだろう。

というのも、単にこなした問題数と実力との間には

そこまで相関があるようには思えないからで、

実際のところ、問題数だけ見るともっと強くてもよかったチームとか、

そんなに問題数を解いていないのにすごく強かったチームとか、

そのあたりが実証している。

何かを意図を持って問題に取り組み、

確実に自分を変えていかないといけない。

そういうわけで、今回私は一応ある意図をして問題を解いていて、

さらにそれがある程度思惑通りに進んだ。

他のチームの人がみんな私のようなタイプでは無いとは思うが、

ここで後継の人たちのために私の意見を書いてみようと思う。

「私は無知だが、自分が無知であることを知っている」

唐突だが、私は勉強熱心な方ではない。

アルゴリズムだって人一倍勉強していないし、

私が知っていることはおそらく大体の人が知っていることに過ぎないはずだ。

むしろ他の人が知っていることの多くを知らないと思う。

そんなことは無論承知済みである。

去年の時点でそれまで完全に独学でやってきた知識を

一応基本を勉強してそれなりに穴は埋めたはずだが、

そんなので十分なはずが無い。

というか、アルゴリズムなんてものはそれこそ数限りなくあるわけで、

全てを勉強するなんてことは不可能なのだ。

GNCの人などはなるべくたくさんのアルゴリズムを習得して、

カバーできる範囲を広げることが重要だと考えておられるようだが、

これがなんというか、私の経験によると、外される時は外される、なのだ。

特に某リージョンなど知識重視の問題を出して来て、

それはおそらく日本において普通教えられているアルゴリズムから

相当剥離してしまっているように思う。


どうせ外されるのなら、そこまで知識を重視しなくても

良いのではないかというのが私の意見だ。

いや、それでも知識が重要だというのには私も異論は無い。

そうではなくて、少なくとも知識を拠り所とするようなことはしたくないということだ。

当然知っておくべき知識は勉強する。

でも、終わった後で、「こんなん知らんがな!」となりそうな

アルゴリズムまでは無理して勉強する必要は無いのかなと思う。

アルゴリズム学習というのはかなり大変だということに加え

(特に私なんかはものを覚えるのが苦手なので…)

知識は時に発想の障壁になり得ることにも留意しなければならない。

  • ひらめき重視

では、知っていれば解ける問題をみすみす捨てるのか?

これはどちらかといえばYesだ。

そんなことでいいのか?これがある程度許されると思っている。

というのも解けない問題というのは知らなくて解けない問題だけでなくて、

思いつくことができなくて解けない問題もあるはずで、

というか、むしろそういう問題の方が往々にして多いわけであるので、

そういう問題を徹底的に排除することが最重要なのではないかと考える。

つまり、終わった後で、「ああーっ!」とかそういう問題があってはいけないのだ。

そういう問題は何も知らなくても解ける問題なんだから。

ひらめきというのは時の運ではない。

これは確実に鍛えることができる。

具体的な方法を述べるのはなかなか難しいが、要するに頭のやわらかさで、

物事をいかに多角的に見ることができるかなのだ。

個人的な意見であるが、これはひらめくという行為を繰り返すことにより

徐々にそのような能力が伸びていくのではないかと思う。

ひらめく能力というのはあるドメインに特化した能力ではないし、

基本的に簡単な問題を含め全ての問題に影響を及ぼす。

簡単な問題の解を発見する時間の短縮、さらに解ける問題数が底上げされ、

もしかしたら知識を前提とする問題について別解を見つけることもできるかもしれない。

鍛える具体的な方法は難しいと書いたが、

今年のImagineCupのアルゴリズム部門の課題なんかはまさにうってつけかもしれない。

解のルートを見つけるのに相当頭を使わなければいけないので、

とても頭を鍛えることができる。

ICPCにおいてはアルゴリズムばかりが取りざたされるが、

実のところヒューリスティックが使えるケースがしばしばある。

そういうケースでは積極的にヒューリスティックを使っていくべきだ。

将棋にも詰みより必至という言葉があるように、

どうせ解けるのなら簡単な方を選ぶべきである。

ヒューリスティックで問題を解くといっても、

闇雲に適当な処理を並べたら良い訳ではない。

ちゃんと解けるめどの立つ方法を考えなければならない。

この辺の感覚は微妙で、質の良いヒューリスティックを生み出そうと思うと

ある種の経験と勘がものを言う。

この感覚は実際にいくつかの問題をヒューリスティックで通して感覚を磨くしかないのだが、

ヒューリスティック初心者には、とりあえずプログラムプロムナード

2002年9月号 「点の集合を包含する球」

2002年12月号 「三角形の分割」

あたりを読まれることをお勧めする。


・実際の合宿の成果

ここを参照。

一回目

問題A:問題なく解法を思いつく

問題B:二部グラフになることに気付かず。でも、気付いてもそれから使うアルゴリズム知らなかったしいいか…

問題C:ごり押し問題なので普通に解ける

問題D:解法をちゃんと構築できる

問題E:ヒューリスティックで解く。想定解は線形計画法。

線形計画法なんかそらで書くことは不可能だし、こんなものここで書けなくても良かろう…。

構築したヒューリスティックは線形計画法と大体等価という話もあったが、

ここではアルゴリズムも考え方もコードも超単純で、

難しいことなんか何も考えていないことが重要だろう。

問題F:時間が無くて解けず

問題G:問題なく解法を思いつく

問題H:幾何的解法をとる。想定解は連立方程式を解く方法。

掃き出し法なんか難しくないと言われてしまったが、

一次一変数の方程式を解くほうが簡単なのは明白なわけで…。

なお、この解法も連立方程式等価という話になったが、

やはり難しいことを何も考えていないのと

コードが超単純になっているのが重要

問題I:時間が無くて解けず


二回目

問題A:問題なく解法を思いつく。必要知識、ダイクストラ

問題B:想定解よりオーダの低い解法を思いつく

問題C:ヒューリスティックで解く。想定解は空間を分割する方法。

想定解は思いついて実装できても良かったが、

質の良いヒューリスティックが実現できて通ったので問題なかろう。

問題D:解法が全く思いつかず。

問題E:適切なアルゴリズムを知らずに変なことをした。

想定アルゴリズムはSuffix Array。

しかし、もっと別のアルゴリズムでも通る。

問題F:問題自体が分からず

問題G:解法は分かったものの、誤差の取り扱いを間違ってWA連発。ダイクストラ

問題H:解法を思いつくことができた。日本チーム唯一。

問題I:問題なく解法を思いつく。

問題J:問題なく解法を思いつく。


さて、このような結果になったのだが、

これを見てもらえるといかに発想力が重要なのかが分かるだろう。

今回うちのチームはダイクストラぐらいしか知識を使っていない。

全体としては割と良好な結果で、まともに考えて解法が思いつけなかったのが

二日目の問題Dぐらいだった。

これでまだ速度面の問題や二日目の問題Dなど伸びしろがあるので、

知識を増強させる前にまだやることがあるのではないかと思う。


・その他

今回は中国チームも何チームか招待してコンテストを行っていたのだが、

その中でもやはりNimrodは強い。ここの強さは本物だ。

現時点でうちのチームより一回りか二回りは強い。

東京大会の時も同じような印象だったし、

正直今から一ヶ月では勝てるようになれないような気がする。

でも、他の中国チームには勝てないことはないと思う。

知識でで負けていても、発想が生かせるケースとなると、

そこまでこちらに不利なわけでもない。

あとは世界大会が知識重視ではなければ…。