Joeの精進記録

旧:競プロ練習記録

ゆるふわオンサイト2に参加した

www.hackerrank.com

before contest

普段会わない人と新宿でご飯でも食べようと思ったが、12:30頃に起床。そのまま会場へ向かう

contest

A, B, Cを開いて解く。速解き勢がいなかったためかFA。ちなみに見せ場はここで終了です

D: n-dwich box 最初、正規表現でも使って'||'でsplitして#の個数を数えようと思ったけど、'||'で愚直に区切るのはやばいことに気づいて時間を溶かし連続FAがきれる

E: usagi vs kame 実は入力が単調だったのでO(N)で解けたらしい。最近鈍っているのでこういうのでつまづきがちだと思っていたがサクっとかけたのでよかった

F: mneme game C, D, Eより簡単だった。三角数でmodとるみたいなことをやる

G: double range cards はじめ、カードが重なってる領域求めるのが面倒すぎると思ったが、よくよく考えると求める必要がなかった。

H: gori uho game 深さ優先探索を愚直実装した。TLE心配だったが爆速だった。冷静に考えればだいぶ枝刈りされるはず。

ここまで、経過時間は53分でしたが、多分1分以上考えた問題がなくて、だいぶ実装コンテストな印象を受けた。しかしコンテスト終了までこのままの点数でいることになるのである…

I: pino assort

制約を誤読してしまって、別々の箱に入っていると思っていた。pino assort買ったことねえ… にぶたんみたいなことをすればいけると思ったが、これに20分ぐらいかけてしまったため、残りの問題が楽そうだったらそっちやろうと思ってとりあえず飛ばす。

J: swapping paths さすがにDPをするだけなんだけど、端に進めない場合があるので、数学ゲーではなくて、かなりしっかりとしたDPを書く必要があるっぽい。これを実装するぐらいならIをやると思って飛ばす。

K: fuzzy search queries Suffix Arrayのcount_substringの実装の中に現れるlower_bound, upper_boundの実装を流用すればそのまま解けそうという気持ちになる。点数的にもおいしいしこれを実装するのが一番楽だと思い、これを解くことにする。 Suffix Arrayを10000年見ていなかったため、単にlower_boundの結果から一つずつarrayをさかのぼっていくことをすればよかったところを、lower_boundの実装ミスを疑ってしまい、永遠にデバッグをしてしまう(普通にぼくの実装への勘違いが原因で、SAはバグっていなかった)。厳しい。蟻本もう二度と見なくていいかなと思ってたけど蟻本に乗ってたらしいし普通にもってこりゃあよかった。

L: 残り時間がなかったので1分ぐらい考えて、わからなかったので飛ばした。

結果

2400点でいろいろな人に負けた

after contest

  • そすうささんと初めてしゃべった
  • matsuさんとprdさんと、高速化の仕事ってやばくないかという会話をした
  • matsuさんと、テストケース作成は闇!wやはりmod数え上げ!という話をした
  • ぷにくんに中本食べすぎじゃないかと心配された
  • う し た ぷ に き あ く ん 笑 っ て 何 ? 笑って聞かれた。これ最近のオンサイトで毎回聞かれる。何?

個人的にあの問題セットは頭と手が両方ついている状態でも2:00で解き終わる気がしなかったので時間は2:30でもよかったんじゃないかと思いましたが、全完者もいましたし結果としてはベストな時間だったのかなと思うなどした。

問題あたりの考察要素は前回のゆるふわコンのほうがあった気がしますが(とくに前回のラストの問題で、距離の問題を最小費用流で解くものは初めて見て感動した)、今回もコンテスト・懇親会ともに存分に楽しめました。ありがとうございます。

そういえば2週間後ぐらいにGirigiriコンを開くかもしれません。コンテストを開くか開かないかのどちらかです。