足跡-sokuseki-

りかの日進月歩の記録

ゆるふわ競プロオンサイト #2 参加記

競技プログラミング 参加記

9/14にゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状のオンサイトに参加してきました。

コンテスト前

新幹線に乗りながらオンサイト準備

新宿駅で迷っていたら着くのがギリギリになってしまいました…。会場にはすでに人がたくさんいました。

2時間12問で100点~600点とスピードランみたいなコンテストらしい、開始前にペナがないという話を聞きました。

コンテスト

www.hackerrank.com


時系列順で、

A：ifで分岐するだけだなーと思って下までみたらコードを書く欄があって途中まで書いてあったのでそこに直接書いて出しちゃった。

B：やるだけだったのでこれも直書きした。

C：どの列どの行にも1つだけ白いマスを作ればいいんだなーこれはN!！wとか思って直書きしたらCE出たので手元実行は大事だなあと思いました。次の問題からはエディタで書いてます。

D：n-ドイッチすこ。#の個数をもって、|が連続したら答えにして個数リセット、をした。

E：kameの場所はqiなので気にしなくてよくて、usagiはクエリごとにしゃくとり?っぽくして比較すればいいやーって思った。クエリが昇順なのありがたいなあ。

F：あれ、これクエリ先読みしてしゃくとりか？また？クエリ先読みの練習題？とか思ってたら、各暗唱の文字数を前計算しておいてクエリごとにlower_boundでいいことに気づいた。

G：各クエリで範囲Aを全部ひっくりかえして範囲Bを全部ひっくりかえしても等価なので、ひっくり返した回数を持つ2次元配列を用意して、クエリごとに長方形を2回加算して（加算場所は4箇所*2回）最後に累積和。2次元累積和わすれたのでいもす研をググっちゃったけどよく考えると覚えてた（は？）。回数が奇数のマスの総和を出して終了。

H：ゲーム苦手で実験したくないな…と思っていたら、制約が小さすぎたので、dfsで探索すればいいや！wって思ってたらバグらせた。デバッグ出力とかしてたけど、わからないまま残り時間があまりなかったので後でデバッグしようとして次の問題に進む。

I：なんだこれ…と思ったけど制約の「少なくとも2つは1」を見て、じゃあ各味について少ない人から貪欲にすれば、箱の数にぶたんでできるじゃーんって言って実装した。ピノ食べたことないので、バニラ10アーモンド7チョコ7で固定されてるの意味わかんなくて、これ与えれば良くない？ってずっと言ってた。

J：サイズが大きいので愚直DPはできなくて、500を使うんだな〜となる。DPの遷移は一定なので、これ行列累乗で高速化できるね！とか言ってたんですが、これは実は縦が10^9以下の奇数、横が500だと誤読していて、ずっと合わないなーとか言ってた。誤読していることに気づかなくては？とか言いつつ次の問題を見る。

L：Success Rateを見てKよりLを優先した方が良さそう？と思ってLを開く。なんかWUPCで似たようなの見た（ACはしていない）なあ*1とか思ったけど、わかんないからフローか？とか言ってた。

K：trieだと構築でTLEしそう、じゃあSAか？とか思って考えてたんですが、存在しなくて自分より後ろを調べるときに愚直に1つずつ見る以外の方法が思いつかなくて、1つずつ見てたらTLEしないか？ってなって、じゃあどうすんの、って思ってた。

最後まで問題見たあと残った時間が10分くらいしかなかったので、デバッグしたりしてた。


f:id:wk1080id:20190915174141j:plain
この画像からはわかりませんが（AtCoder ID が書いてある人はオンサイト参加者の一部）、オンサイト順位はけっこう良さそうに思える。わーい！

コンテスト後

prdさんがほぼ全ての原案をしたと聞いて、すごいなあと思いました。問題を思いつく秘訣を聞けばよかった。
Lの解法が天才すぎて、こういうのコンテスト中に思いつきたいなあって思った。

オンサイト優勝者と各色ごとの優勝者には賞状と賞品のバナナが渡されていました。さすが「ゴリラの挑戦状」…

懇親会ではピザが出ました。美味しかったです。FORCIA社ありがとうございます！！！！

懇親会でホワイトボードアンケしてたんですが、参加者は競プロ歴~2年くらいの人が多かったみたいです。

感想

日程がJAG夏合宿と被っていたのですが、そのぶん普段オンサイトで会えない人とも交流できてよかったです。ゆるふわオンサイトに参加した後JAG夏合宿に行く人すげえ…

*1:https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d、今から思えばこれ解いてたら解けてたかも