ICPC以後競プロをあまりやっていなかったのですが、やはりオンサイトはワクワクします。
予選
予選A→頑張ったら構築ゲーに勝利して通過
予選B→寝てた
予選C→ボロボロだった
予選Aからちゃんと出ておいて正解だった
本戦
前日十分に寝れず、つらかった。
A問題
正規表現👊 一発AC。
B問題
ABC...のようなパターンしかない。一発AC。
C問題
最小値の最大化を最大値の最小化と思い込みタイムロス。
最小値をk以上にできるかという判定問題を考えれば、2-SATに帰着できることは分かったがどう考えても500点の難易度ではないので実装を考えた。
結局色々考えたあげく、2人の間の関係を(同じ符号のみOK/異なる符号のみOK/どちらでもOK)の3つに分け、dfsして解いた。2-SATに還元したほうがマシだったまである。
D問題
どう考えても順序が必要なので、H順,P順がダメな事を確かめてH+P順を考えたがうまく証明できない。
めちゃくちゃ色々考えて詰まる。
残り1時間くらいになったので仕方なく他を読む。
F問題
Eは回文というキーワードを見た瞬間無理と感じたので、構築ゲーのFを考える。できなさそう。残り30分くらいでDに戻る。
D問題
実験でどうもH+P順が正しそうなのでDPを実装中。バグって時間切れ。
終了後15分くらいで解けた。
4完を目標にしていたが3完でレートも40以上減ってとても悲しい。
Dの貪欲部分の証明
2以上の最適解が存在すると仮定する。
この時、座布団を置けない人は後ろに固めても最適である。以降座布団を置く人のみを考える。
連続する2人に注目する。この2人が座布団を置く前の座布団の枚数を,先に座布団を置く人を
、後に置く人を
とおく。
この時次が成り立つ。
かつ
ここで、と仮定し、この2人の順序を入れ替えても同じ人数で座布団をおけること、すなわち
を示す。
ゆえに、座布団を積む人は昇順に並べ替えてもよい。
トーナメント
本戦が3完で冷えたため、もっとも下のグループ6に入った。
Round1
なぜかC,D問題の2問。
C問題を開く。カッコ列と言えばDP。
カッコ列１つでどうこうするのかと思い込み誤読する。
素直なDPのだとやばいが、カッコ列に対応するxy平面上を動く点を考えると、原点近くの5つくらいしか要らないことに気づいてなんとかなった。
遷移を書くのがややしんどかった。
D問題は最小の部分点（パスの場合）を目指したが、ギリギリ提出してWA。
勝ち上がった。
Round2
A問題を読む。概要を理解するのが少し難しい。
部分点をよく読むと200点はただ最小全域木を実装すれば取れることに気づき、提出。
Aでさらに点を取れる気がしなかったのでBへ。
B問題、k=1の操作が左シフトなことには気づくが、k=n-1は全く思いつかなかった。
最初の部分点を幅優先探索で取ろうとしたが時間切れ。
200点のみだが早めだったため勝ち上がり。
Round3
Round2までの順位表から、グループ6では早解きだけしてれば勝てそうというのが分かったので、とにかく小さい点から素早く取る作戦にした。
Eの200点(1): 愚直に距離（演算はmin）を計算するだけ。面倒なのでダイクストラを貼った。
Fの200点: bitDPで全列挙して条件に合うやつをカウントするだけ。
Eの200点(2): コストが2の辺のみで連結成分を考えて、うまく計算するだけ。UnionFindを貼った。
余った時間は祈ってた。
結果作戦大成功、2位でトーナメント勝利。
１位は本戦なぜか0点の赤コーダーなので実質優勝（？）
4年間CODE FESTIVALに出て壇上は実は初めてな気がする。本戦がダメだった分ちゃんとパフォーマンスを出せて良かった。
リレー
チーム内の本戦順位は下から2番めだったが、開始直後に雑に問題を取ったのでD問題を読んだ。
そこそこ考えたが、1と2を含む連結成分のうち大きい方に残りの頂点全部くっつけてクリークにすればよさそう。
と、考えた所でJ問題の公式が降ってきて実装を任された。
万が一公式が間違っていたら大変なことになるので不安だったが、断れないのでやった。
実装中にキーボード操作が一切効かなくなるトラブルが発生してパソコン再起動（つらい）
実装もintをintで割るなどして3WAくらい出し、パソコンスペースで時間を食いすぎてしまった。
後半戦で実装が詰まる状況になったのでこれは良くなかった。
JをACしてからは隣のrianさんとEの考察をしていた。式変形していたらそれっぽいのが出てきたので、rianさんと確認し、海外プロのお墨付きも貰って良さそうだとなった。
Eは通ったので一安心。
実験ゲーや構築ゲーが残っていなかったので残り時間は祈っていた。
チームとしては8完で終わった。
