RUPC2019参加記

2019/03/05-2019/03/07に開催されたRUPC2019に前泊して参加してきました。このブログを開設したのは昨年のRUPC2018がきっかけなので、感慨深いです。

day0

朝9時くらいの新幹線に乗って滋賀県に行きます。郡山でいづみちはると合流します。道中は前日のABC120-Dのコードゴルフをしていました。 滋賀についてホテルに荷物を置き、京都に行きます。いづみちはるの知り合いに会いにゲーセンに行き、そのあとご飯を食べました。

day1

朝早めに起きてご飯を食べ、立命館に行きます。去年と同じ建物に行くと一階にくちもちとくらさんとホスフィンがいました。しばらくしてへのkとかも来て、そろそろ上に上がって良いのでは？となったので行ってみると、すでに結構人がいました。

そのあとも続々人が来て、チーム決めを経ていよいよコンテストが始まります。 1日目のチームは前日に決めておいた僕・いづみちはる・ツカサさんの組です。

コンテスト

僕は最初にCを読んだのですが、全然わからなかったためBを通したツカサさんに投げ、Aを通したいづみちはるからDの考察を聞きます。この間にツカサさんがCの実験をしていて、サンプルが合うので投げるとAC。

Dについて、二分木で良さそうと言われたのでダメでは？と言ってみると実は良いことがわかり、実装をします。なんか無限にREが出たので実装方針を適当に変えると通りました。3RE。

Eはまあそれはそう、と言いつつ蟻本のLISを参考に実装し、サンプル1が通ったのでサンプルが通ったと伝え、提出すると早々にWAになってしまいます。ここで問題文をよく見るとサンプルが複数個あることに気づき（は？）、全部試すと普通に違っていました。あほくさ

よく考えていなかった不等号に等号を付けると今度こそサンプルが全部合い、提出してAC。

そのあとは僕がFの考察を、ツカサさんがGの考察をしていて、Gに貪欲を提出したらしいですがWA。僕もFがある基準に基づいて貪欲に取れることまでは分かったのですがその基準がわからずダメ、結局五完で終了しました。

その後は懇親会に参加せず、にぼで食事をしてゲーセンに行きました。にぼはこの日ちょうどラーメン360円券を配っていたらしくて良かったです。 去年と同じゲーセンに行って遊び、帰りはナンが終電を逃しそうになっていました。というか完全にアウトのはずだったのですが、僕たちが乗った電車が大幅に遅れていたので、その待ち合わせをしてくれていたらしいです。

day2

昨日、day2は東北大から来た僕・ホスフィン・碧黴さんでチームを組もうという話をしていたので、そうします。

コンテスト

Cを読むと全探索だなあとなり、ホスフィンがAを通した後碧黴さんがBの考察をもうちょっと詰めるらしいので先に書きます。実装が面倒で嫌になってうっかり直前の考察を忘れ、実行に無限時間かかったりしていたのですが、AC。

他の問題を見ていると碧黴さんからBの相談を受け、シミュレーションでは？とか言いながらなんかごちゃごちゃやっていると通ります。

Eに僕の名前が出ていたので、次にこれを解くことにします。AC。別にFAでもなんでもないのですが、無理を言って最初に実装を始めれば取れたなあという気持ち。しかしコンテスト開始時には僕の名前が出る問題があることを完全に忘れていたので……（名前を出す許可をしたので、問題の存在を知っていたはずだった）

GはNimで、ホスフィンのググりによりD+1でMODを取ればよいことが分かっていたのですが、実は勝利条件を誤読していました。1,1,1,...,1で来るとまずいのなら最初に全部の山から1引けば良いのでは？となり、サンプルが合うので碧黴さんに実装を伝えてAC。この実装はめちゃくちゃ軽くて、4分で終わりました。

DはDPと書いてあるのですが、通している人があんまりいなくて怖かったので後回しになりました。y=0が許されていないことを見逃してサンプル2が合いませんでしたが、そこを直してAC。

Hはまあどうせフローでしょ、となり辺の張り方も分かったのでライブラリを持っていた自分が実装します。サンプルが全部0になりましたが、適当に辺の張り方を一部逆にしたら通りました。こういう問題に慣れていない。

残りで解けそうなのはFだけだったので、それを考えます。東北大のチームAobayama_dropoutはこれまでのJAGやICPCにおいて、簡単な問題を爆速で通した後何もできずに椅子を温めることを繰り返していたので、ここからもう1問通すことが重要だと考えていました。

まず点集合の凸包が欲しくなったのでライブラリを探していると、制約に与えられる点が凸多角形であることが書いてあると碧黴さんから指摘されました。ええ……

正三角形の全ての辺に1点以上ずつ点が乗っていることがわかり、サンプル1で試してみると、さらに正三角形の1辺には凸多角形の1辺が乗るらしいこともわかりました。乗らなきゃ解けないだろ、と証明なしに突き進みます。

正三角形に乗る辺を全通り試すと、固定した辺について斜め方向に最も離れた点が正三角形の他の辺に乗ります。この点は、全体を適当な角度だけ回転させてx座標の差を見れば判定でき、その差から辺の長さも決められることがわかります。

実装してみると全然サンプルが合わず、適当に回転する角度とかmaxとminを入れ替えたりとかしていたのですが、実は回転させる方向の正と負を間違えていたことに気づき、ここを直すとサンプルが合います。祈るような気持ちで提出、AC！これはこの合宿中最もうれしいACでした。

結局O(N2)で解いたのですが、点から垂線を下ろす実装より定数倍が軽かったらしく、実行時間については難なく通りました。ノーペナ八完は最の高。

この日は懇親会に行きます。朝ホテルに折り畳み傘を置いてきたので、雨に降られながら延々歩くことになってしまいました。 学部1年生が多いテーブルについて、何やかや話します。そのあとナンやへのkと話し、「最小素因数ゲーム」で負けたりしていると解散になりました。

昨日行ったゲーセンは遠すぎるので、台数は少ないけど隣にあるゲーセンに行くことにします。懇親会から流れてくる人が無限人いて面白かったです。seicaさんがメイド服を着てドラムをしばいているのを遠目に見ていたりしました。 卓球で空振りしているうちに閉店時間になり、ホテルに帰って寝ました。

day3

起床TLE。同じく寝坊していたもやし先輩と一緒に優雅に朝食を摂ります。

この日のチームは昨日ナンとへのkと組むことにしていたので問題なし。いつの間にかチーム名がBurningkotatsuになっていました。温まるのかな？

コンテスト

へのkがFAを狙ってAを解きます。入力の数は2つだと予想してそのコードを書いていたのですが、全然違って残念。

ナンがBを、僕がCを読みます。僕が先に方針が立ったので実装を初め、ナンとへのkがBの相談をしているのを聞きながら実装していると、何やら今自分の実装している問題を考えているような声が聞こえてきます。慌てて問題文を確認すると、なんと僕がC問題だと思っていたものはB問題でした！は？　は？じゃないんだよな　は？

仕方ないのでそれを伝え、ナンとへのkにはCを考えてもらいます。このBはオンサイトFAだったので、不幸中の幸いといった感じ。

ナンがCを書いている間に他の問題を読みます。へのkがDを解けたというのでEを読んでいると、ナンがCを通してへのkが実装に入ります。

Fが数え上げでナンが一瞬で包除の式を立て、僕に見せてきたのですが、そもそもこの式はすでに完成されていてオーダー的に十分であることが分かったらしく、へのkがDを通したあと実装をしてAC。

この間に僕がへのkにEの考察を伝えると、ロリハで殴れることが分かったらしいので実装してもらいます。AC、この時点でコンテスト開始77分、残りはG問題だけ、現在トップ、勝ったなガハハ！ｗ

へのkが実装している間にナンと僕でG問題を考えていました。ナンが頂点2組を順につなげていくDPでは？と言い、これは正しそうなので遷移を考えます。地獄の遷移をしていて、Eを通したへのkに方針を伝えると、別のことをやってみると言っていました。

そのまま一生地獄でもがいていたのですが、ナンの実装もへのkの実装もサンプル2を合わせることができず、コンテスト終了。六完オンサイト2位に終わってしまいました。

ナンの実装は、最初に挙げていたループの例を一種類忘れていたことが原因で落ちていたみたいです。へのkの実装は何もわからないのですが、2Byte追加すれば通ったらしいです。残念……

閉会後、にぼに行きました。競プロ勢がたくさんいて面白かったです。

新幹線に乗ります。仙台に着いたのは九時半ごろでしたが、ゲーセンには行かずすぐに家に帰りました。