いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

KUPC 2017 京都大学オンサイト参加記

京大が好きなので参加しました(?)
Kyoto University Programming Contest 2017 - Kyoto University Programming Contest 2017 | AtCoder

参加まで

TL等で見かけるし誘ってもらっていたりしたので即決で参加した
申し込みが遅かったので申し訳なかった
コメントに575をかましておいたので一読ください

前日に天下一プログラマーコンテストがあり0完で太陽をキンキンに冷やして精神が逝かれてしまったのでD問題を解くまで寝ないような配信をした
www.youtube.com
結局ACまでに3時間程かかり、寝たのは4時になってしまった
ゆらふな氏、しょラー氏、Yazaten氏と一緒に行く約束をしていたので9時には起きるようにして寝た

京大まで

結果異様な眠さで起床AC
駅で合流して京大最寄り駅へ、近くのラーメン屋で昼を済ませる
f:id:ratetion:20171002020957j:plain
INF回チャーシューが食べれて幸せだったけど腹LE寸前だった

会場へ着くとJAG合宿その他でお会いした方が結構おられ、あいさつしつつ準備をした
ネットがつながりにくかったのでスタッフの方が頑張ってくれて快適な環境でコンテストに参加できた
結果自己紹介がWi-Fi接続タイムになっていてバジリスクタイムを彷彿としてしまったが、感情を抑え込んだ(何故?)

コンテスト

実は時系列で書きます

A問題

貪欲マシーンを使ってウィーンした、AC

B問題

木を登るときに倍か倍+1になってるなとわかったが、それだと数が増えていく一方だったので逆算しようと思った
そのまま実装したらAC

C問題

開いた瞬間辛いと思った
とりあえずハッシュの値を求めてみようと思って何故か10^1000を10^10と勘違いしてlong long intで持てると思って実装
当たり前のようにオーバーフロー:kinniku:
まあハッシュ値を求めたところで僕はそれをどうやって直せばいいか思いつかなかった

ここら辺で順位を確認するとCを飛ばしてD,Eに進んでる人がちょいちょいいて、なるほどと思いながらDとEを開く

D問題

とにかくテストケースを試してみた
なんだか2文字で全部行けそうな気がしたので、2文字敷き詰めを考える
特に2*2に着目して、これを敷き詰めたらどうなるか考えてみた
〇〇 〇〇 〇〇 〇×
〇〇 〇× ×× ×〇

全部でこれだけあるが、左1は周りを×で囲む必要が出来るためまず不可能
左2も周りに×と〇の配置が確定していき3つ置かざるを得なくなる
右1も同じようにして詰む
右2は同じものを並べていけばどんな大きさにも対応できることが分かった
これから2文字で常に敷き詰めれることが言えると思ったので、細かい検証をして、数えて場合分けして投げたらACして拍子抜けした
まじかいや、ほんまかいや
2完で残り4時間半地蔵とかにならなくてよかったなぁって安堵のため息をついた

E問題

鍵を記録しようと思ったが、開けた段階でどのカギを使ったか決める必要がないなと思って、使った鍵の種類だけ記憶することを考えた
記憶するのが困難だと分かった
次に全部箱を開けたとして、開けられない箱の分だけ引いてみる事を考えた
これもなんか難しそう管理がダメ
飛ばしてCに戻ることに

C問題(2回目)

さっきはオーバーフローしてしまったので、各項に注目した
サンプルがどのような動きをするか考えると、右のほうに行くほど大きいが、一つ左に進むときに、右の項を1減らして左の項にa足せばいいことが分かった
これを利用してなるべく左端に数字を集めるようにすればいいのではと思った
しかし調整が難しいので、雑に寄せれるだけ寄せた後で慣らすイメージでforループを2回回したらAC
なかなか気持ちよかった

E問題(2回目)

こういう問題で思考が詰まったときはどうすればいいかなって思って考えた
眠くなってきた、4完出来てしまった
もうゴールしていいんじゃないか?
と思ったけど考察すれば解けると信じて考えると、そういえばこの問題だけサンプル図示してないじゃないかと気付いた
サンプルを図示するとどうなるかと言えば、グラフっぽくなった
そしてグラフを見ると、辺と頂点の数の差があればすべての箱が開けられないと言えるなどわかってきた
どうも合ってそうなので実装したかったが、実装力が足りなかった
辛いなぁと思いつつ、もっと簡単に実装できるかもしれないから別解を探す旅に出た
彼に会うことは二度となかった

タイムアップ
解説を聞いて、F以降は異次元だと思ってしまった
まあ4完出来たのでよかったが、何より問題がすごくおもしろかったなと思った
賢い人はもっとうまく解くけど、僕のように考察をしまくれば何も知らずとも解ける問題があったりして、地蔵になるような事が無かった
問題も面白いし、多分AC出来なくても楽しかったんだろうなと思った

懇親会

焼き肉


適当に目の前の席に座ったら運営のあしぃ氏が運営の話や、競プロの話をわんさかしてくれた
まだ僕は始めたてだし、あまりオンサイトとかに参加することもなかったのですごくいい話が聞けたと思った

どの机でも競プロの話が飛び交っていて、当たり前なんだけどこんなに楽しんでてええなぁと思ってた
める氏と肉を頼みまくって腹LEした

帰路ではりか氏、T.M氏、odan氏らと駅まで歩いて向かい持ち前のクソトークとコミュ障を披露した(???)

まとめ

  • 楽しかった
  • 問題の質が良く、作問者に感動していた
  • 知り合いが増えてきて競プロやってる実感が沸いた、もくもく
  • 考察はとにかくサンプルを書く等すると捗る

運営のみなさま、参加者各位ありがとうございました
おわLE