3完 76位で予選落ちです
ラストイヤーだったのですごい悔しい
チーム
myau(ぼく) : 一応レートが一番高いのでチームのエース枠、高難度典型を早めに見抜いて倒すことを目標にする
hashimoto76 : 水色だけどARC適性が高めなので、ぼくが苦手なひらめき系と序盤をお任せする
nemurineko : 新入生の中でサークルに多く来てくれた子を連れてきた、戦力としてはあんまりかも、話すなかで何か出てきたらいいかなと
立ち回り
例年の国内予選は、3完早解きで通っていた＆ぼくが早解きタイプなので、3完をできるだけ速くするのを理想にして、D以降は解けたらラッキーくらいのつもり
割り振りはA+B : hashimoto76 C : ぼく
本番
Cを見つつ、方針を立てる
hashimotoくんにAを聞くと、「余裕です」とのことなので安心して任せる
CはN,Mが中途半端に大きくて、どうしようかと考える
休みは細かくした方がいいのでは？と思い、休みの分割回数を最大化することにする
少なくとも最適解の構造は、
休み・精進・休み・精進 ... になっているはずなので、これで書いてみる
NやMが0や1のときは怖いので場合分けをする
嘘貪欲ぽくてこわいな～～って言いながら実行！
とサンプルの1つで落ちる
よくよく考えると、休みを細かくするのが最適ではない場合もあるっぽい
うーんと思うが、すぐに休みの個数を決め打ってもTLは問題ないことがわかる
そうすると、最適な場合を漏らさず探索できそうなのでACを確信する
あとは実装すると無事AC！
Aは通っているけど、Bの実装が重そうなので、ぼくもBを書く
愚直にやるだけなんだけど、各人が持つカードをどう持つかで実装難易度が変わりそう
ぼくはmapで持つことにしました
サンプル合わせるとhashimotoくんがちょっと前に書き終わったらしいので、出力が一致していることを見て通してもらう、無事AC
順位表をみると、40後半くらいでDによるな～と思いつつDをみる
数え上げでまあ手は出そうな範囲だなと思う
N,Kの制約からO(N^2)のDPかなーと考える
ちょっと考えると右端rを固定するとどこまで区間をとれるかわかるんじゃないか？と思う、でも話してみると難しいケースがあることに気づく
あまり進展がなく、考えているとhashimotoくんが切るための条件・切らなくてもいい条件を考えてくれて、それを単純に書くとかなりサンプルが合うのでそれを詰めることにする
はじめは隣り合うところだけ見ていたけど、それだけだとどうしようもないことがあり困る...あとそもそもできないのも検出したいけどその条件が分からない
大転換必要か？と思って有向グラフを考えたりするけど、なにもわからず
最後にhashimotoくんが惜しいところまで考察してくれたけどWA
3完で通過できるという読みが外れた＆Dを解ききれず、完敗でした
総括
ICPCに対する努力不足と単純な競技プログラミングの実力不足
ICPCはもう出れないけど、どこかでもっとすごい活躍をしたい
これからも競プロがんばるぞ
