はじめに
KUPC 2020 AutumnにICPCチーム,state_of_the_art (sotanishy, renjyaku, mugen1337)で参加しました.
結果はABCDEFmの6完+m部分点でした.
画像ではMが見切れています.
時系列
最近土日は大学図書館が開いていないのでWi-Fiを使えるよくわからない貸しスペースみたいなところに集まります.みんな5分遅刻して結果的に全員同時に集まります.
基本的に,いつもrenjyaku, sotaくん, 僕の順でmod3で問題を見ているので,今回もその作戦で行くことにしてKUPCスタートです!楽しみだなぁ~.
ちなみに僕が苦手な問題はパズル,数え上げです.
A
renjyaku「書きます」B
sotaくん「解けました」
よしよし.イイカンジですね.この調子で僕もCをね...C
Cをみましょう
え?
ちなみに,僕の苦手な問題はパスル,数え上げです.(2回目)
困りました...D
「C,アカン.誰か任せた.(無責任)Dを見ます」...
「Dもアカン...パズルみを感じる...」
帰っていい?
まぁでもCよりは解けそうなので解きます.
とりあえず偶数は自明に作れるのでどうでもいいですね.
Bを書き終わったsotaくんと一緒に考えると,平方数の倍数は作れそう.ということに気づきます.
1, 3, 5
9, 11, 7
17, 13, 15
という流れでn=9が作れることに気づき,同じように1ずつずらして並べることで平方数は作れます.
ここら辺で,もうそろそろ十分じゃない?1回落ちてから考えない?という話し合いをして平方数の倍数なら作ってそれ以外はimpossibleな実装をします.
落ちます.(悲しい)
ある程度をx2のブロックを何個か並べて作って,そのあとに残った個数がxの倍数かつ,偶数倍ならいいことに気づきます.
ここらへんでもう十分じゃない?落ちたらまたその時考えない?ということにしてまた実装します. 通ります.(嬉しい)
こんな通し方でいいのか...E
renjyakuをCに据え置きにして,僕とsotaくんで先に進むことにします.
僕がDを書いている間にEを読んでくれたsotaくんから,DPじゃないか,という案をもらいます.
僕も読みます.「DPやんけ(単純)」
さぁ遷移がまだ二乗なので落とすぞと考えます.
...
無理.
悲しいね.もはやこれまで.
ここらへんで僕が「二分探索じゃね?」「いや二分探索してもDPの遷移変わらないし嬉しくねぇ~」を毎秒30回言うようになります.
ところがどっこい,自明なDPと二分探索を組み合わせると,値でDPしていたのがbool値でDPできるようになり,(雰囲気伝われ),イイカンジにイイ感じにできることに気づきます.
僕が書いて無事AC.
DPにしか見えないけどそんなことないとてもおもしろい問題に感じました.好きです.F
見た瞬間,僕が「不可能」と叫びます.
でも,僕が広義単調増加の文字を見落としており(太字で書いてあるやが)右下に点を拾っていくだけでいいことをチームメイトが教えてくれます.
僕が「可能」と叫びます.
おおまかな方針を立てて細部詰め切れずに放置して一回順位表と他の問題を見ていると,Cで無事満点を取って帰ってきたrenjyakuが詰めてくれました.え,すごい.
僕が引き継いでAC.感動です.G
Fでちょっと詰まったタイミングで,Gを僕が読みました.
...
僕の苦手な問題はパズル,数え上げです(3回目)
この位置に置いてある数え上げ,無理みがすごい.放置.M
僕とrenjyakuがFをわちゃわちゃしている間に,Mをsotaくんが取り掛かっていました.
sotaくん「OEISを使うと,カタラン数がでてきました.3乗は自明に書けました」
え,チームメイト,優秀...
sotaくん「部分点とりあえず欲しいですね,3乗から2乗に落としたいです.この遷移,畳み込みですか?NTT使えますか?」
ぼく「はい.そうだと思います.」
え,チームメイト,優秀...
無事部分点獲得!やっぱりMがここまで考えられたら解きたいですね.ということになり,Mをみんなで考えます.
ここらへんで僕もちゃんと脳が走って仕事をします.
ぼく「もしかしてK項目を0にしたカタラン数を係数とした多項式のN乗になっていませんか?それ」
と,有効な考察をひねり出すことに成功します.
でも多項式をN乗するなんて無理ではないですか?
巷でよく聞くFPSとかいうのでうんぬんかんぬんをするとうまくいくのかなぁとか思いますが,履修していません
sotaくん「じゃあ繰り返し自乗できますね」
え,チームメイト,優秀...もう完全にお祭りムードです.
KUPC最高!一番好きなKUPCです!
やったぜ!最高だ!空も飛べるはず落ちます.え? 1e6にlog2個はダメですか...そうですか...
終了...
コンテスト終了
MはやっぱりFPSでできるみたいですね
多項式のpowはlogが1個落ちてlog1個でできることをコンテスト終了後に知りました.びっくりです.
まぁライブラリは仕組みがわからなくてもどのライブラリを使えば何ができる,というのを一通り知っておくのもいいかもしれないですね.
まぁでもチーム戦でらしいことができたのでよかったです.
最高に楽しかったです.
やはりKUPCいい問題が多いと思います.
EFは特に解けたとき「あ~~~おもしっれ~~~今,俺は生きているぜ~~」となりました.
運営の皆さん.本当に楽しいコンテストをありがとうございます.