7完20位。阪大内2位。
国内予選の参加記はこちら
チーム
kotamanegi_mijingiri
黄色下位3人チーム(最近KowerKointは2段になりました)で、阪大では2軍でした、国内では3軍のチームに負けましたが…。
- KowerKoint (@KowerKoint2010)
一番レート高い。実装とか早解きの鬼。
- Daylight (@Daylight_pro)
DPとかデータ構造が得意らしいです。3人の中では一番英語ができるので問題読解を頼むことが多かった。
- shinchan (@Sophia_maki)
数学とかFPSとか構築が(2人に比べて)ちょっとだけできます
戦略
KowerKoint君にAのFAを狙ってもらったあとセットアップ。Daylight君にはB。僕はそれ以降の問題に後ろからざっと目を通して、問題文が短いものから読んで解けそうなのを探す。
また、その都度得意不得意に合わせて問題の交換は行い、読解がわからない問題があったり新しく読みたい問題はDaylight君に任せたり、重実装やライブラリ写経はKowerKoint君に任せたりという方針をとりました。
そして、私はできる限り実装をしない。すぐかけそうなのは書いてもよい。と決めていました。
あと特にこういうのは決めてるわけではないですが、僕の性格的にいろんなことに口出ししたいタイプなので、2人に指示を出したり、2人の解法のコーナーケースを探したりすることが多かったです。これは結果的に(最後の15分を除いて)いい方向に招くことができたと思います。
実力は遠く及びませんが、これのりんごさんみたいなポジションがしたいのかなと感じました。 japlj.hatenablog.com
リハーサル
順位表が見当たらないので解いた順番とかは忘れました。
A問題
KowerKoint君にFAを狙ってもらいましたが2位だったような気がする。おしい。
B問題
インタラクティブ。KowerKoint君が実装を終えてサンプルが合わなかったかペナったかだった気がします。僕も問題を聞いて考察は自明。KowerKoint君の解法だと実装バグらせやすそうと思って僕が実装しなおしてAC。
C問題
Daylight君が困っていました。解法を思いついたけどサンプルがなぜそうなるかわからない、という状況でした。KowerKoint君も手伝ったかは忘れました(ごめん)。僕も問題を聞いて、お気持ち解法と注意点をいろいろ説明してサンプルだとこの注意点にはまってしまってーというのを説明した。Daylight君が細かいところを詰めて実装してAC。
D問題
読んだら典型と既出の組み合わせみたいな問題だった。重実装では全然ないけど僕が書くには重いので、KowerKoint君に解法を説明して実装してもらってAC。
本番
順位表があるのでできる限り時系列順に。
コンテスト開始、KowerKoint君がAを読んで実装。Daylight君が封筒を開けてBを見る。shinchanはボールペンをすべて開封して後ろからさらっと雰囲気だけ目を通した。問題の種類だけメモった。
A(0:05) KowerKoint
2位だった。おしい。
Daylight君がBで詰まってたので僕も問題を教えてもらったが僕は苦手そうなのでKowerKoint君が手伝う形に。
このあたりのどこかで、僕が2人に「Dが構文解析みたいなの書いてある。サンプルみた感じは簡単そう、読んでみてほしい」と伝えてKowerKoint君にやらせてみたら考察(そんなに難しくなく、ロリハ+区間DP+復元らしい)と実装100行を爆速で終えてAC。FAでした！
D(0:27) KowerKoint
KowerKoint君が実装している間、順位表ではspeed starにFが解かれていた。読んでみると得意だった。setで i 行目と i+1 行目が反転しているとき i+1 が入っているみたいなのを行と列それぞれ持った。実装も簡単そうだったのでそのまま僕が実装してAC。
F(0:36) shinchan
このあたりでDaylight君かKowerKoint君がBを実装してペナを生やしていた気がする。僕はCを考えていた。Cはポリアの定理はそれはそうとして、回転の重複を無視する場合が解けなければ話にならないが、話にならなかったし順位表を見て難問らしいので捨てる。
BをKowerKoint君に任せてDaylight君と他の問題を見る。Kが解かれていたが海外なのでいったん無視する。speed starが解いていた問題をDaylight君に読解を任せて2人で考察してた気がする。
しばらくしたらKのACが増えていたのでDaylight君に読解と説明してもらうと解法はすぐ生えたのでDaylight君に伝えた。KowerKoint君がBを実装している間は、2人でインタラクティブ特有の質問回数の制限とかが大丈夫かの確認をしていた。
そうこうしてたらKowerKoint君がセグ木二分探索でO(NlogN)でBをAC。コンテスト後にわかった話では入力の数値Cの制約を見落としていてこのようなことになってしまった…。
B(1:54) KowerKoint (考察: KowerKoint, Daylight)
このあたり記憶があやふやなんですが、KowerKoint君がEの実装をしていた気もする。さて、Daylight君がKを実装、バグがあったので僕もコードを読んで2人でバグを見つけたりした。
K(2:45) Daylight (考察: shinchan, Daylight)
EとGは解きたいなぁという気持ちになる。Eは僕が「高速ゼータ変換…、うーん、ないか」と言ったのに思いつけなかった。KowerKoint君がいろいろ工夫して永続配列を書いたりしていた。
EはKowerKoint君に任せて、GをDaylight君と一緒に考えていた。2人でDPの添え字が合うことを確認したあと、高速化手法を考える。「FPSとか…、でも畳み込みじゃないしなー」って言ってた気がする。僕が「メモ化再帰でけっこう重複しそうで実際O(N2)もかかんないんじゃない？」と言ってワンチャンを狙ってDaylight君に実装してもらった。
動かしてみると時間制限の2倍くらいかかってた。KowerKoint君がその実装を見て「非再帰で書きたい」と言ってきた。そう、KowerKoint君はなんでも非再帰で書く。僕が「それは時間かかるからmapをunorderedにしてkeyをpairからlong longに変えてやりましょう」と指示。間に合いそうだったので提出。
なんと出力のコメントアウトを除き忘れていた！1ペナしてAC。
G(4:08) Daylight (考察: shinchan, Daylight)
さて、KowerKoint君がEでメモリのとりすぎとかでREが外れないそう。 メモリをその都度解放するようなコードに変えてなんとかAC。空間計算量 O(N*C(N, N/2) + 2N)とかで解いてたような記憶がある。
E(4:32) KowerKoint (考察: KowerKoint)
Jやってるdaylight君が「HL分解と貪欲でワンチャン…」と言い出し、他2人も「ワンチャンすぎるな…」となってKowerKoint君がとりあえずHL分解を書く。
僕が「貪欲はさすがに無理やろ～～」って言ってしまったのが戦犯。HL分解書き終わった時点で残り15分あったが、書き終われる保証はなかったけど。
このあたりは僕がちょっと貪欲解法を理解していなかったような気がする。コミュニケーションがうまくできていなかったかも。
最後に残りの問題に2,3回ずつa.cppを提出して終了。
英会話
3人いるときの英会話はほとんどチームメイトに任せていた。チーム紹介もKowerKoint君がやってくれたし。僕は単語しか言ってない気がする。
「hello」
「thank you」
「yes」
「ok」
「sorry」
「restroom」
「male」
「kotamanegi_mijingiri」
「Osaka University」
本番中にトイレに行きたいときも「restroom」と単語だけ言ってなんとかしていた。
MaleとFemaleを聞かれてどっちが男性なのか忘れたが2分の1が当たってよかった。
コンテスト前にボールペン開けていいのかなって思って「pen, open, ok？」って言ってダメって言われたけど隣のチームが開けてたの指さしたら申し訳なさそうにsorryって言われるなど。ライブラリを画面に置くアレといい、ライブラリの紙をなんとか立たせるチームもいたり、well-definedを求められる運営も大変だなぁと思った。
あとがき
阪大の1軍チーム、kotamanegi_marunageが4位で本当にすごい。こたまねぎさんとkuhakuさんはラストイヤーだったので来年は僕が1軍になる可能性がありますが、ここに追いつけるようにがんばります。vwxyzさんがよく「SPJには勝ちたい」と言っていて、SPJが5位でちゃんと勝っててすごい。
speed starもさすがです。今年がラストイヤーの強い人がけっこう多いですが、今の高3も赤がいたりしますし気を抜けませんね(阪大来てほしいな～～～)。
懇親会はいつも通り企業の人としゃべることや食べることを忘れてましたが、話したい人と話したり、話しかけられたりしてうれしかったです。
来年と再来年もよろしくお願いします！
