読者です 読者をやめる 読者になる 読者になる

JOI合宿 - 1日目 , 2日目

JOI プログラミングコンテスト

おわった。 西会場での参加でした。久留米から来たnikollsonさんと、灘の4人と一緒の会場。6人少ない。

どうせ僕は今年は代表になれるような選手ではないので、もう点数とかどうでもいいです。なので晒しちゃいます。とりあえず合宿、残りの問題解けるようにがんばりたいです。

day1

前日お昼寝すぎて夜寝れない上に、薬とかちょっと飲んでたのでそろそろ少し眠たかった。(14時からだったので)

1.Banner

問題読む

→むむ。2色固定したらいいのかな?(まちがい)

→分からない。

→とりあえずお腹痛かったのでトイレに行ったらO(H・W^2)解法思いついたので帰ってきて実装しました。

2.Dragon

問題読む。M理事長とんでもない・・・。「いや、会場変えろよ」

→二分探索やset,mapを使いまくって実装を試みたけど、バグりまくって死亡。

→結局諦めて20%を取りにいったけど10%しか取れずorz

3.Joitter

Dragonやってる時にちら見する。

→1の条件の人が居る時は云々ってのだけは分かった。

→でもそれ以外の場合が分からない。Dragonの実装に特に力を入れることにしよう。

→結果としてどっちも死んだ。

全てのケースに対しての普遍的な解法が思いつかないので諦めるなど、場合分けとか思いつかなかった。

day1 Result

残念点数。Joitterをもっとじっくり考えれば良かったのかもしれないけど、「その時はみんな実装ゲーは手をつけていない!だからdragonの実装ゲーと戦うのが最善策なんだ」とか考えていたりしていた。結局解けませんでしたが。

100 / 10 / 0

day2

前の日結構寝たはずなのに朝6時起きはいつもしていないのでやはり眠たかった。

もう少し遅い時間からやってくれると嬉しい・・・。

1.数当てゲーム

問題読む。対話型か・・・。

→最大ケースは、N=100 , L=700

→一つの数字あたり7回使えるってことは、ceil(log2(100)) = 7。なるほど二分探索か。

→0が返ってくるような数列(以降下地と呼ぶ)を一つ見つければ、それ使って1つずつ位置決定出来るのか。

→たしかにそうなんだけど、下地見つけるの意外に大変だぞ。

→1つ決定してしまえばいいのかもしれないけど、100回使うのはきつい。

→そこらへんだけ嘘っぽく書こう。かけた。

→8件正解1件RE。まあいいやと放置して他の問題を解く。(恐らくassertのもの)

→残り20分のところで再び着手し、もっと嘘っぽい下地をつくろうとか思った。

→でも未確定領域1回毎に減っていくんだから、log2(100) + log2(99) + ... + log2(1)って、100回実は余るんじゃないか?でも概算だし、実装しなきゃいけないのは大変。

→嘘解法のまま9件正解。

→そのままでいいや・・・。

2.キーカード

2^1000000の鍵を受け取るって地球がヤバイ。いや宇宙がヤバイ。問2の問題設定はday1,2共にぶっとんでいると思いながら着手。

→ゆっくりペースでかなり考える。でも頭痛くなる。組み合わせ数学本当に苦手。

→N=10いけるんじゃね。

→DP思いつかない。だめでした。

→数学無理。

なぜか「みんな数学得意だから解けているだろう」という焦りだけ生じた問題。

3.しりとり

簡単そうに魅せる問題。実際のところ全く簡単ではない。制約がなんでその値設定なのか理解できないくらいに解法が思いつかなかった。

→トポロジカルソートとかするのかと思ったけど、なんとなくそんな気がしただけであてはめてみたら上手く行かず、迷走した末に諦め。

day2 Result

なぜか問1が満点で、すごい罪悪感に襲われる。これはSRM500の時と同じ気持ち。あれはギリギリ落ちたけど。

西会場だと20%ケースが取れなかった人が多いみたい。

100 / 0 / 0

げんざい

210/600...JOI合宿本当に難しいし、来年もし来れたとして解けるようになっている気がしません。

4時間長いようで短くて長いです。解法思いつかないと1問に4時間とかゆったりかけてしまいます。本当に眠ってしまいそうです。

day3から5時間ですが、恐らく競技中に寝ます(まあそんなことがないように善処するが)