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

RUPC2015参加記

初参加でした

一日目

CODE THANKS FESTIVALの会場で会ったことのあるomu さんと再会する。
一緒にチームを組もうという話になって組むことになる。div1:div2を1:2で組みましょうみたいなことを運営の人に言われる。div1の人を募集した結果Mi_Sawaさんがチームに加わることになる。チーム名は全員のHNを合わせた omu_sawa_dan になる。

チーム方針をどうするか話してる時にMi_Sawaさんは普段US配列のキーボードを使用していることがわかる。その結果、Mi_Sawaさんが解法考える人になると宣言する。

コンテストが始まる。

僕がテンプレートを打ち込み、その間に2人が問題を読むという形に。打ち終わる。

omuさんがAを書き始める。

Bを読む。sortして累積和取って二分探索すればいいのがすぐわかる。Mi_Sawaさんに考えた解法を伝えると、もっと簡単な解法があることを教えてもらう。

Aが通らないらしく、印刷してパソコンを交代する。Bを書いて投げる。WAをもらう。印刷してパソコンを交代する。

今の解法だと配列の大きさが64bit分ないとダメだから、sortして累積和取って二分探索の方でいこうと言われる。パソコンを交代する。境界条件面倒って言いながら書く。投げる。通る。

Cを読む。DFSして最小値見つけて掛け算すれば良さそうとわかる。それをMi_Sawaさんに伝えるとUnion-Findを使うほうが楽だと教えてもらう。

Aが通る。Cを書き始める。O(N^2)を投げたけど通らない。次数の下げ方を教えてもらって下げる。投げる。通る。

Dの解法をMi_Sawaさんに解説してもらう。第一段階としてTLE解法をomuさんが実装することになる。その後オーダーを下げる方法を教えてもらいながら僕が実装する。投げる。通る。

EもDPで解けると言われる。解説を聞くが頭が足りないので理解できない。言われるがままに実装する。バグを取る。終了30秒前になってて慌てて提出する。一発で通る。

Mi_Sawaさんプロだった。何度も同じことを質問したけど毎回優しく答えてくれました。人間的にもプロだった。

二日目

この日は5時間セットでdiv1とdiv2は混合しないようにチームを組むことになった。

くじ引きの結果、YuZakuroさんとししゃもさんとチームを組むことになる。チーム名はhopping_heartsになった。両方面識のある人だったから気が楽になる。

チーム方針を話している時にある問題が浮上する。それぞれの普段のプログラミング環境が

YuZakuroさん ししゃもさん
OS Windows Linux OS X
キーボード JIS配列 Dvorak配列 US配列

と全く異なることがわかる。つらい。

コンテストが始まる。

マクロを打ち込む。打ち終わったあとにYuZakuroさんがBはやるだけ宣言をしたのでパソコンを交代する。

Cを読む。ワープする順番は関係ないから、まとめて右に行ったあとにまとめて左に行けばいいと思い、DPで解ける気がする。

Aを投げるけどREする。印刷してししゃもさんにパソコンを交代。ししゃもさんがAを実装する。

Bのコードを読んで配列外参照してるところを見つける。ここ直したら通るだろうってことになる。

Aが難しいらしい。印刷してパソコンを交代する。YuZakuroさんがBを修正して提出する。通る。

YuZakuroさんとししゃもさんにAを任せてCをDPで実装する。投げる。通らない。

印刷してYuZakuroさんにパソコンを譲る。Aが通る。

Dは実験して周期性を見つけて周期ごとにまとめれば良いってことになる。愚直に1日ずつ進める関数を書く。400年周期であることがわかる。実装をししゃもさんに任せて、YuZakuroさんとCを考える。

YuZakuroさんが大きく左右にワープするパターンで落ちることを発見する。

似たような問題を幅優先で解いたことを思い出す。これも幅優先ではと思い始める。

Dがなんかバグっててサンプルが通らないのでパソコンを交代する。Cを幅優先で書く。サンプルが合わない。YuZakuroさんにバグを直してもらう。投げる。TLEする。dijkstraと同じでpriority_queueを使えばいい気がしてくる。queueをpriority_queueにして投げる。通る。

ここで残り1時間ぐらい。

Dのバグ取りに残りを使うことになる。

printfデバッグでバグを探す。曜日判定を行っている

365*y+y/4-y/100+y/400+153*(m+1)/5+d-428;

でオーバーフローしてることがわかる。元々経過日数を計算する式だけど、欲しいのは経過日数の剰余だから途中で剰余とっても問題ないよねってことで式をいじる。サンプルが合う。投げる。通る。

自分が担当したCに時間をかけすぎた...。Eはローリングハッシュ使うんだろうなと思ってたら案の定だったから本番でもっと考えたかった。

チームの人にコード見てもらってバグを修正してもらうのはチーム戦って感じで良かったです。

懇親会のあと会津大の人と信州大の人と一緒に銭湯に行きました。色々お話して勉強になりました。

三日目

一日目と同じくdiv1,div2混合チームにしましょうということになる。

くじ引きの結果、わにさんとぬまさんとでチームを組むことになった。僕以外の二人がMacだったため、チーム名はMacLoversになった。わにさんとは二日目の夜に銭湯に行った時からチーム組めたらいいなと思っていたので組めて良かった。

コンテストが始まる。

わにさんがA、僕がB、ぬまさんがCを読む。

わにさんがAを実装する。投げる。通る。

Bを誤読してて解法がわからない状態だった。わにさんに相談した結果誤読が判明する。Bを実装する。タイプミスしまくる。30分かかる。サンプル一致する。投げる。通る。

Cをぬまさんが実装する。その間にわにさんとD,Eのについて話し合う。

ぬまさんがCを通す。

Dは拡張ダイクストラで解けると思い、実装する。サンプル一致しない(今思うと始点をデクリメントしてなかったせい)。

ぬまさんに、郵便物に関係する頂点について普通のダイクストラして、その後に配る順番を総当りすればいいと言われる。総当りパートをぬまさんが実装する。わにさんのEの解法を聞く。難しそうと感じる。

ぬまさんが総当りパートを実装し終えたので、ダイクストラパートとくっ付ける。投げる。通らない。

INFを10回以上足していることに気付く。intをlong longに変更する。投げる。通る。

コンテストが終わる。

Cは実装重たいって言いながらスッと通したり、Dの総当りパートを実装したぬまさん強いなあと思った。

わにさんがFについて正しい解法を思いついていて、時間があったら解けてた気がする。悲しい。

終わりに

立命館合宿とても楽しかったです。運営側、作問側の方々ありがとうございました。