ほんばん！

あと1時間ぐらいで本番になります。



自分にとっては最後の大会になるので頑張ってくるよ！



ライブ中継はこのアドレスらしいので、よければ見てくださいｗ



http://icpclive.com/

dress rehearsal

おはようございます。こっちは5/29の18時です。

さっきまでdress rehearsalというのがありました。

行ってみれば「ほぼ完璧なリハーサル」って感じで、

厳格なルールの下で、問題やら雰囲気も、

web中継用のカメラまで本番さながらに動いていました。

調べてみたら語源は(舞台稽古で)dressを着てやるリハーサル、らしいですね。

ICPCはドレス着ないのに何でだろうと思っていたけど、そういうことでしたか。

さて明日はいよいよ本番です。

リハーサルではまぁそれなりに解くことができたので、

明日(日本時刻では今日30日の22時から)の本番、頑張ってきたいと思います☆


ちなみに...フォトギャラリーとかがあるらしいです。

もうすこししたら、今日の様子も公開されるかもですね↓

こちら

大会のページ

ホテルついた！

今現地時刻で朝の1時ですが、やっとホテルに着きましたｗ

サンフランシスコからオーランドに飛ぶ飛行機が

出発予定から2時間ぐらい遅れて出発したので、

まぁ大学を出て関空に行くところから計算すると24時間の大移動になりました。

それにしてもいいホテルですね、、びっくり...

明日はIBMの人の講演とかを聞く日なので、

のんびり過ごしたいと思います◎

さんふらんしすこなう！

ふろりだまであと５じかんかかるらしい・・・

あめりかよこほうこうにひろすぎじゃね？

きょうがく。

てーまそんぐ

今回のテーマソングはこれでいくことにしました



九州新幹線開通のときのCMソングらしいです。

よく分からんけど盛り上がれる曲調なので良いなぁと。

まぁ俺には歌詞ききとれんのだけどね(笑)雰囲気雰囲気ｗ

ちなみにマイア・ヒラサワさんが歌ってるそうですよ　：０

あいしいぴいしい

さて、明日(今日)の17時ごろに関空いって、アメリカへ行ってきます。

メインの目的はICPCの世界大会。

「力まず練習どおり」ってのがうちのチームの良いところなので、

まぁ楽しむことを目標に、頑張って来たいとおもいます。

コンテストは30日の朝9時...日本時刻でいうところの、夜10時からです。

おそらく今年も生放送があって、

このページ　http://cm.baylor.edu/welcome.icpc　から

Live映像が見れると思います。

去年は各チームがプログラムを書いている様子が、

ものすごいどアップで映っていたと聞いていますので。。。

ちょっと面白そうだけど、やっぱりどアップは怖いなぁ(汗


ICPC最後の1試合、頑張って来たいと思います：）

東京大会

miracです、お久しぶりです。

この土日にICPCの東京大会に参加してきました。

結果はこちら。
http://icpc2010.honiden.nii.ac.jp/regional-contest/standing

従来のような "アルゴリズムは簡単だが実装が大変" という感じの問題が減って、

"実装は普通だけどアルゴリズムをしっかり考えないと解けない" 問題が増えたかな、

という感じです。


タイムラインはこんな感じ。

開始 5分前:
チーム内で「勝ちを狙わず楽しんで解きましょう」と話し合い

開始 20分:
例年通り A問題が簡単だったので、mirac が実装して提出。TLE (速度が遅く、不正解) 。
nkamae から修正案をもらったので修正を開始。

開始 35分:
A問題を修正して提出。AC (正解) 。
kaming と nkamae がB問題を考えていたので、そのアルゴリズムを確認。
よさそうな感じなので nkamae と交代。
mirac は他のチームがよく解いていたFを考える。

開始 55分:
B問題を nkamae が提出。AC (正解)。
Fがさっぱり分からんので nkamae に丸投げ。自分はDを考える。

開始 75分:
nkamae がFの大まかな解法を説明してきたので相談。
そのままでは解けない事が分かったので、
相談しながら15分ぐらい (?) かけてアルゴリズムを修正。
問題を読んだ mirac が入力部分を、それ以降を nkamae が実装。

開始 110分:
問題の本質ではないところが無駄にバグってたので、ひたすらデバッグ。

開始 125分:
バグがとれたっぽいので再度チェックして提出。AC (正解) 。
他の問題を読んで考えていた kaming から、Gが簡単との説明。
典型的ダイクストラだったので、ダイクストラ担当の mirac が実装開始。

開始 155分:
Gの実装・デバッグが終了。提出。AC (正解)。
この辺の時間に何をしていたか、あんまり覚えてない(笑)

開始 ???分:
Hが解けるっぽいことが判明したので、実装開始。

開始 ???分:
だらだら書いていたHの実装が終了。しかし"問題解釈が間違っていた"ことと、
"それを修正すると実行時間が8倍になる"ことが判明。
まぁやってみようかということで kaming と2人でプログラムを修正

開始 220分:
修正とデバッグが完了。最大ケースを入れると遅すぎたので一部高速化

開始 230分:
これ以上高速化する方法が思いつかなかったので、
TLE(遅すぎで不正解)にならないことを祈りながらHを提出。AC (正解) 。
Hを解いている間に nkamae がEを紙上でプログラミングしていたので、
そのアルゴリズムを確認して、交代。自分は再度Dを考える。
nkamae と kamingの2人でペアプロを開始。

開始 255分:
あと40分しかないのでDを考えることを諦めてEのデバッグに参加。
 
開始 270分:
Eのデバッグが終了。提出。AC (正解) 。
他チームに勝つためにはもう1問必要だということで、問題を選ぶ。
Dは多くのチームが解いているが、
3人ともアイデアがなかったので上位チームが解いているC問題を選択。

開始 275分:
終了まであと25分。
kamingがそれっぽいアイデアを提案。
3人で一般化したが証明できないので焦る。

開始 280分:
時間がないのでとりあえず mirac が実装開始。
あとの2人は証明を頑張る。

開始 290分:
実装する時間が十分にないことが分かったので、
先ほどまで言っていたアルゴリズムではなく、
"正しい可能性は少ないけど10分でも実装できるアルゴリズム"に変更。

開始 297分:
終了まであと3分。実装が終了。デバッグ開始。

開始 299分:
終了まであと1分。今まで実装していた"正しい可能性は少ないけど
10分でも実装できるアルゴリズム"に反例を発見。諦める。

開始 299.875分:
みんなでカウントダウン開始

開始 300分:
終了。チームメイト同士で握手。
8問ぐらい解くつもりだったのに、6問しか解けなかったのでちょっと涙目になる。

タイムラインはまぁこんな感じでしょうか。詳細はまた書くことにしますー。

今日は

国内予選です。
どきどきどきどきどきどきどきどき

せかいたいかい けっか！

こんばんは、miracです。

昨日、ICPC2010世界大会@ハルビン に参加してきました。

とりあえず結果だけ書くと、

103チーム中33位でした。

悪いともいえず、良いともいえず、

なんか微妙なライン(笑)


以下twitterに投稿した内容を書いてみます。


１問目を通したのが1時間45分ごろ
(コンテストは5時間なので全体の1/3以上)
といういつも以上のスロースタートっぷり。

1,2,3問目を通した時点では60位前後をうろうろしてたので、
もしや50位以下になるのではないかと
ひやひやしていました(50位以下は公式順位がつかないので...)

この時点で3時間ほどが経過していました。
他チームが解いている問題の解法を必死に考えていました。

最後1時間半ぐらいで2問を通すことができて、
5問正解の33位という結果になりました。
5問正解したチームの中では下から2番目ぐらいの遅さでしたが...汗

5問正解からあと1問解くかどうかが入賞(12位まで)できるかの
境目だったのですが、5問正解するのがギリギリで、
6問目はアルゴリズムも浮かばず、全く手が出ない感じでした。

そんな感じに不甲斐ない結果に終わってしまったのですが、
来年の出場権を目指してまた1から頑張りたいと思います。

おやすみなさい、どうもありがとうございました
>応援してくださったみなさま


まぁこんな感じでした。
icpcの公式ページで写真とかビデオとかも公開されていますが、
またおいおい紹介することにしますー☆

せかいたいかい

以下mixiのコピペなので、

以前に書いたことを書いているかもしれませんが、

まぁ気にしない方向でよろしくっ(笑



さて今、中国のハルビンというところに来ています。

中国でもかなり北にあるので、

気温は-15度から-25度の間を行ったり来たりしています。

外を歩くときはスキーウェアみたいな防寒着上下、分厚い手袋、

耳を覆える帽子、2重の靴下、というような重装備です。

まぁそれでも5分以上歩くと全身が凍りそうな感じになったり...(笑



さて今そんな寒いところに来ている理由なのですが、

以前の日記(11月ごろ？)にも書いたとおり、

ICPCというプログラミング大会の世界大会に来ています。

いろんな人の支えと、かなりの運によって、

ついに世界大会まで進むことができました。

どうもありがとうございます。



2/1にこちらに来て、様々なイベントがありました。

そして明日2/5、ついに大会のメインである

5時間のプログラミングコンテストがあります。

大会の時刻は日本時刻で11時から16時です。

多少前後するかもしれませんが、まぁだいたいそんな感じ。

で、大会前数十分から、大会中、大会後の数十分まで、

世界大会の様子がライブ中継されます。

URLはこちら： http://liveacm.hrbeu.edu.cn/

まぁ選手は黙々とプログラミングをしているだけなのですが、

去年のライブ中継ではアナウンサーがいたり、

ルールの解説をしたりとなかなか派手な感じでした。

もし暇であればちょっと覗いてみてくださいね☆

ちなみにmiracの属するチームd3sxpは、

中継ルームの斜め後ろの机が割り当てられているので、

もしかしたら中継の間、左後ろの方に映っているかもしれません(笑

いろいろ楽しいイベントもあって、

書きたいことは盛りだくさんなのですが、

卒論を書いてたころから忙しくて、

寝不足が解消できていないので、

今日こそは早めに寝たいと思います。

(あ、卒論無事に提出できました。
卒論書いた人、みんなお疲れ様ー☆)



では、がんばってきますー◎

おまけ：

チームメイトkamingの日記；
http://mixi.jp/view_diary.pl?id=1403484149&owner_id=4694360
http://mixi.jp/view_diary.pl?id=1404302887&owner_id=4694360
http://mixi.jp/view_diary.pl?id=1405122234&owner_id=4694360

コーチoxyさんの日記：
http://mono.kmc.gr.jp/~oxy/d/

ICPC2010公式ページ(videoとかがある)：
http://english.hrbeu.edu.cn/showcolumn.php?columnid=48

ICPC日本予選公式ページ：
http://www.waseda.jp/assoc-icpc2009/jp/

Live中継ページ(コンテスト中のみ放送)：
http://liveacm.hrbeu.edu.cn/

icpc

ICPC、世界大会に行けることになりました☆

大会の行われるハルビンは零下15度らしいですが、

まぁ寒さに負けずに頑張ってきたいと思います◎

ICPC 2009 Tokyo

行ってきました、ICPCアジア地区予選。


結果はチーム別で6番め。日本人チームでは3番めでした。

俺たちより上位にいる日本人が東大チームだけだったので、

(まぁいろいろややこしいルールがあるのだけれど)

もしかすると世界大会に行けるかもしれません。

2週間もしたら世界大会行けるか分かるはず、、

いろいろ頑張ったし行けるといいな、行きたいなw



ちなみに世界大会、来年は中国のハルピンというところであるらしく。

2月に開催なのですが、最高気温が10度、最低気温は20度らしいです。

え、最高気温が最低気温より低いじゃないかって？

いや、最高気温が"氷点下”10度で、最低気温が氷点下20度なのですよ笑"



さてまぁせっかくなので、今年はどんな風に問題を解いたか載せてみます。

問題はこちら。http://www.waseda.jp/assoc-icpc2009/contest/problems.pdf

pdfなので気をつけてくださいねw


開始早々、パソコンがサスペンドになるというハプニングが発生。

どうやら相方がログインボタンと間違って、

サスペンドボタンを押してしまったらしいw

まぁそれは簡単に復帰できたので、

面白いこともあるものだとか思いながら問題を読みにかかりました。。

例年に比べて問題文が長くて、

１つの問題を読むのにかなりの時間がかかりそうでした。

なので問題の図を見ながらパーっと問題を斜め読み。。

例年はA問題が一番簡単で、次がB問題、次にC問題...となっているのですが、

問題の図をみたところではなんかA問題もB問題も簡単ではなさそうで。

とりあえずC問題を頑張って読んでみたところ、

それなりに簡単そうだったので俺がプログラムを書くことになりました。

その間に他の2人が問題を読んでくれていたのですが、

何やらさっそくA問題やB問題に正解したチームが現れたようで。

どうも問題を読み終わった友人に問題文を聞いてみると、

どうも問題を勘違いしていたようで、とても簡単な問題でした。

ICPCは解いた問題数だけではなく、"如何に早く解くか"ってことも

重要視されるので、やや時間のかかりそうなC問題を放置して、

慌ててA問題を解くことにしました。


ちなみにA問題はこんな感じ。

1辺1mの立方体がいくつか積んであります。

南からそれを見ると、こんな感じに見えました。

+-+-+
| | |
+-+-+-+
| | | |
+-+-+-+

また、西から見ると、こんな感じに見えました。

    +-+
    | |
+-+-+-+-+
| | | | |
+-+-+-+-+

さてこのとき、立方体は最低でいくつあるでしょうか。。

ただし、立方体が宙に浮くことはできないものとします。


ちなみにこの場合は、7個の立方体があれば実現できます。分かりますか？w

A問題を提出してから3分ほどして、"正解です"との返事が帰ってきました。

ひとまず1問正解ということで、やる気が出てくるのでありましたw

その後B問題も難しくないことが分かったので、さらさらっと実装。

ちょっとバグったものの、まぁ3分ぐらいでバグが見つかって、これも正解。

相方がD問題を解きたそうにしていたのでパソコンを譲って、

C問題を早く解くにはどう書いたらよいかを考えていました。

その後しばらくして相方がD問題を提出、正解しました。

再びパソコンの前に座り、相方と相談しながらC問題を実装。

再び答えが合わずに焦ったものの、3分か5分ほどで見つかったので提出。正解。


ちなみにD問題が説明しやすいので紹介しておくと、、

"床の上に、100個の白黒の碁石が落ちていて、その座標が与えられます。

この時、床の上に長い棒を置いて、その片側には黒石だけ、

その反対側には白石だけになるようにすることができるでしょうか。"

この問題は人間が見たらほぼ一瞬で答えが分かりますよね。

だって白石と黒石が綺麗に2つに分かれていたらYESで、

白石と黒石がごちゃごちゃ入り乱れていたらNOなのだから。

でもコンピュータには目がないので、こういう問題は得意ではありません。

というわけで人間には簡単だけどコンピュータには難しい問題の1つでしたw


さてこの4問解いた時点でうちのチームは10位ぐらいでした。

うちのチームは簡単なA問題からでなく、C問題から解きはじめてしまったので

タイムロスが生じたのでした。そしてこれは予定より低い順位でした。(涙

去年までの俺たちなら、”負けている”という事実に焦って、

悪循環に陥ってしまうところでしたが、、今年はちょっと心に余裕があったので、

みんなで「落ち着いて解いて最後に逆転を狙おう」と励ましあっていましたw

この時点で2時間が経過。コンテストはあと3時間。。



ちょっと大会が終わってから寝不足ぎみで辛いので、

続きはまた今度書くことにしようと思いますw

国内予選いってきましたー

icpcの国内予選(でも実質は学内予選)に行ってきました。


去年は7位でしたが、今年は4位で突破できました☆

ま引退したチームがあることを考えると、

実質はほとんど変わってないのですが…笑"


問題が全体的に易化したので、いかに早く

プログラムを書くかという勝負になってましたw

結果はこちら。うちのチームはd3sxpというやつですw

http://mirac.jp:8080/icpc-2009domestic/standings.1959.html

solvedが解いた問題数で、トップチームだけが全問正解。

問題数が同じ場合はtime欄(解答時間の積算)で勝敗が決まります。


もうちょっと頑張って最後の問題が解けてたら2位になって、

海外派遣という特権を手にできてたのだけどなぁw


やっぱicpcって楽しいねってことが分かりました、、

11月のアジア地区予選(でも実質は国内予選)に向けて頑張ってきます◎


応援してくださった方がたどうもありがとうございましたー☆




<実際に参加した人向け>

A問題
ターン数が1,000,000までとかなので、
実際にシミュレーションする

B問題
連結の定義がちょっと気持ち悪いけど、
BFS的な何かで数を数える

C問題
うちの解法は：
まず、あるアルファベットを1としたとき、
方程式の左辺と右辺の差がどれぐらい変わるかを調べておく。
次に、アルファベットに数字を割り当てていきながら、
方程式の左辺と右辺の差を修正していく。
すべてのアルファベットに割り当てられたときに差が0ならカウント。

D問題
次行く場所(30)*速さ(30)*直前にいた場所(30)でdijkstra

E問題
GCDが1でないものに枝を張った最大二部マッチング

F問題
線の曲がる連続した3点p,q,rのなす三角形上に
1.点がなければqはいらない
2.点があればそのうち最もqに近い角度のものに線がかかる
をひたすらやるだけ(多分ね)。

ただし1つの釘だけを何回も回って、その後で逆向きに回ることで
なんてことをされると釘の影響があるのかないのかよく分からないので
本来の釘からepsだけ離れた4点(上下左右)に仮想的な釘を考えることで
1つの釘をぐるぐる回るっていうのに対応しましたー。


質問等あればどぞーw



今年のアジア大会予想出場チーム(間違ってたらごめんなさい)

10チームルール
HITORI#　　　　　　　University of Tokyo
_(ry　　　　　　　　 University of Tokyo
Watch.d　　　　　　　University of Aizu
d3sxp　　　　　　　　Kyoto University
HABRush　　　　　　　Tokyo Institute of Technology
40010　　　　　　　　Tokyo Institute of Technology
MAGI System　　　　　University of Tokyo
#35　　　　　　　　　Kyoto University
SINONIS　　　　　　　Tohoku University
Imo = {imos,ao,eee}　Osaka University

20チームルール
swap(day,night);　Waseda University
-W　　　　　　　　University of Aizu
0x3f　　　　　　　Waseda University
HinagikuRhapsody　Kurume National College of Technology
TLEbusters　　　　Suzuka Natioanal College of Technology
auto main =-277;　Osaka Electro-Communication University
y/y　　　　　　　 Tohoku University
Kaeru Mario　　　 Meiji University
__BISCO__　　　　 Toyohashi University of Technology
NERV　　　　　　　Mie University

26チームルール
UNK　　　　　　　 University of Tsukuba
arguments.callee　Ritsumeikan University
(:D)rz　　　　　　Hiroshima University
Kyueue　　　　　　Kyushu University
Spanking Boys　 　The University of Electro-Communications
YUDOFU　　　　　　Tsuyama National College of Technology

ワイルドカードと女性枠は分からないですw

コンテストまとめ

• 5/30 maximum
• 6/ 7 utpc
• 6/13 imos contest
• 6/20 OBOG会(?)
• 6/27 ICFP
• 7/ 3 国内予選

毎週どこかがコンテストを主催してくれてるので、

来月はかなり楽しめそうですw



lingr書けなくなってしまった、、どうしようorz

じんましん止まりましたw

タイトルの件はご心配をお掛けしました。

さて3日連続で問題を解いてるわけですが。

昔解けなかった問題のアルゴリズムを思いつきました、、

どうやらこの方針で解けそうです☆

問題はこちら



さて、国内予選まであと70-3=67日なのですよ、

刻々と時間は過ぎていきますので、、頑張ろう。



研究室の教授が"ICPCやるならこの本を読むといいよ"って言って、

本を10冊も持ってきてくださいました。ありがたいのですが、そんなに読めません;;

すでに音声処理関連で3冊の本と3つの論文をお借りしてるのですが、、

さてどうやったら消化できるのだろうかw



がんばるんば。

じんましんが止まらない

国内予選まであと70日！

高校生

いやー、、高校生でもすごい人はすごいものです。

今高校2年生なのかな？

今ICPC(これは大学生向け)やってる人たちが、

"あいつが大学生になったらICPCがやばい"(=それだけ強い)

って言ってる人がいるのですが。

さっき数人で(ネットで)さっぱり解けんよーって言ってた問題を、

あ、思いついたかも、、とか言って解いてしまいました。。

しかもAcceptされてるし、Acceptされた111人中2位(実行時間)2だし。。

ソースを読んでみて、

"ここは怪しいんじゃないか？"とか思ったところも、

10分ぐらいかけてよーく考えてみたら合ってるし。。

あー、、やっぱすごい人ってのはいるものです。。

俺も頑張ろうっとw

さーて

来週のサザエさんはー

mirac会津若松へいく
miracアジア地区大会
miracなぜか夜行列車

の３本です。

じゃん、けん、ぽん(ぱー)。




さーていよいよ明後日の夜からICPCアジア地区予選会津大会に行ってきます。

なんか新潟経由で行くと夜行列車とかSLとかに乗れるみたいなので、

そっちのルートで行ってきます、、かなり旅行気分w

んでー、、大会の方はというと、東大に勝てる気は正直しないけど、、

それ以外には勝ってきて国内2位を目指したいな。

てか世界大会行きたいー、、国内2位なら運次第で行けるかもしれんし。

去年の12月からこれのために1年やってきたようなもんだから、

ほんっっと頑張ってこようと思います。。




あ、なんかwebで放映されるそうです。
http://sparth.u-aizu.ac.jp/icpc2008/webcam.php
わくわくw

icpc合宿

icpc合宿３日目が終わってちょっと一息w

もうこんなにプログラム漬けなのはすごくて〜。

プログラミング終わってからの雑談とかもすごくてーw

ときどき激しく息抜きするのもすごくてー笑”

あと１日なんでとにかく頑張る！

icpc

正式に通過者が発表されたみたい。
http://sparth.u-aizu.ac.jp/icpc2008/d_result.php

大学別に色分けしたみたいなんだけど、
なんか色の数が多すぎてよくわからない事態になってる笑

ICPC Japan Domestic

タイトルの意味はICPC日本国内予選ってことで。

ついに今日 ICPC:International College Programming Contestの

国内予選がありました。結果は…まぁ日記の続きを読んでください。

ちょと他のSNS…っていうかまぁ日本一巨大なアレに書いてたのを転載。

一応ネットで公開して変なことは書いてないと思いますが何かあったら教えてね。

んで今回は新しくURL教えた人もいるので結構ワクワクw

質問やらなんやらコメント大歓迎なんでどーぞよろしく☆

ではここから日記開始ーw


---


珍しくハイテンションです。理由はこちら。

http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_standings_en.php

ちなみにうちのチーム名はd3sxpです。

なんと7位。アジア地区予選(という名の実質国内予選)にいけるじゃないですか！

問題はこちら。今回は日本語なのでいつもよりは読みやすいはず。

http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_top_en.php
(左側のA B C D E Fってのが問題番号で、jaっての押すと日本語で出てきます)


難易度的にはー、、

A：日本語を読み間違えなければ簡単。難易度★
B：問題がとにかくややこしい。ちゃんと問題文を整理できたら、
単に素因数分解したらいい問題だと言うことが分かるはず。難易度★★
C：P,Q,Rの組み合わせが27通りしかないので全部の場合を試してみる。
アルゴリズム思いつけば後は頑張って実装するべし。難易度★★★
D：メモ化というかDPというか。グラフ理論でもとけるんじゃないだろうか。
こういう問題に"十分慣れてていれば"そんなに苦労はしない。難易度★★★
E：幾何系のライブラリが十分に用意されてるかどうか。難易度★★★★
F：俺はアルゴリズム思いつきませんでした。難易度★★★★★

まぁ国内予選らしくA問題から解いていけばいい問題セットでしたね。


ではー、、調子のって我がd3sxpがどういう風に解いたかをダイジェストw
あー、、ダイジェストなんていいから解法教えろって人は下の方まで飛ばしてねw

16:15 開始15分前。この頃が一番心臓バクバク。
演習で部屋を使ってた人たちが帰っていく。
みんなに応援を受けて頑張る気になる。

16:25 開始5分前。用意万端、チームで集合。さて頑張るか。

16:30 国内予選開始。予選参加者みんなが一斉に問題を見ようとして、
サーバーに負荷がかかってなかなか問題が見れない。我慢我慢。

16:32 まだ見れない。我慢我慢。
16:34 まだ見れない。そんなバカな!刻々と時間は過ぎて行く…汗
16:35 なんか前の机のチームが見れたらしい。うちはまだ。我慢…我慢…。

16:36 問題やっと見れたー!!! ということで俺たちの国内予選やっと開始。

コンテスト中は時計見てる余裕なんてなかったので以下時間は省略。
まずA問題に目を通す。太郎くんと花子さんが何枚かずつカードを持っていて、
そのうち何枚かを交換するらしい。で、交換した結果、太郎くんの持ってる
カードの合計と、花子さんが持ってるカードの合計を、等しくするような
交換の方法はありますか？という問題。

太郎くんも花子さんも最大100枚のカード持ってるのに、
そんなのめちゃくちゃ難しいやん！と思ってA問題を無視。
(後に実は誤読だったことが判明…まぁ詳しくは後で。)

次はB問題を見る。問題がややこしい、、とりあえず放置。
続いてC問題、D問題を見る。解けそうな気もするけどややこしいなぁ…
さらにE問題、F問題を見る。もはや解けそうな気すらしない。

んー、、簡単に解けそうな問題が1問もない。。正直焦る。
国内予選はAが一番簡単なはず、と思ってもう1回Aに戻る。

Aの問題を再読。さっきは太郎くんと花子さんが"何枚か"カードを交換する、
と読んだけど、実は"1枚だけ"交換する、なんじゃない？と思い出す。
それだったら太郎くんが100枚、花子さんが100枚持ってても
交換する方法は100*100の1万通り。余裕じゃん！って思ってプログラミング。
さらさらーと書いて(といっても実際書いてるのは別のメンバーだけど)
submit(提出)。Correct Answerってことで1問正解☆

あとから聞いたんだけどこの問題は日本語がまぎらわしくて、
"1枚だけ交換する"とも、"何枚か交換する"とも読めたんだとか。
英語の問題には"one card"って書いてあるので"1枚だけ"が正解だったらしい。

で、A問題が解けたのでB問題へ。
7で割った余りが1か6になる数、つまり1,6,8,13,15,20,22,28…ってのを
月曜土曜数と名付けるらしい。なんだそれは(笑)　で、ある月曜土曜数nを
とってきてその約数を考えたときに、その約数のなかに1とn以外の
月曜土曜数が含まれていない数を月曜土曜素数と名付けるらしい。なんだそれは(笑)
で、別のある数Xが与えられた時に、そのXを割り切ることのできる月曜土曜約数を
全て挙げなさい、という問題。まぁ1は除くとかややこしいことは置いておいて。

実際の問題はあとひとひねりぐらいヤヤコシイ文章が入ってて、
問題解こうと焦ってるこっちの頭の中は完全にカオス。
ちゃんと問題を理解したら実はただの素因数分解問題だということに気づき、
submit。 Correct Answerだと返事がかえってきて２問目正解。
実はこのころ東大のトップチームはすでに3問目を終えていたらしい。早っw

続いてC問題へ。
コンピュータの中では0と1の信号で処理されるって話をよく聞くと思うけど、
それは論理回路っていって、ANDとかORとかそういうもので構成されているのです。
で今回はそれを0と1と2の3種類にして、ANDとかORとかもちょっとややこしく
してみたけど君たちにそれが理解できるかな？みたいな問題。

見て数秒でアルゴリズム思いついたのでコーダーのカマエ君に伝える。
5秒ぐらいで適当に説明。通じなかった。10秒ぐらいかけてちゃんと説明。
んー、、伝わらないな。30秒ぐらいかけてゆっくり説明。あ、通じた(笑
俺は説明能力に乏しいようで毎回こんな無駄会話が繰り返されてますw
あ、ちなみにコーダーってのは実際にプログラムを書く人のことです。
この大会は3人チームなんだけどパソコンが1台しか与えられないのよね。
実際にプログラムを書くのはカマエが一番早いので、俺はアルゴリズム(解法)
を考えたり、コーダーのミスを指摘したりとかそんな役回りw

で、カマエがプログラムをカリカリ書いてくれる。カリカリ。カリカリ。
できたので提出してみる。Wrong Answerが返ってきた。あれ？？ 汗”
アルゴリズム間違ってないはずだしなぁ…とか思いながら2人でチェック。
問題を見てない人には分からないと思いますが-(Q*P)みたいに括弧の前に
マイナス符号がつく可能性があることをすっかり忘れてました。ごめん!!
で、それをカリカリーと直してsubmit。今度はCorrect Answerをもらって。
という訳で3問正解になりました。Wrong Answerのときは本当に焦ったけどw

で、続いてD問題をやりはじめる。西田くんっていうもう一人の子が、
事前に問題を読んでくれてて、一番解きやすいのを俺とカマエに教えてくれます。
いつもどおり問題の説明を受けて3人でちょっと考えてー…
PFS(priority fast search)というよくある方法+メモ化で解けることが判明。
カマエとプログラムを書く作業に戻ります。

D問題は、正方形のタイルがw*h個並んでいて、、ロボットがその中を動いて
左上から右下まで行きたい、という問題。ただ各タイルには"まっすぐすすめ"とか
"右へ曲がれ"とか書いてあって、その通り進むと右下のタイルまでいけない
場合があるのです。タイルに書いてある内容を無視するとその分罰金を
支払わなくてはいけないのだけど、とにかく右下のタイルに進みたい、と。
じゃぁ罰金の額を最小にするにはどういう風に右下まで行ったらいいですか？
という問題。んー、、俺の説明能力でこれちゃんと説明できてるのだろうか。
時間がある人はぜひ問題見てみてください、、上にも書いたけど
http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_top_en.php
の左の方にあるAとかBとか書いてある部分のjaをクリックすると見れますので。

で、まぁカマエとここはこうした方がいいんじゃないかーとか言いながら
調子よく書いてたのだけど、ここで問題が発生。1回罰金を払ったタイルを
もう一回通るときに、再度罰金を払う必要はないんじゃないか？という話が。
そうなると"罰金を払ったタイル"を覚えておかないといけなくなるから、
今までやってた方法では解けなくなってしまう。うー、、ここまで書いたのに！！

カマエと2人で悩むもやっぱりこの方法では解けないという結論に。
落ち込みながらとりあえずE問題にすすむ。

E問題は大玉ころがしをする問題。大玉転がしをしたいのだけど、
回りにいっぱい障害物があって、あまり大きな大玉だと障害物にぶつかってしまう。
けど見栄えとか考えるとできる限り大きな大玉を使いたい。
じゃぁ障害物一覧から大玉の最大サイズを計算してください、という問題。

幾何問題っていうんだけど、こういう平面上を何かが動く見たいな問題は
数式がいっぱい出てきて大変なのです。で、今まで全然解けていなかったのだけど、
今回は事前に数式集みたいなのをネットでみつけてたので、用意してました。
するとすると、その数式集を駆使すれば解けることが判明。
てことでカマエはひたすら数式集をコピーし始め、
俺と西田君は数式集にない式を自分で作り出す作業に入る。

で、きっかけはなんだったか忘れたけど、西田くんが突然D問題の解法について
俺にしゃべり始めてきた。俺は「あー、、その方法は無理だったよ、、だって
罰金を払ったタイルを覚えてなくちゃいけないからさ」とか返事をする。
すると西田くん、「え？何で？」ってreply。俺「だって1回罰金払ったタイルって
次にもう1回通るときは罰金払わなくていいじゃん」とか応答。
西田くん「え？もう1回通るときでも罰金払わないといけないよー？？」
俺硬直。「え？なんですと？ならさっきまで書いてた解法で解けるじゃん！！」

ということでカマエをたたき起こして(笑)D問題に戻る。9割がた完成してたので
あとはちょっと手を加えるのみ。提出してみる。Correct Answer !!

実は俺もカマエも問題ほとんど読んでないのですよ。それは悪いことではなくて、
西田くんが先に問題を読んで、上手くまとめてくれたのを聞いてるわけです。
でもそうすると今回の様に、「問題を自分で読んだ西田くん」と、
「問題を西田くんから聞いた俺とカマエ」で解釈が変わってくることが時々。
実際にプログラム買いてるのは俺とカマエであることが多いので、
間違ってプログラムを書きだすと大変な目にあってしまうことがあるわけで。
その辺今後の課題かな。2人以上で問題を読むとかしてもいいかもしれない。。
アジア大会とかで英語の問題になると読み間違えも起こりうるしねー。

って感じで4問正解したのでこれは予選突破できるのではないかとか思いつつ
E問題の大玉転がしに戻る。ちょっと気持ちにも余裕が出てきて、時間を見てみると
1時間45分経過してのあと1時間15分とかだった気がする。
数式集からコピーしたのは、高校数学頻出の「点と直線の距離」にはじまり、
「点と線分の距離」やら「線分と線分の交差判定」やら、
さらには「ベクトルの内積」やら「ベクトルの外積」やらとにかくいっぱいw
あと足りない分は自分たちで式を作って、ごりごりごりごり書きました。
各問題にはテスト用入力とその模範解答が用意されてたので、まずはそのチェック。
初めはなかなか答えが会わなかったのだけど、「大玉を転がす直線上に
障害物があったときは全然転がせないので0を返す」とか、
「ゴールのすぐ近くに障害物があるとゴールまで大玉を転がせない可能性がある」
とかいろいろやると模範解答どおりの答えが出るようになりました。
この時点で残り20分ちょっと。この問題に55分もかかったんだなぁ(汗+笑)
で、提出してみるとCorrect Answer！！なんと5問正解！！
始めて幾何の問題を時間内にとけてみんな感動。公式集の力はほんとすごい。。
そしてチーム全員で公式集をネット公開してくれている人に感謝。
ちなみにこんなページです。 http://nya3.jp/libicpc/
(プログラミングの公式集のことをライブラリと言ったりします)

で、あと20分。もしや結構上位なんじゃないかと思ってランキングを見てみると
その時点で暫定6位。おおっ、、去年16位だったのに比べればかなりの快挙w

(ちなみに去年の結果はこちら)
http://www.logos.ic.i.u-tokyo.ac.jp/icpc2007/jp/domestic/result.html


最後F問題は時間がかかるアルゴリズムしか思いつかず、、
結局ラスト20分ぐらいを無駄にはしてしまったけどよく頑張ったと思う。
その間にどっかのチームに抜かれて7位にはなってしまったけど、、
目標5位とか(無理だろうなとか思いながら)言ってたのに比べれば
本当すごい結果だと思うわ、、まぁトップ4は東大独占なわけだけど(汗)

アジア地区予選の会津地区は10月末、会津大学で行われるそうです。
(アジア地区予選はペキン地区とかマカオ地区とか10ヶ所ぐらいでありますw)
んー、、ただで会津まで旅行できるなんて素晴らしい、、頑張るよまぢで！

というわけでダイジェストは終了ー、、長いお付き合いありがとうございます。

1時間半も日記書いたの初めてだわ、、wcってコマンドで文字数測定すると
どうやら7000文字以上打ったらしい、、90分で7000文字ならそれなりじゃない？笑





で、実際に参加した人とかアルゴリズムに興味がある人向けの解法解説。

まぁあくまでうちのチームが解いた方法なので最適解かは知りませんが。。

まずA問題。
太郎君のカードを入力する際に、その合計TAROsumを計算。
花子さんの入力の際にもその合計HANAKOsumを計算。
太郎くんのカード最大100個と花子さんのカード最大100個の組み合わせは
100＊100＝10000しかないのでそのすべてに対して、
交換するとTAROsumとHANAKOsumがどう変わるかを計算。
で、この2つがイコールになるときに値を出力、なければ-1を返す。
まぁこれぐらいは(問題の読み間違えさえなければ)解けるはず。
最後まで問題の読みにくさにハマってしまったチームの人はどんまいです。

次にB問題。
まず300000以下の全ての月曜土曜素数を求めます。
方法は簡単。月曜土曜数を小さな数から順に(1,6,8,13,15…)生成して、
それより小さな月曜土曜素数全てで割ってみます(1を除く)。
どれかで割り切れたら月曜土曜素数じゃないし、それ以外は月曜土曜素数。
そうして月曜土曜素数をすべて求めたら、入力を1つずつよんで、
１つ１つ月曜土曜素数で割れるかをチェック。割れたら出力したらOK。
問題がややこしいのでどうしてこうなるのかはよく考えてみてね。
ヒントは問題文中の「月曜土曜数aが月曜土曜数bの月曜土曜約数であるためには、
aがbの普通の意味の約数であれば必要十分であると，簡単に証明できる。」
っていう一文。まぁ頑張って考えてみてください。

次にC問題。
カッコで計算の順序が定められてる問題は、スタックを使うと楽です。
まずP,Q,Rを0,0,0として次の操作をします。次に0.0.1として同じことをして、
これを計27回、最後に1,1,1として次の操作をして、結果が2になった回数が答え。
PとかQとか考えるの面倒だったので以下のように入力データを直接改竄。
string inputstr=(入力)
for(int p=0;p<2;p++){
for(int q=0;q<2;q++){
for(int r=0;r<2;r++){
string tmp=inputstr;
replace(tmp.begin(),tmp.end(),"P",(char)p+'0');
replace(tmp.begin(),tmp.end(),"Q",(char)q+'0');
replace(tmp.begin(),tmp.end(),"R",(char)r+'0');

int ret=何か処理();
if(ret==2)answer++;
}}}
まぁこんな感じでPとかQとかを初めに隠蔽してしまうと後が楽になります。
で、準備としてminus、number、opっていう3つのスタックを用意して、
変数numOfNotを0で初期化しとく。ちなみにnumOfNotは直前のnot記号の数ね。
後は前から1文字ずつよんでいくたびに、その文字が
'0'か'1'か'2'だったら、変数numOfNotをチェックして、
偶数なら0か1か2をそのまま、奇数ならそれをnotした値をnumberにpush。
'('だったら変数numOfNotをminusにpush。
これは'('の前にあったnotの数を表す。
'+'か'*'だったらそれをopにpush。
')'だったらnumberから2つpopした値を、
opからpopした演算子('+'か'*')で処理して、
さらにそれをminusからpopした値の数だけnotした値をnumberにpush。
'-'だったら変数numOfNotを1インクリメント。そうでなかったら0にする。
ということをします。ちょとややこしいので注意が必要ですが。
まぁnot演算子を無視して言うと、閉じ括弧がくるまで今の状態をひたすらpush。
閉じ括弧が来たときに計算するべき値は、直前とその前に決まった値(number)で、
どういう演算をするべきかというと直前の演算子(op)だから、という感じかな。
なんかどう説明したらいいのか分からんのでコメントなり何なりで質問どうぞw

んー、、Cの説明が上手くできなかったのだけど気にせずDの解説へ。
この問題は各タイルについて、どの方向から来たかが分かれば
次にどの方向に行くのにどれだけコストがかかるか、が分かります。
例えば左から来たときに、そのタイルが「直進しろ」タイルであったとして、
そのまま右に進むには罰金は0。向きを変えて下に進むには右折する必要があるので
右折分の罰金を払えばいいことがわかります。だから、
「今のタイルのx座標」「今のタイルのy座標」「来た方向」の３つを記憶して、
「これまでにかかったコスト」の小さい順のものからどんどん次のタイルに進めて
いってやります。これは「これまでにかかったコスト」順のPFSに相当します。
で、あと重要なのが、「一旦(X,Y)のタイルに向きZ(例えば左)から来たら、
以降同じ(X,Y)のタイルに同じ向きZから来ることはない」ということ。
だってコスト順にPFSしてるのだから、以前ここに来たということはその時は
今のコストと同じか、それより小さいコストできたはず。わざわざ大きなコストで
同じことする必要ないよねー、って感じいうことで。
これを使うと状態数が(Xのサイズ)*(Yのサイズ)*(向き)となって、
つまり最大で30*30*4、計算するとたった3600通りで表せます。
だいたい今のコンピュータは(プログラムにもよるけど)1秒で1000万ぐらいの状態を
処理できるので3600通りなんてほんと一瞬なわけで。そんな感じで実装しました。

Eはごりごり頑張って、という感じだなぁ、、サンプル入力が親切なので、
サンプル入力で通らないものをチェックしていけば条件を忘れることはないはず。
あとは幾何ライブラリを駆使することとバグを埋めないようにがんばることかな。

Fは去年京大から世界大会に行った先輩に教えてもらったのだけど
今ひとつ理解できてないのでまた理解できて暇だったらそのうち。



あー、、日記を2時間15分も書いてたようです。
普段は20分ぐらい書いたら飽きるんだから、
アジア大会行けるのがよほどしかったんだろうなぁ＞俺

まぁ他の大学で国内予選出た人とかにも見てもらえたらいいなーと思いつつ
この1万1000文字にもおよぶ日記を終わりにしたいと思います。

てかmixi1万1000文字も書けるのか!?


最後に。いつも書いてますがこの長ったらしい文章を読んでくれて、、
なんかいろいろ応援してくれて、、ほんとありがとうっ

お詫び。

昨日ぐらいの日記に今週の金曜日が国内予選って書きましたが、、

この週末でなくて来週の週末の間違いでした(汗

この土日は新歓合宿ということで串本に潜りに行ってきます、、

どうやら天気がよくないとかなんとかでちょと心配だなぁ・・・


久々にprojectEulerを1問解きました。
http://projecteuler.net/index.php?section=problems&id=98

RACEとかCAREみたいな文字列が数千個与えられて、

その中でアナグラム(文字の入れ替えで別の単語になる)ものを

探してくるのが第一段階。さらにその各文字に0-9の数字を当てはめていく。

例えば上の例だとCに1、Aに2、Rに9、Eに6をあてはめると、

CARE=1296、RACE=9216となる。

んで実はこの2つはどちらも平方数(ある自然数の2乗した数)に

なっているんだけど(1296=36*36, 9216=96*96)、

そういうものの中で一番大きい数(この辺の詳細な定義は問題文をw)を

出してくださいとか言う問題。第2段階がちょっとてこずったけど、、

Accept(正解)もらえたときは結構すっきりしました☆



で、、第一段階のアナグラムぐらいだったら国内予選にも出そうなので、

ちょと勉強になるかなーって感じで書いてみる。といっても一瞬で終わるけど。

ある文字列A、Bが与えられたときに、それらがアナグラムか判定する

アルゴリズム(ピタゴラスイッチではなくw)を考えてくださいw

とりあえず単純で記述量が短いものを考えてみてね。答えはちょっと下に。
















正解は、文字列Aと文字列Bをソートして、その2つを直接比較する、というもの。

C++だったら

string strA,strB;
cin>>strA>>strB;
sort(strA.begin(),strA.end());
sort(strB.begin(),strB.end());
if(strA==strB)cout<<"アナグラムじゃん!"<<endl;

とまぁ上2行の入力部分を除くと3行で判定できちゃうという。

覚えておいて損はないのではないでしょうか？？

ちなみに計算量についていうと、

文字列A、Bの長さをnとしたときに、

ソートはnlognでできるので、O(nlogn)の時間で判定できます。


じゃぁ、O(n)ではできないのか考えてみましょう。

(と言うかほんとに今考えたw) O(n)でも可能ですね。

プログラムは長くなりますがソートしなければいいのです。


例えば文字列A、Bには小文字しか入らないというのであれば、

文字列に含まれる各アルファベットの数を数えたら良いですね。

コードはこちら。コンパイルしてないから間違ってるかもだけどw

string strA,strB;
cin>>strA>>strB;
int cntA[256],cntB[256];
for(int i=0;i<strA.length();i++)cntA[ strA[i] ]++;
for(int i=0;i<strB.length();i++)cntB[ strB[i] ]++;
int same=1;
for(int i=0;i<256;i++){
    if(cntA[i]!=cntB[i]){
       same=0;
       break;
    }
}
if(same)cout<<"アナグラムじゃん!"<<endl;

まぁこんな感じになると思います。

計算量はO(strA,strBの長さ+アルファベット数)になるので、

文字列の長さが短くてアルファベット数が多いときは、

ソートした方が事実上早くなるなんてこともありえます。


んー、、たまにはタメになるコンテンツも書かないとな、

と思って書いてみましたがどうでしょうかね、、

感想があったら(というかなくても)何かコメントよろしく!(笑



あ、、上では省略してしまいましたが、

strAとstrBの長さが違うときはアナグラムにはなりえません。

その場合はすぐにbreakするなり何なりして、処理を減らしましょう◎

Branch and Bound

今日は5月31日。

亡くなったお婆ちゃんの誕生日だったはず。

そして一番歳の近い従兄弟が結婚式を挙げたとか。

まぁ一番歳が近いといっても9歳ぐらい離れていたと思うけどw

お幸せに☆


今日は東大主催のコンテストに参加させてもらってました。

問題(いつまで残ってるのか分からんけど) http://www.utpc.jp/mjudge/problem_list.cgi

結果 http://www.utpc.jp/mjudge/standings.cgi?cid=0

運良く10位には入ったけど、、あと一問いきたかったなぁ…w



久々今日のラーメンズ。

ラーメンズ　ヨンタウロン　春夏秋冬　あいうえお
http://www.youtube.com/watch?v=PtEuGsGznVA

最初の方はちょっと暇かもしれんけど、、

まぁ伏線張りまくって最後に楽しませてくれる感じのですw

よし。

ここに今宣言します。

8月末までに200問のプログラミング問題を解きます！！

いや、、単なる気まぐれなんですがw

単純に計算して…13+30+31+31=104日残ってるので、、

1日2問。学校とかあると相当きつそう。

まぁ目標は達成するためにあると思うし！



今日のラーメンズ：風と桶に関するいくつかの考察
http://www.youtube.com/watch?v=VlsYNvzTh7w&feature=related