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文字も書けるのか!?


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