お久しぶりです。ブログ書く習慣を忘れて７～８ヶ月くらい経ってました。ツイッターでは元気にしてます。競技に力を注ぐ余裕が去年よりも無くなっていたというのも要因だと思いますが、国内予選の報告をしようと思います。
チーム「Operasan」(0perasanではない)として、@tacosufestivalと@drafearと参加していました。
まず結果から書くと、326チーム中10位でした。Bでクソハマりしてた割には好成績だと思います。
コンテスト4時間前くらい(お昼休み)
- コーチである教員の研究室をお借りして大会に参加することになったので、セッティングのためお邪魔する。
- セッティングが長引いてしまい、皆勤が掛かっているdrafearには教室に戻ってもらい、僕たちは30分くらい遅刻して何食わぬ顔で授業に参加する(クズ学生)。
書いている時間は適当です。ファイルが消失したので感覚で。
コンテスト開始前(30分前くらい)
- 物理の授業が終わるのが本来4時25分で、それでは困る。
- なので、応用物理教員に大会あるんで4時くらいに抜け出していいですかというお願いをしたら、それまでに終わるようにすると言ってくれて、それはよかった。
- でも、出された課題がやや計算ハードで、drafear君の助けを借りながら式変形がんばる→結局4時25分くらいに研究室に行くことに（計らいの意味なかった）。
[0:00]コンテスト開始 ＆ A読む
- A問題を読んでいる間に全問題を印刷してもらい、tacosuとdrafearに後の問題を読んでもらう方針。
- Aは「横長長方形についての比較ルールが与えられるので、与えられた横長長方形よりも比較したとき大きく、かつその中で最も小さいものを求めよ。1≦縦幅＜横幅≦100」という問題。
[0:03] A暫定書き上げ
- 適当に比較演算子を定義し、書くがサンプルが1ケース目すら一致しない。
- んん～？？？色々弄るが一致しない
[0:05] Aサンプル一致
- あっ横長（察し）
- サンプル一致した。一致しているかチームメイトに確認し、提出準備。
- 提出方式が相変わらず面倒くさい。2回目の提出で回答ファイル間違えたら痛いから、めっちゃ慎重になる。
[0:07] A Accepted ＆ B読む
- ヨッシャ！順位表なんか見てもどうしようもないということで、間髪入れずに次の問題。(実はこの時点で3位だったらしい。）
- drafear君が読解できていたので、説明してもらう。「ICPCの簡単版の順位シミュレーション」
- 普通のコンテストと同じ感じですかと言ったら「多分そう」と言っていたのでとりあえず書く。「ACした問題に再提出することはあるか？」とか細かいところを口頭で確認しながらコーディング。
- すんなりサンプル一致したので、提出。
[0:15] B WA
- ファ！？オオン...
- えっ何が悪いの・・・あっ初期化バグってる。ただdiff取ると原因ではないらしい。
- 20分近くめっちゃ悩む。これまさか予選落ちでは・・・ってなる。
- あまりにも原因が分からないのでdrafear君と議論しながら色々弄っていて、サンプルを見ると0が正解で、"それ以外の場合不正解"と書いている！！
- コードで、「1なら不正解、それ以外なら正解」としていた。なぜこれでサンプル通るんだ・・・。
[0:35] B Accepted(1WA) ＆ C読む
- やったぜハイタッチ（失敗）。まだ順位表見ない。
- Cをtacosufestivalが読んでいたので問題概要を教えてもらう。分かりやすかったので、すぐに理解できた。
- 「過半数系選挙シミュレーション」、構文解析にとって悪質なデータは無い。
- とりあえず、木構造に直すべきだと思ったのでそうする。
- この形式はBNFだと個人的にやりづらいので、構文解析思いついた感じで再帰書く。少し手間取り10分くらい掛かる。
- あとは、とりあえずＤＰするか～ということでＤＰをしようとして、実装が複雑になりかけていたり、貪欲うまくいくんかほんまかとか考えてしまったりして泥沼。冷静にサンプル眺めて考えてみるとＤＰなんて必要なくて、貪欲するだけだった。慌てるなヤバイヤバイ。
- DとEとFの議論が進んでいるのを端から聞きながら、しどろもどろしているのを申し訳なく思う。
- サンプルが一致。サンプル優しい。
[1:05] C Accepted ＆ D読む
- よっしゃあ！ハイタッチ（失敗）
- 順位表見る。あれ、意外に順位高い。20位～24位くらいだっけそんくらいにいた。この調子なら通るなあと思う。
- drafear君がDを読んでくれていたので教えてもらう。フムフム、死ぬほど嫌いな渦巻きだ。
- 「1を中心として、半時計周り渦巻き上にN(最大10^6)までの数を書き入れた盤面上を考える。盤面上のとある点から始めて、ある点からはその左下・真下・右下の3マスのうちいずれかに移動できる。道中で辿る素数を最大化する経路を見つけ、素数を最大化する経路が複数あるなら、最後にたどり着く素数が最大であるような経路を見つけろ」
- ぼく「あれ、(10^6)^2ってでかいしDP出来る気しないんだけど？（勘違い）」→drafear「いや横10^3*縦10^3程度だから・・・（即答）」→ぼく「おっそうだな」
- たしかテストケースも10^6個だと思っていてバカだった。
- うゥーンこれは・・・。こういうのたまに出るし、効率的にグリッドに配置する方法とか絶対ある気がするが、とりあえず自分の実装力を信じ、ぐるぐる渦巻き書く。
- やっぱり少しバグる。係数弄って辻褄合わせる。盤面構築は出来た
- エラトステネスが合っているか少し自信が無くなるので、チームメイトに確認を取る。(ライブラリ使えよ・・・)
- とりあえず最大個数を見つけるメモ化再帰を書く。
- 経路復元はやっぱりもう一度メモ化再帰するのが賢いと思ったので、最大を達成できるような辺だけを辿るようにした上で、末尾素数の最大を得るメモ化再帰を書いた。いろいろ誤魔化した。
- サンプルが一致。
- 配列をboard[1000][1000]でギリギリで取っていたので、配列外参照してないか調べたら、実はやっぱりしていて、それは困るので修正。提出。
[1:46] D Accepted ＆ F読む
- キマシ！ハイタッチ（失敗）
- 順位表見たらちょっと順位上がってる。えっっ0perasan(偽者)全完してるんですがそれは・・・ってなる。
- Eの考察は一通り終わっていたらしいが、2人にFは簡単という主張をされる。O(10!)計算できるならチョロいというお話もされる。全探索だ～と。
- ほんまか？とりあえずFの問題文＋彼が考えた解法を聞く。頭が悪いのでよく分からない。
- 頭悪いので、サンプルで例示してもらう。理解する。しかし、文字列が増えることがないという主張を何度もされるのに理解できていなかった（ひどい）。
- 「環状文字列A,Bと、いくつかのパターン(ある文字列をある"文字"にする)がある。それぞれA,Bにパターンを複数回適用して一致させたい。一致できるときの最大文字数はいくつか」
- とりあえず書こうとする。
- 頭が悪いなりに直感的に探索の改善は泥沼るという感じがしたので、Eをしたくなる。Eはそんなに難しくないはずと言われる。
[2:05] Eを読む
- とりあえずtacosufestivalにFの入力部分を書いてもらいつつ、Eの問題文をdrafearに説明してもらう。
- 「杭が1～10個くらいある、各杭からはそれぞれロープが伸びていて、それぞれのロープの端を1つの風船に結びつけたとき、風船は最大どれくらいまでの高さに到達するか」
- 重心を見れば云々とか怪しいことを主張していたが、怪しいなあと思いつつ、よく分からないのでとりあえずdrafearに考えてる解法を書いてもらうことにする。その際に「ライブラリとか写したほうがいいですか。」と言われたので、ε,∞,πとか、点の定義とか直線の定義とか円の定義とかだけ写してもらう。
- 写してもらっている間にtacosufestivalと議論する。z=0のとき、風船の可動範囲がx-y平面で杭がつくる円の共通部分になるよね？という話をする。なんとなく了承もらう。
- zが0じゃないときも同じことが言えて、そのときは、zが高くなるほど円が小さくなるということを主張する。なんとなく了承もらう。
- つまり、共通部分が存在するギリギリの高さを見つければ良いので、二分探索で良いことが分かる。なんとなく了承もらう。共通部分が存在するかは、大体円の交点付近を見れば良いということは知っていた。
- 方針が立ったので、drafearに円の交点ライブラリを写してもらう。
- その間に、n=1の場合とかのケースを考えるが、恐いからとりあえず交点と杭の位置(=円の中心)だけを調べればいいか～ということにする。(この判断、ある円がある円を包んでいるケースとかも勝手に回避できて、かなり幸運だった。）
- とりあえず写せたらしいので、コーディングする。
- なんか高専祭のことについて話し合う2人に対して、「今やるのか（困惑）」とか思いながら書く。叱咤しつつも、僕も意見加えながら書く（ひどい）。
[2:30] Eサンプル一致
- 一発で一致した。めっちゃ幸運。
- tacosufestivalたちが高専祭とF問題のことを話している間に「一致した」と言ったら、「これマジ？そんなわけないだろ」→「一致してるわ」みたいな流れになったので、出しちゃえ出しちゃえの流れで提出。
[2:34] E Accepted
- ウオオオオオオ！ハイタッチ大失敗してタコスの手が僕の顔面に襲いかかる
- 10位でびっくりする。F解きたいと思ったが方針が固まっていない。
- とりあえず実装して改善することにする。あまり気乗りしないが書く。tacosuが入力部分を書いてくれていたので、少し楽になっている。
- 高専祭の話を再びされている～～～。
[2:45] Fの制約に気づく
- ぼく「あれっこれ文字列の長さ増えないよね？」→drafear「そうだよ」
- bit用いて状態持って最適化するか・・ってなるが時間が足りない。
[2:55] 片付け
- もう時間が圧倒的に足りなさ過ぎるので片付けをする。うーん。
[3:00] コンテスト終了
- 10位で変動無しであった。
感想
- コーダーとしては結構ハマってたと思うが、チーム練習が模擬予選以外一切無かった割にかなり上手くいったと思う。drafearとtacosufestivalにコーディングさせてないのめっちゃ申し訳ないが、他の面でかなり助かっているので、本人らが退屈だと言わなければこの調子でやりたいですね。問題の解法詰めたいときは、コーディング任せると思うけど。
- お邪魔した研究室の皆さん、セッティングとか手伝ってくれて本当にありがとうございました。
- まだ確定したわけではないですが、アジア地区予選には行けると思います。英語が懸念でしたが、チームメイト2人が最近英語に精を出しているので結構信頼しています。頑張りたいと思います。
- 会えると思っていた人でも結構予選落ちしていて、ICPCの厳しさを感じた。
- ハイタッチ練習します。
