KUPC2019参加記
これはなに
KUPC2019京都オンサイトに行ったので参加記を書きます
コンテスト前
12:30に着けばいいやろ！wとか言ってたら12:00集合とか書いてて真顔になったが、阪大黄色コーダーのsnowくんも同じくらいの時間に着く予定らしかったので安心した（運営の皆様におかれましてはご迷惑をおかけしましたことを深くお詫び申し上げます）。
snowくんと合流して京大に着いたらわりとギリギリだった。
「上下黒づくめの聞いてもないのにアスナについて語りだすオタク」みたいな服装だったので、スズメバチに絡まれてめっさ怖かった。
部屋についたら阪大生がめっちゃいてウケた。スギノキさんが誰か把握した。
てんぷらさんがコンテスタントで不正を疑ったが、不正しなくても自明にオンサイト一位になれる実力をお持ちなことに気づいた、それはそう。
自己紹介パート
急遽自己紹介が始まり、「うしたぷにきあ王国から来ました」と名乗る人が二人（正確には一人とうし一頭）いて、時代はグローバルだなと再確認できた。
ところでうしたぷにきあ王国ってどこですか？
「大学で一番スマブラが上手いと思います」とか謎のアピールをする人がいたので、「この中で一番数学ができないと思います」とか逆イキリをしようかと思ったけど、あまり面白くないのでやめた。
こたまねぎくんがこたつがめさんを詐称していておもしろかった。じゅぴろ笑い声うるせえ
コンテスト中
とりあえず前から考えた。
A問題
普通に200点の難易度だったが、少し緊張して手が止まった。深呼吸すると手が勝手にmax_elementを書き始めたのでそのままAC(2:57)
B問題
これに時間をかけているの、水色失格だと思いませんか？ゆるせねえ。
お腹が痛かったのでトイレに行って十分ほど無駄にしたことを鑑みてもなおひどい。
サンプルを見ると連結成分で繋がっているものをまとめてしまえば、ただのナップサックということがわかる。
Union-Findの扱いに慣れていると品物をまとめるパートが書けて、EDPCをやったことがあるとナップサックパートも書けるんだよね。AC(38:32)
C問題
とりあえず手でK == 1の時の最適解を考える。が、できない。{1,2,3}とかに惑わされ、よくわからなくなってきたので一度全部の問題を見る。
D問題
タイトルにゲームと書いてあったので飛ばす
E問題
問題分にAliceとBobが書かれていたので飛ばす
F問題
おもしろそう。
とりあえず分散するのではなく一点集中するのがよくて、DPっぽい感じがしたけど状態をどう管理すれば良いのかわからず飛ばす。
G問題
天才構築か数独ソルバみたいな枝刈探索かどっちかだなと思って、制約を見て天才の方だと確信。飛ばす。
[H, L]問題
解かせる気がありますか？ないですね。さようなら。
D問題
Cが解ける気しなかったのでDを渋々読んでみると、ゲームではなく数え上げであることがわかって嬉しくなる（は？）
手で実験して45分ほど時間を潰し（は？）、組み合わせを全列挙する実験コードを書いてみる。
それで適当に遊んでいると、10101010... というように交互に勝敗が並んでいるものは必ず1であることがわかった。
更に
1 11 111 1111 11111 111111 1111111 11111111 111111111 1111111111
の場合の数を数えてみると、1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 となった。
「規則性がないと、解けっこないだろ」というお気持ちでOEISに祈りを捧げると（ちなみにこれが人生初OEISなので実質初詣）、徳が高いので報われた。
カタラン数、こたまねぎくんが口走っているのを聞いたことがあり、これは競プロに関係する数のはずで、つまり正解方針です。やったね。
これをどうすんねんと思いながら、試しにサンプル2で1か0が連続している長さごとにカタラン数をかけていくと、2100になったので勝ちを確信。
よくよく考えれば10101010...も延々1がかけられていると思えば理解できて、あとはカタラン数を求める漸化式を適当にググって念の為うしさんのmodintを貼り、AC(159:14)
C問題
DよりCの方が解かれていたので、解きに行く。
無限時間かけて実験をした結果、k == 1の時は {1, 3, 9, 27, ...} というように3の累乗を持つと良いことがわかった。
k != 1の時はassertさせて出してみると、とりあえずWAが出なかったのでk == 1の時はOK。
k >= 2の時を考えて何回か嘘にはまったが、
k == 2 の時は {1, 1, 5, 5, 25, 25, ...}
k == 3 の時は {1, 1, 1, 7, 7, 7, 49, 49, 49} が最適であることを泥臭い手実験の結果発見した。要は累乗していく数が3, 5, 7, ...と増えていくだけで、3+(k-1)*2とかで表せる。
あとは累積和がmを超えるまで要素を足していく処理にこれを追記するだけなので、AC(251:34)
F問題
解けそうな感触だったが解けず......残念。
コンテスト後
懇親会に行けなかったので、じょえさんとうしさんに挨拶した。
これを布教するのを忘れていたので、ここに貼っておく
うしさんのライブラリを使ってACした時に見る動画（関西ローカルCM）
結構たくさんバリエーションがあるので探してみてね
