足跡-sokuseki-

りかの日進月歩の記録

HUPC2019 参加記

北海道大学プログラミング合宿 2019 : ATND に参加しました。参加記FAを目指します。(追記:FAできませんでした)

経緯

○○大学競技プログラミング合宿といえば、RUPCとACPCがあります。その2つの合宿は、近年は立命館大会津大・北海道大がコンテストの問題セットを提供しており、よく懇親会などで「北海道大学はHUPCを開催しないんですか〜」みたいな話をしていました*1

しかし、ここにも書いたように、競プロ合宿の需要が高まっていることもあり、北大の方がやる気を出してくれて、開催することになりました*2
北大には競プロ合宿やその他オンサイトで知り合った人がたくさんいるので、ATNDが公開されたらすぐに登録しました。

day0

国内予選の翌日ですが、当日入りをすると早朝の飛行機でつらそうなので前日入りをしました。

day1

前日入りをしていたので朝が暇で、開場より少し早く行ったんですが、それでも運営でない参加者がすでにいてすごかった。
自己紹介フェーズの「国内予選突破できなかったので懇親会で発散します」「国内予選突破できたので懇親会で発散します」がおもしろかったです。
詳細は書きませんが、競プロ合宿はコスプレ会場でもあったんだなあと思いました(小並感)(4ヶ月ぶり3回目)。

チームは事前にてんぷらさんと組むことにしていて、残り一人をランダムに決めた結果、スポンサーのフィックスターズのMatsudaさんと組むことになりました。



〜以下コンテスト〜
てんぷらさんが後半のFAとる!って意気込んでた。
競プロがほぼ初めてのMatsudaさんがA問題、自分がB問題、てんぷらさんが後ろからといていくことにする。
Matsudaさんがつらそうで、Bも数学でつらくて、てんぷらさんがFの解法浮かんだとかいい始める。PC空いてるのでとりあえずゆっくり実装してもらうことにする。Bはそれぞれの数について2つ目の条件を満たすかをいろいろ書いて確かめると、約数が少なすぎるとだめっぽいことがわかる。2から20くらいまで書いたところで、約数が自分を除いて4つあればできそうな気がしてくる。証明してないけどてんぷらさんに相談してみるとそうだねってなって、前計算はエラトステネスの篩っぽく自分の倍数に加算していくと素因数分解とか必要なくて簡単に書けると言われたのでそれをする、AC。
Aはつらそうだけど、方針を聞くとあってそうなので、そのまま任せてC以降を読むことにする。
Cは構文解析なのでやりたくないですと言ってとばしてDを読むと、AがBの約数のときは-1で、あとはBを使わずにAだけで少なくなるかみたいなのを考えると良くて、っててんぷらさんに伝えたら書いてACしてくれた。
Aを書いてもらう間にてんぷらさんとEを考えると、てんぷらさんが(s,t)を聞いてから(s,i)と(i,t)をみるとiが最短路上にあるかわかるので、最短路上にあるやつだけをもう一度クエリ投げてパスを1つに確定するって言っててすごいなあとなる。
Aを提出すると3重ループしてdを決めた時に負になる場合の処理をしていなかったのでWA、すぐになおしてAC。
EもAC。オンサイトFA!!
Cを考えると、構文解析をしながら、短絡評価できるかをパラメータとしてもっておけばできるっててんぷらさんが言ったから書いてもらった。その間FGをみてMatsudaさんといろいろ考える。TLEしたけど状態の持ち方を変えるとACした。Fはてんぷらさんの方針(つらそう)をきいてから実装をしてもらって、てんぷらさんが実装している間2人でもっと簡単に解けないかを考えてた。けどあまりいい方法が浮かばなくて、そうしているうちにてんぷらさんがFを通してオンサイトFAをとる。
残ったGは何もわからなくて、計算量がアになっていいなら根を決めて木DPなんだけどなーとか言ってた。でも順位表を見るとうしたぷにきあくんがGをいっぱいWAってて、うしくんがいてこんなにWA出す?とかてんぷらさんと話してた。
うしたぷにきあくんがACしたあたりで、全方位木DPが〜とか言ってると、てんぷらさんが去年の国内のHに似てるっていい始めて、解説記事や講評を読んでいると、前原先生のQiitaにたどり着き、てんぷらさんが読解して、これ実装したら10^9くらいになるけど解けるのでは?って言って実装し始める。直前で書き終わって提出するもWA。全完できずにコンテスト終了。

〜以上コンテスト〜

感想戦をしてから、解説を聞く。


解説が面白すぎるんだよなあ。問題については、個人的にEが好きでした。

その後、懇親会会場まで移動する。おいしくていろんな話もできて楽しかったです。


AGCに出るために早抜けした人がちらほらいたんですが、AGCが30分こどふぉっておもしろかったです。

day2

夜はあんまり眠れなくて起きられるか不安だったんですが、無事起床。


会場についてお菓子をもぐもぐしたりする。
チームを事前に組んでいたので、チーム決めの時間にアニメを見ていました(迷惑なのでイヤホンをしようね)(ごめんなさい)。(追記:見ていたアニメはリステです )
チームメイトはえびちゃんとしるにゃん。

〜以下コンテスト〜
AのFAを担当しますと啖呵を切ってしまったのでAを読む。読んでる最中にBがAと問題設定が同じと聞こえたので、C以降を読んでもらうことにする。
A書いたんですが、バグらせて1WA。すぐに直してAC。FAはとれませんね。
Bを考えるとぜんぜんわからなかったのでえびちゃんと考えていると、しるにゃんがDわかったっぽいことを言っていたので、コーディングを交代する。
サンプルがあったぽいので投げてもらうとTLE。Bは4隅に近いやつだけピックアップしてから2乗かけて試すとよさそうだとわかり、しるにゃんに代わってBを書く。AC。
Dは2べきで考えるとよさそうとなってそのままAC。オンサイトFA。
その後えびちゃんからCの概要を聞くも、ゲームが得意ではないのでわからず、全探索するくらいしかわからないーとか言って、放置してE以降をすることにする。
ぜんぶ読んで、一番できそうだったEを考える。よく考えると、頂点1からパンを買うまで、パンを買ってからジャムを買うまで、ジャムを買ってから頂点1までに分けて考えることができると気づく(今日の最大の貢献)。頂点1からの距離を最初に求めて、あとはパンからジャムまでをいい感じに求められるといいな〜とか言ってた。頭がないので「パラメータが2つだとCHTみたいだねー」とか適当を言ってたら、しるにゃんがパンを買った時のコスト(パンの幸福度-距離)を初期値にして各ジャムまでダイクストラみたいにわーってできない?という天才の発想をしたので、えびちゃんにそれを書いてもらう。ちょっとバグったけど、なんとかAC。オンサイトFA。
FGHよりも明らかCが解くべきなので、Cを3人で考える。ゲームがわからないときはとりあえずやってみるという精神で、えびちゃんと実際に対戦する。しるにゃんは黙々と規則性を考えてた。ゲームが1試合終わっても何も得られなかったので、えびちゃんにとりあえず愚直解をかいてもらって、小さいケースで規則性考えようってなった。えびちゃんのコードをちょくちょく見ながらFを考える。すると、途中でしるにゃんが、「奇数が2つ以上あると、最初に真ん中をとってあとは対照的に動くと最適戦略」と言ったので、それをえびちゃんに書いてもらう。AC。すごい。
この時点で4完で、オンサイトには5完も出ていて、順位表からEとFのAC数が同じくらいだったので、どうしてもFをときたい!という強い意志が生まれる。
いろいろ考えると、Biでまとめて計算するのと、Aiでまとめて計算するのをして、包除で計算できない?みたいな話になる。でも計算量的にやばそう。そのあともいろいろ考えてみたけど、何も浮かばず。「こういうのはwriterの気持ちになるとよくて」「じつは全部包除なのでは?」「F包除G包除H包除」「A包除B包除C包除……」「A包除まじ?!」みたいな謎会話をしていた。最後はCEを使って
f:id:wk1080id:20190715225012p:plain
f:id:wk1080id:20190715225015p:plain
f:id:wk1080id:20190715225013p:plain
という遊びをしていました(ごめんなさい)。

〜以上コンテスト〜

感想戦をして解説を聞く。
「998244353 で割ったあまり」が多かったから実は全部writerてんぷらさんでしょとか言ってたけど全然そんなことなかった(それはそう)。

その後、解散してお片づけをした。お片づけの途中、えびちゃんと廻小宮ごっこをしてた。
一度家に帰ってから、しるにゃんとえびちゃんとわくくんと4人でゲーセンに行って遊んだ。
そのあとしるにゃんと別れて、3人で回転寿司を食べにいった。おいしかった。




寿司が流れてくるの面白かった。寿司と一緒にデザートも流れて来てさらに面白かった。3人で注文のタッチパネルのバグ探し(?)みたいなことしてて、オタクか?とか言ってた。
そのあとさらにゲーセンに戻ってお金をたくさん溶かした(ア

さいごに

今夜も1泊するんですが明日は特に何もないので、参加記はここまでにします。HUPC全体的にとても楽しかったです。チームでたくさん考察できたのも良かったし、いろんな人と交流できて良かったので、機会があればまた来たいです。

HUPC開催前に「北海道で開催しても誰も来ないんじゃないか」という話があったんですが、少なくともHUPCは30人以上が全国から集まって来たので、もうどこで合宿を開催しようと競プロ狂は来るんじゃないかと思っています。
合宿開催したいけど運営できるか不安ですみたいな人は気軽に相談に乗ります!いろんな競プロ合宿があったら楽しいよね!各地での開催を待っています!!!!

*1:開催時期的な問題や、年3回も作問をしなければならない負担、会場が北海道であることなどの懸念事項があり実現には至っていませんでした

*2:実はそすうさはRUPCでの運営経験を買われて、HUPCの運営の相談に乗る役をしていました。