ICPC
メモライズと聞いては、Haskellを出さないわけには行かない。 いろいろやっているうちに30行を切った。 あの、苦戦したD問題がこんな小さなコードになってしまったよ。 実行時間は12秒ぐらいなので十分現実的なコードだろう。 import Control.Monad import D…
↑でちょっとあんまりな結果になってしまったので 大分取り乱してしまいましたが… 冷静になって計算量を評価してみる。 計算をキャッシュするテーブルが30*(2^8)=7680 それ一つを計算するのに必要な再帰的呼び出しの数=30*8=240 というわけで全体の計算量は18…
書いてみた。なにこれ？超簡単。 3時53分から書き始めて4時5分に完成。 12分だった。しかも、一箇所のバグもなし。 コンパイルもFirst Inputも一発通過。 なにこれ？ 書いてる途中一回も迷わなかったし。 しかも実行速度超速い。 提出したやつ(-O3で) → 9秒 …
ありゃあ？？？ なんか、↑で別解を検討していたら思ったんですけど、 これってもしかして、 関数型プログラマである私が超超超得意とする 深さ優先探索+メモライズで解けちゃうですか？ なんたるちあ。 いまから実装してみます。
本体サイトのほうで、D問題、馬券の使い方を固定してその8!に対して ダイクストラを最初に思いついたが、馬券を固定してのダイクストラが分からなかった、 見たいな事を書いたが、今さっき思いついてしまった。 ある地点までにある枚数を使ったその時点での…
G〜N〜C〜、う〜ら〜め〜し〜や〜。 もとい。 うらやましい〜です。 もう、おめでとうとしか言えません。 問題数で負けてますからね。 今年はすでに各所で問題の考察が公開されていますが、 私も一応書いておきました。 (本体サイトのほうに。) E以外のソー…
完全に負けました。 全問解くこともかなわなかった。 もう、だめだ…
入出力データが公開されたので、 早速E問題の出力をチェックしてみた。正解だった。 vector > > などの乱舞するプログラムを 一発で通せて、なんとなく嬉しい。 Bの誤審がなければぎりぎり間に合ったんではないかとも思うが、 M氏は10分ぐらいどこからでも捻…
模擬練習会があった。 今日も二人だったけど、今日はちゃんと集まってやった。 キーボードも英語キーボードでやった。 結果は、とりあえず一位だったが、どうにもすっきりしない。 というか、こんなんじゃ駄目だ・・・。 最後のほう、完全にぐだぐだだったし…
GNCの人が企画しておられる練習会が今日あった。 ちょっと前にお誘いをもらったので参加することになった。 これもK氏は出なかったけど… …ちょっとは三人での練習をさせてくれ。 で、参加したわけであるが、会場は東京だったので、 いつもどおりリモートだ。…
6月19日に練習会があるらしい…がK氏が参加できない模様… ショックである。 国内予選など私一人で楽々だとかまだ思っているのだろうか。 今年は海外派遣を真剣に狙わないといかんのですよ。 去年の強かった人たちが結構出場資格がなくなっていっているので、 …
締め切りがもうすぐそこですね。 うちのチームも登録を済ませました。 なーんか、今年、京大からまだ2チームなんですけど… いったいどうなってるのかね…？ それはともかく、全然練習してませんよ。 春から一問も解いてなかった。 とりあえず、いくつか解いて…
上の文章が良く分からん感じになってしまったので、 問題についての説明だけこっちにも書いておきます。http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf問題はここから参照できます。 問題A 一方の図が他方の図の一部になっているかを判定する…
いつもはぐうたらな私がいつに無く働いております…。 といいますか、ICPC世界大会が一週間後ですよ。ほんとですか。 今まで全然準備をしてこなかったしわ寄せが。 ただでさえ初海外で大変なのに、去年から 会場に自由な紙媒体資料の持込が制限されて あらか…
なんだかんだで後二週間を切っている。 進まぬ準備。 Haskellerだけに、作業を遅延評価してしまっているようだ。 そんなわけで、この前の acm.uva.es の world final warmup 2 に 参加した。またもや世界大会レベルの難問ぞろい (一問むちゃくちゃ簡単なのが…
世界大会出場を受けて総長に挨拶に行ってきた。 総長が図書館横のあたらし目の建物に居られることは 知らなかったが、なんだか物々しい警備であった。 ここ最近まで一階部分は一般公開されていたようなのだが、 なんんでも最近の授業料値上げ騒動？と石垣問…
みたび東京へ。 なんだかどっと疲れた。 前日から行って東大に泊まっていたのだが、 GHC6.4のWindows版が出ていたので、 M氏と朝までHaskellでシューティングを作ってしまった。 最初は何かポリゴンがへろへろと動くだけだったのだが、 「自機から弾を撃たな…
L-Gap Substrings これは難問である。K氏とM氏と三人で何時間も考えたけど分からなかった。 DPなんだろうか。問題のサイズから考えるとそうとしか思えないが。 うーん。
また東京に行ってきたらしいです。 今回はお金が京大から出るらしいけど、 帰りの特急券の領収書を貰うのを忘れたらしいです。 私はどうなってしまうのでしょう。 成績はまずまず…か?悪くはなかったけどこれで楽観もできないな。 一日目遠隔の韓国チームに負…
残りの問題を解いた。 F問題は実装がめんどくさいと思ってたのだが、 実装してみると全然めんどくさくなかった。 I問題はM氏が解いた。体積を求めるのはさほど難しくない (数値積分を使った模様)ので、 立体を微小に膨らませたときの体積を求めることにより …
当日書いたソースを送ってもらえたので、公開してみました。 正直そんなに綺麗なソースではありませんが…。
本体サイトに文章書きました。 色々と書きたいこととか出てきて、まとめるのが大変でした。 私の超(駄目)筆力による臨場感をどうぞ。 世界大会でも恥ずかしくない成績が残せるよう頑張りたいと思います。
なんだか闘病日記みたいになってしまいましたが、 (いつも書こうとしたこととちょっとずれてしまうんだよなぁ) 昨日はACM/ICPCアジア予選愛媛大会でした。 それでまぁ、勝ちました。 詳しい状況は明日の日記にでも書きます。 克目して待たれよ…？
なんか愛媛大学のICPCのページに外国チームが決まったとか書いてあるので http://www.ehime-u.ac.jp/ICPC/jp/regional/participants.html#foreign 見てみると…。中国ばっかりやん。(ばっかりというか、４チームか) 中国に勝つためにこの練習会やってたんとち…
この前の合宿に続き、今日は"東京大学"でICPCの練習会が あったもよう。まぁ、うちのチームにとっちゃ東京大学でも 北海道大学でもあんまり変わりは無いのですが。 東京に行くわけにもいかないので、オンラインからこっそり参加となったわけです。 (いつもの…
7月の初頭、私達はICPC国内予選に参加し一応5位という成績で通過したのであるが、 アジア予選日本会場の大会で中国人が毎度毎度一位を掻っ攫っていくのが とある方々？にとってお気に召さない様子で、 日本強豪チームを世界強豪レベルにまで持っていくことを…
ずっとやろうと思っていたのだが、 なんだかほかのことをやっていたらこんなに遅くなってしまった。 ゲームが一段落した?ので気晴らしに解いてみることにした。 問題Dぐらいまではさくさく解けたのだが、 問題Eは結構めんどくさかったし、 問題Fはなんかへん…
http://ccserv.adm.ehime-u.ac.jp/ICPC/jp/ なんと出力例が公開されているではないか。 問題Eと問題Fについては正解していなかったので、 公開している解答が合ってるかわからんかったんだよなぁ。 ということで、チェックしてみたところ、 サイトにアップし…
今日の02:00から06:00まで http://acm.uva.es/ で オンラインコンテストがあったので、とりあえず参加した。 というか、参加しようと思っていたのだが、すっかり忘れていて 気づいたのは5時。しかしまぁ、一時間だけ頑張った。 簡単そうな問題を適当に。 問…
コンパイラ作るつもりがなぜか問題Aの改良を… Scheme的にはCPSだけど、Haskell的には関数合成だでよ!! ということで、再実装。 入れ替えを関数にして、それを合成して、それに0を適用。 ついでに入力のパーズをちょっとだけ手直し。 全体的に幾分かすっきり…
