立命館大学競技プログラミング合宿参加記
3/5~3/7に立命館大学で開かれていた立命館大学競技プログラミング合宿2019(以下RUPC)に参加してきました。 昨年に引き続き二回目の参加です。
RUPCでは三日間にわたり、それぞれ立命館大学、会津大学、北海道大学の学生が作成した問題セットを三人一組のチームを組んで解きます。 コーディングに使用できるPCは同時に一台で、ICPCと同じ形式です。
チーム編成は事前にチームを組むかランダムで決めてもらうかのどちらかなのですが、今年はtsutajさんのCompetitive Programming Team Makerが大活躍していました。 チーム戦の醍醐味として同じくらいの実力の人と組んでワイワイ考察するのと、強い人に組んでもらって色々教えを請うの両方がありますが、今回も両方楽しめたので良かったです。
一日目
一日目は寝坊しましたが何とか自己紹介には間に合いました。
この日はランダムでチームを組み、kawabysさんとprdさんでチームrupc_ponta_gori_kusaを組みました。
問題セットはこちらです(https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day1)
チーム全体では5問を解き、私はB, Cの考察＆実装、D問題の考察をしました。
割と好きな問題セットでとても楽しかったです。
B問題
この問題は問題文の通りに実装をやるだけの問題でした。 prdさんがA問題の実装をしている最中にB問題のコードをホワイトボードに下書きし、 prdさんが実装終わった瞬間にコードを書き始めました。
C問題
Bを実装した後D問題を読みましたが、インタラクティブ問題だったので交換してC問題を解き始めました(AOJとpythonのインタラクティブは相性が悪いらしい) この問題、見つけた人はよく見つけたな!?とびっくりできるので、是非一度問題文を読んでみてください。
私はホワイトボード上で実験しました。(5, 4)に石を置けたら普通のオセロっぽくなるのにと思って一人オセロをしましたがどうしても置けず、置けない場所に規則性があるのでは？と思いました。 4*4の盤面で全列挙すれば法則が見れるだろうと思いホワイトボード上で書き、法則を見つけました。 では法則をどう実装したものか……と悩みましたがprdさんに相談して累積和で書けばいいと言われたので二次元累積和を書いて通しました。
D問題
C問題を通している間にprdさんがE問題を通してくれたので、順位表的にD問題をきっちりと通そうと決めました。 改めてkawabysさんから問題の概要を聞き、グラフの構造はこちらで指定できると知りました。 kawabysさんの方針を元に二進数28でグラフをパッと閃いたのがこの日のハイライトで、kawabysさんにそのまま実装をお願いしてACになりました。
F/G問題
見たけど歯が立ちませんでした……
懇親会
立命館のオードブルは結構豪華で、大学の設備とは思えないぐらいおいしかったです。 懇親会の途中で普段にじさんじのこと呟いてますよね？とこうきさんに話しかけてもらったので、 オタク特有のどこまで喋れるかのジャブをうったところ一期生の初期から統合後の新ライバーまで全部話せることが分かり狂喜乱舞しました。 好きなライバーや伝説の配信、哲学について話しまくってのどが渇いたのでお茶を飲もうとしたとき謎ドーラをやったら通じたので凄くうれしかったです。
二日目
この日も遅刻しました。間違いなく目覚ましアプリが鳴っていなかったせいです。
この日もランダムでチームを組み、tsukasa_diaryさんとtuki_remonさんでrupc_tsunaremonを結成しました。
問題セットはこちらです(https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2)
チームでは5完、私はC問題しか解けず激冷えをしました。
会゛津゛大゛学゛許゛せ゛ね゛ぇ゛よ゛な゛ぁ゛
— nadare🌱 (@Py2K4) March 6, 2019
戦゛争゛だ゛っ！
C問題
この問題は長さNの電話番号を圧縮した後ボタンを全列挙するのですが、電話番号の圧縮に気づく前の方針を引きずりすぎて面倒な実装をしてしまいました。 何をしたのかというと、真ん中のボタン、上下左右のボタン、斜めのボタンに分けるとそれぞれのグループで列挙に必要な個数を減らせるので、これで計算量を削ろうという方針でした。 斜めのグループでは対角の距離に考慮する必要があるので実装が面倒になり、この時点で落ち着いて引き返すべきだったのですが、無理に実装をして無駄に時間を使いました。
B問題
正解の方針には比較的すぐたどり着いてはいました。ただ、x < aの時にそのままxを出力する部分でMODをとるのを忘れ無限に時間を溶かして結局AC出来ませんでした。 コンテスト後にちゃんとMODを付けたら通ったので本当に辛かったです……
懇親会
しうかつの話がでてきて、やっぱ競プロerは競プロerのいる会社に就職するんだなぁと思いました。 ほかにもきゅうりさんから昔阪大で勉強会やってた時の内容を聞けたので、近いうちに似た内容をやりたいと思います。
三日目
この日はあまり眠れていなかったのですが、ちゃんと目覚まし時計(物理)を用意したのでちゃんと起きられました。えらい。
最終日は元からチームを組んでいたので、ixmelさんとprdさんでチームを組みました。
ixmelさんに介護してもらいながらprdさんとD問題までを解き、最終的にチームで5完でした。
私はA, C, Dを解きました。
A問題
やるだけでしたが、最初に書いたコードは出力の形式がガバでした。 サンプルが丁寧だったので無事通せました。ありがとう
C問題
1012までの数字の素因数は106までの素数を確認すればチェックできるのですが、この際106より大きい素因数を忘れていたのをixmelさんから指摘されました。 素因数分解でここを忘れがちだから気を付けることを覚えたので、今後はもう大丈夫だと思います。
D問題
コストを前計算して二分探索でクエリを消化していく系の問題で、方針は見えやすかったです。 ただ、コードを書く際変数のつけ方がぐちゃぐちゃでごっちゃにしてしまったので反省です。
E問題
ローリングハッシュを勘違いして覚えていました。結局考察から実装までixmelさんにやってもらいましたが、これはちゃんと復習してろりは自分の物にしたいと思います。
三日間を振り返って
三大学の皆さんには毎回素敵なイベントをを運営していただいて本当に感謝しています。 また、一緒にチームを組んだり戦った他の競プロerの人にも感謝です。
一年前に参加した時は典型の知識がなくボロボロだったのですが、一年競プロをやっていた成長を感じました。 ただ、まだ後ろの方の問題が解説の用語の意味も分からず、フローとか聞くと思考停止してしまうので、蟻本中級編以降の知識もちゃんとつけていこうと思いました。
