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

あったこといろいろ

ほぼ自分用備忘録です。

RUPC2017参加記

RUPC2017の運営・作問・参加をしました

1日目

卒業式がRUPCと被っていたため早朝に大学へ移動した。
会場ではなぜかn_vipさんが保護者席にいて "学部長のありがたい話" の実況をしていてシュールだった。
卒業しながらコンテストを開催するのは初めてだったので緊張した。

卒業が済んだので15時頃にRUPC会場に到着。
omu君達のチームにスーツ姿で風船を運んで威圧する。


今回の問題セットは、最終防衛問題みたいなのはなく中難易度以上の問題が沢山あるという感じだったのですが、お楽しみいただけたでしょうか?

2日目

drafearさん、omuさんと、チーム「caffe」で参加した
drafearさんが解法を吐いてそれを実装する みたいなことをしていて、結局僕はB,E,F,K問題に関わった。

B: lower_boundとupper_boundでえい
E: 蟻本とか「ABC-D食塩水」とかで見たやつ omuさんが実装してくれた
F: drafearさんから「解は高々2」と言われると後はわかったので書く(例に漏れずバグった)
K: drafearさんから「SCCすると木になるので後はDPするだけ」と聞いて解く
さて、優秀な読者のみなさんならお気づきかと思いますが、SCCして出来るグラフは木ではなくDAGになります😫
木だと思い込んだ*1僕がメモ化をサボってTLEを大量生産している間にコンテストは終了


オンサイト2位もとい1位を取ったので*2嬉しくはあったのだけど、あまり解かれていなかったG,Jを解いたのはdrafearさんだったので、プロだなあという気持ちの方が強かった。

順位表を見るとなんか偽物がいた*3
プロが居たおかげでチームとしては勝ったけど、僕より偽物の方が強いんだよな……


3日目

btkさん、treeoneさんと、チーム「daisotsu」で参加した*4
主にA~C問題を片付けたりしていて、結局僕はA,B,C,(E,G)問題に関わった。
A: codefightsで見た
B: treeoneさんがバグで苦しんでいたので、紙に擬似コードを書いたりして一緒に通す
C: 列の端にある数字を得られればOK treeoneさんに託す
E: btkさんが「遅延セグ木で解けるけど貼りたくなさすぎる〜」とか言っていて、btkさんの考察を聞いてあれこれ言っていたらsetで区間を持つ解法を生やしてくれた
G: こういう問題文を読むのは苦手。LISか?みたいな考察をしてbtkさんが解法らしいものを思いついてくれたが、誤読があったので嘘だったらしい


コンテスト後にA~Eを自力で解いてみたら結構バグったので、B,D,Eあたりを実装してくれたチームメイトに感謝。
木の同型判定を学びたいのでFも解いておきたい。

おわりに

  • ブランクのせいか、実装力が落ちていて困った
  • 知り合いばかりとチームを組んでしまったが、せっかくなので初めましての人とも組めばよかった
  • 運営などをしていて春休みが消滅したので、今後はICPC国内予選に向けて精進したい

*1:無向グラフの2重辺連結成分分解結果が木になるので正しいと思い込んでしまった

*2:チーム「btklatte」はon hotel & on 卒業式という扱いとのこと

*3: 実は結構嬉しかったんだけどうまく反応できなかった(>_<)

*4:btkさんもちょうど少し前に卒業を済ませたところだったので