ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

会津大学競技プログラミング合宿2019参加記

番外編

と言うことで、昨年も参加したACPCに再び参加しました。

1日目

行き

新幹線では、JAG合宿の復習として、最小費用流を写経しながら問題を解いていました。
郡山から会津若松への電車では、TABさんやてんぷらさん、てぃーいけさんを始めとした競プロerの方々が続々と乗ってきて面白かったです。

可愛い。

コンテスト

わくさん、drogskolさんとのあらかじめ組んでいたチームで出場しました。

コンテスト開始後は、わくさんがA、僕がB、drogskolさんがC以降を読む、という形で進めました。わくさんがAをかなりのスピードで通してくださったので(オンサイトだとFAでした)、そのまま自分もBを結構な速度で通すことができました(こちらもオンサイトFA、わーい)。
その後は、わくさんがCの実装を行うことになり、自分とdrogskolさんでD以降の問題の共有をしつつ、DEの考察を行いました。
Cの実装の合間を縫って自分がDを通しました(が、自分は嘘でした。それぞれの辺に対する2つの頂点を通った回数を加算する際に、どちらか片方の頂点分しか加算していなかった上、そもそも自分の解法にコーナーケースがありました)。
その後は、Cの考察をし直したときに、わくさんが強連結成分分解ですねぇ、と言ったので、たしかになんでここまで誰も気づかなかったのだろうみたいに反省をしながらCを通し、3人でEを行うことになりました。
E問題は、大方正しいDP解が求まっていたのですが、そもそもの笛をソートする優先順位が間違っていたので、そこに気づけずタイムアップとなりました…実際、数分後に優先順位を変えただけで通ったので悔しいです。
Fは3人とも何もわからず、Gはフローっぽくてやりたいことはなんとなくわかるのですがコーナーケースの処理が何もわからないので無理そう、となっていたので今後の課題になりそうです。

コンテスト後

まずはラーメンを食べました。

ラーメン屋に入る前、yamadさんが言っていたダジャレを晒しておいたのですが、数分後にてぃーいけさんにお会いしたときにはすでにバレていて、Twitterは怖いなぁと思いました。

その後はyamadさんを除いた早稲田勢で銭湯へ行きました。コーヒー牛乳うめぇ。


ホテルはyamadさんと同室だったのですが、

  1. yamadさんがTwitterを開く
  2. yamadさんが笑い出し、ボソッと「Twitterおもしれぇ」とつぶやく
  3. 僕が「どうしたんですか」と尋ねる
  4. うしさんの過去ツイートが朗読される
  5. 僕が爆笑する
  6. 数分経ち、yamadさんがボソッと「Twitterおもんな」とつぶやく
  7. 僕が爆笑する
  8. yamadさんがボソッと「Twitterアンインストールしたわ！ｗ」とつぶやく
  9. 僕が爆笑する
  10. 1へ

という雰囲気のやりとりを繰り返していたら日付が変わっていたような気がします。

2日目

朝

美味しかったです。

大学へ向かう途中、誰かのスマホから急に通知音が流れ、どうしたのだろうと思っていたのですが、
しろくん「ツバサさんが今他の方のツイートをRTしたので通知音が流れてしまいました、マナーモードにしてバイブだけにしますね」
？？？？？？？？？？？？？？？？？？？？

僕は後輩にストーキングされています。

コンテスト

ホスフィンさん、よこさんが2人で既に組んでいて、僕がランダムでそこに入るという形になりました。
自分はB以降の問題を全て読み、適当に解けそうな人に割り振る、みたいなことをしていました。
初めはC担当だったのですが、B担当のホスフィンさんがBがぱっとわからなさそう、というのと、Cが幾何で自分よりホスフィンさんがやるのがよさそう(ただやりたくないだけです)、ということで、Bの考察を行いました。結局Bの実装はAを終えたよこさんに投げました。
その後は、I,Hを自力で解き、Mは式変形が苦手だったのでホスフィンさんに投げてデバッグを行い、Gはゲームだったので、グランディ数の概念のみをよこさんに教えつつ必勝法を考えてもらう、という感じで割り振りました。
これがうまくハマり、残り時間40分ほどで7完という形になりました。
しかし、最後に考えていたE問題が全くわからず、転倒数が絡んでいそう、という地点から進まなくなっていませんでした。が、残り3分ぐらいでホスフィンさんに「実装をしていいですか」と聞かれ、何もわからず「いいです」と答えると、なんと残り数十秒で通ってしまいました。
？？？？？？

懇親会

懇親会がありました。
自分が座っていた卓は、全員20歳以上なのに2人しかお酒を飲まない卓で、隣の卓も、ninjaさん以外が全員未成年、という卓だったので、比較的平和でした。
途中、顔を真っ赤にしたmonkukuiさんがいらっしゃって、明日のジャッジに間に合わないと危ないから集合時間まで起きてお酒を飲んでいれば安全だねぇ！とか、Clarでしりとりをしたり解法を聞こう！みたいな謎の会話をしたり、てんぷらさんやTsutajさんがいらっしゃって、goodbatonさんとのセグ木トークに挟まれ逃げられなくなった結果、わけもわからず頷く係をしたりしていました(セグ木を使わずに累積和を書く人は偉い、みたいな声が聞こえて、？？？となっていました)。beetさん、てんぷらさんの卓では食事がレート順に取れるらしく、それを眺めて怖いなぁ、という話で盛り上がったりもしました。

懇親会後

懇親会をはやめに出て、この日も銭湯に行きました。

コーヒー牛乳うめぇ。
お風呂上りに、ちょうど銭湯に来たばかりのてんぷらさんや、赤みが引いたmonkukuiさん達に出会いましたが、懇親会の最後の方はやはり大変でした～、みたいなお話を聞きました。
monkukuiさんは、受付で預けるはずの下駄箱の鍵を下駄箱につけっぱなしにしてしまったらしく、入り口に戻って下駄箱の鍵をO(HW)で全探索していました。結局ポケットに入っていたみたいです。なんで。

寝る前は初日と同じく、yamadさんのTwitter実況を聞きながら笑う人になっていました。すると...

なんでスマホが鳴るの？？


3日目

朝

起きてしばらくしていると、部屋にボブネミミッミが大音量で流れました。

遅刻しました。ごめんなさい。

コンテスト

自分はB,Dを書きました。
Dは桁DPだったので自分がやりますと言ってそのまま通しました。
Bは実装が重そうだったので、ろーるまんさんの代わりに自分が実装をしました。
B問題は、前計算で4種類それぞれのテトラミノについて、一番左上のブロックからの相対座標をペアでメモしておくと、ミノの当てはめる順番をnext_permutationで全探索して、盤面を走査しつつ、左上の空きマスにぶち当たるたびにピースを埋められるかどうかを試していく、というように実装しました。
解説をなんとなく聞いていた感じ、毎回走査をして調べるのは想定TLE解らしい？のですが、AOJを信じているので通りました(自分は実装途中に、計算量で1か所×4を見落としていることに気づいたので、その時点で計算量について考えることをやめました)。

E問題:三人「セグ木をガリガリ書いたこと(残り時間で実装しきる力と気力)はないです。」
F問題:三人「suffix arrayを書いたことはないです。」
G問題:三人「全方位木DPを書いたことはないです。」
　　　　　　　　 　 終
　　　　　　　　制作・著作
　　　　　　　　━━━━━
　　　　　　　　　ⓃⒽⓀ

帰り

様々な方と一緒に学食でお昼を食べました。

帰り道の新幹線では、しろくんにday2のI問題を教えていました(実際は横からみていただけですが)。のですが、途中でいきなりしろくんが
「ツバサさんツイートしましたね？」
と言ってきました。
だからなんで？？？？？？？？？
助けを募集しています。

東京についた後、ふたたびてんぷらさん、おきもちさん、りあんさんと合流することができたので、その中でおきもちさん、りあんさんと、後輩のsuta君の4人でラーメンを食べました。


全体のまとめ

今年もとても楽しかったです。初めて競プロのイベントに参加した去年とは違い、いろんな方に認識してもらえていたり、去年よりも高度な話をしたり、問題を解いたりすることができたと思います。
来年も参加したいですね。

運営をしてくださった方々や、自分とお話をしてくださった方、ありがとうございました。

おまけ

JAGのときはお見掛けしただけだったのですが、改めててんぷらさんはかっこいいと思いました。
参考↓