RUPC2017 参加記
RUPC2017に参加したので、その参加記です。
Day0
前回初めて作問に参加したACPC2016では、原案も出せなかったし、実質いてもいなくても変わらないような感じだったのが、今回は3つ原案出せて(うち1つは問題として成立してなかったけど)1つはA問題に採用されたので、ちょっとは成長したかな？
今回は立命だけじゃなくて阪大も参加して、ixmelさんの弟(高校生)@pulmmak11さんも参加したので、作問班は大所帯となりました。
Day1 立命&阪大(&Pulmn)セット
名札の印刷が終わってなくて、朝から頑張ってみんなで切りまくってた。
4時間11問セットです。
始まった瞬間に28秒でei1333さんにA問題を通されてドン引き。
今日のハイライト: 天才なのでA問題を28秒で解いた
— うし (@ei1333) 2017年3月22日
あとで聞いてみたら、競プロのプロはエスパーのプロでした。
@shumon_84 トーナメント表が見えたのでN-1だろうって思う→入力形式を見てみたらそんな感じだったのでラッキーだったって流れです（？）(問題文は眺めただけで読んでないですね...)
— うし (@ei1333) 2017年3月22日
プロたちはトーナメントの試合回数が出場者数 - 1回っていうのは一般に知られているって言ってた人多かったけど、オンサイトでは、シミュレーションが得意なフレンズがちょこちょこいたので余は満足じゃ。
A問題の元ネタについてですが、高校時代卓球部だった僕は、トーナメント形式は試合時間に対して(特に序盤は)待ち時間が極端に長いので、効率良く試合を行なったときの待ち時間に比べてどれくらいトーナメント形式の待ち時間が長いか気になって、自分の試合数/全試合数を求めようとしたのが始まりです。
僕が辿り着いた脱落人数を数える方法は、直感的にもすごく分かりやすくて良くないですか。違いますか。そうですか。
うしさんが28秒で通した問題も高校時代の僕が1日掛けて導いた答えなんですよって絶対書く
— しゅもん@競アマ (@shumon_84) 2017年3月24日
懇親会は立命の学食でやりました。あそこで懇親会できるって知らなかった。
会津の新2回生勢と話しができて良かったです。
初日の懇親会は、競プロの話よりも、各大学の情報系学部の話をしていました。
やっぱりどこの大学もあんまり惨状は変わらないという新たな知見を得た。
あと意外とおいしかったです。
その日の夜はABC002を全完して就寝。
Day2 会津セット
交通機関の乱れ等々の理由でコンテスト開始時間が30分遅れて、11:30スタートになりました。
@n_vipさんと@plummak11さんとチームを組みました。チーム名はyazaten_nise。由来は言わずもがな。
A,B問題を担当しましたが、悪魔的なA問題によって当然のようにWAを生やすも、n_vipさんに助けてもらいつつなんとかAC。場合分けで切り抜けました。全探索っぽく通した人もいて、なるほどなと思った。
A問題はtを0.5刻みでループを回しました
— りかさん@数ぴよ🐣 (@wk1080id) 2017年3月23日
#RUPC2017
B問題まではアルゴリズムを使わないだろう(偏見)と思って、制約も見ずにちょっとだけ枝刈りしたO(n^2)解法を書いてTLE。n_vipさんに通してもらってupper_bound lower_boundの使い方を知る。
plummak11さんは僕と競プロ歴ほとんど変わらない(なんなら僕の方がちょっと長い)のにメッチャ強い(AtCoderで黄色らしい)ので、劣等感を覚えたけど、自分の練習不足なのはそれはそう。
13問5時間セットで、実質僕は0完ですがチームは7完でOnsite 2位・Online 5位でした。
niseなので本物には勝てない #RUPC2017 https://t.co/smSlMsOJga
— しゅもん@競アマ (@shumon_84) 2017年3月23日
やっぱり本物は強かったです。
例のA問題の解説が始まったとき。
RUPCDay2A解説
— ウクーニャ@マスコット (@ukuku09) 2017年3月24日
ろーるまんおにいさん「ベクトル化…ですかね…」
contestant&judge「？！？！？！」
ベクトル化なんて微塵も考えなかったよ......
全体的にベリーハードな会津セットでした。
(^O^)/ < 真っ赤だよー
2日目の懇親会は南草津駅前の魚民で。
RCOさんのおかげで行うことができました。
とってもおいしかったです。
ただ、エッチな制服で大量のウコンの力(恐らくノルマ)を売らされていたねーちゃんがいて闇が深そうだった。
@kenkooooさんと隣の席になったんですけど、前回のACPCでチーム組んだこと覚えててくれてて、すごく嬉しかった。RCOの話とかkaggleの話が聞けて、普段自分の周り学生とはあまりしない内容の会話をしてました。
夜は立命勢と蟻本を読み進めるべきか、もっと実装ゲーをたくさんやるべきかで話し合ってたんですけど、実際どっちの方が良いんだろう。
最終的に週替わりで当番を決めて、当番の人は事前に勉強しておいた新たなアルゴリズムをみんなに伝授する「蟻本を読む会」を開くことになりました。
Day3
@rollman054さんと@haji149さんとチームを組みました。チーム名はRHS。由来はそれぞれの頭文字から。
A問題を誤読して、CかD問題くらいな難易度にして解いてました。
3種類の操作で最終的に回文を完成させる必要はなく、並び替えて回文にできるならそれで終了っていうのはサンプル3で示しているのに気づけなかった。
でもその代わりに最長共通部分列の知識を得たので、それはそれで良かったのかもしれない。
7問3時間セットで個人1完、チーム3完でOnsite 12位・Online 21位でした。
Day3で最大の利益はflymakeの存在を知ったことですね。emacs捗る。
チームの結果は1番微妙だった(自分がA問題誤読したせい)けど、この3日間で1番有益な日だったと思う。
RUPCのあとは、にぼが定番らしいので、帰る時ににぼ次郎へ。
五郎全マシチャレンジに無事成功しました。
Day3の途中で(解説は全部聞いた)学部の履修ガイダンスで抜けてしまって挨拶できなかったんですけど、RUPC2017に来てくださった皆さんありがとうございました。
