DDPC2016参加記 - ぴろずメモ

予選

Tasks - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 | AtCoder

A問題

やるだけ。

B問題

$(A_i,i)$ でソートして二分探索しながらシミュレーションっぽいのをやる
バグらせまくってつらくなったので、愚直解とソートして愚直の2つで30点取ってC問題へ

C問題

考察を頑張ると、削除をしまくるか、ある程度置換をした後先頭への挿入or置換をする2パターンになって、
後者のパターンはSuffix Arrayが必要だと分かる。Suffix Arrayのライブラリを持っていないので愚直SAを書くもそもそもSA以外の部分がバグっていたらしい。
点数を取れず時間切れ。

97位だけど17卒に当たるので本戦参加権を得た。

本戦前

DDPC参加者の朝は早い。7時起き。

準備・移動フェーズは特に問題無かった。
しかし、会場は電源が不足しているらしく予め充電しておいた方がいいとの情報が入る。手遅れ。

会場は、基本的に机に電源が無かった。電源がどうしても必要になったら特定の席に移る必要があった。
席は一つの長机を2人で共有する形。広くもないが狭くて困るほどでもなかった。

本戦

開始の合図が開始時間に遅れて始まる。開幕コンテストページに繋がらなかったが数分で回復。

問題一覧
Tasks - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 本選 | AtCoder

A問題

やるだけ。

B問題

最小の時刻 $t$ を求める問題なのでまず二分探索して、ある時刻 $T$ までに総和を $X$ 以上にできるかの判定問題にする。
制約的に二分探索後の判定は貪欲っぽいと予想→貪欲でできた

ある時間に選べる料理はその前の時間でも選べるので、最後に選ぶ料理から順に考えると都合が良く、選べる料理で最もおいしさが高いものを選べば良い。
料理を時間の降順でソートしておき、時間を戻しながら適宜料理を優先度つきキューに入れ、美味しさが最大となる要素を取り出していくように実装。
AC。

C問題

B問題までがスムーズだったので順位が良かった。C問題は10点の部分点は自明で満点は難しそう、間の20点はDPっぽいので満点のヒントになりそうなので20点を狙う。
左から右へ見ていくDPは無理、区間DPもなんか違う。

括弧列 $A,B$ に対して、 $(A)$ と $AB$ の条件を満たす塗り方の数が $A,B$ の条件を満たす塗り方の数から計算できれば解けそう。
結局構文解析をしながら配列をマージしていくDPのようなものが生えた。

最初の提出が10点(WA+TLE)だったので、MODを取るミスを疑ったが見つからない。
sum += sum + ans[i]なる謎の記述を訂正してまだ10点。
無駄な部分を計算しないようにしてTLEを無くす、WAが残り10点。満点のケースでもTLEが無くなったので一応満点も見えてきた。

辛くなってきたので一度D問題とE問題を見に行く。D問題は部分点がなくさっぱり分からない。E問題は部分点はあるもののデータ構造不可避な問題文を開いた瞬間バイバイ。
C問題のバグをなんとかする方針にした。

なんとか考察ミスを発見した。
括弧列を連結していくパターンで赤に塗った数と青に塗った数の差は一時的に $K+2$ より大きくなるパターンがあることを見落としていた。
修正するがインデックスの変換をバグらせREを2回。
残り40秒で最後の提出。コンテスト終了の少し後にジャッジが走り切り、AC。やったぜ。