JOI 2020/2021 二次予選ポエム
419点 本選確定したのでポエム（本番中の思考回路）
問題のネタバレを含む
駄文さん
本番前
戦略としては、3時間あるので "バグらせないことを最優先" 、大抵グラフだったりDPだったりするので "一つの方針をしっかりと考察する" みたいなことを考えていた
前日は午前5時くらいに寝た（なんで）
緊張でお腹が痛くなったのでトイレに行こうとしたら、ちょうど壊れてて使えなかった。近所の公衆トイレまで走った。くさかった
本番(0:00~1:00)
A問題を見る。簡単にシミュレーションするな～となって、バグらせないように丁寧丁寧に実装した
一発で通ったので結果的に早くなった（えらい）
B問題を見る。なにこれ
去年の予選Bくらいのお気持ちでいたので「はいはい貪欲ね～」と未証明貪欲を頑張って書いた
未証明なので、実装中にいろいろ反例が出てくる。それで盛大にバグらせる。50分くらいかけて書いたのを提出する。4点が返ってきた
本番(1:00~1:25)
1時間経って104点やばいとなって、C問題を見る。「えっこれ不可能じゃないですか」「都市は2個ですが？」
グラフ+DPだな～と言いながらグラフをいい感じに作る方法を考える。当然辺の重みは動的なのでうまくいかない
実装バグらせそ～と言いながらダイクストラとかの方針を考える。むつかしい
ここでサンプル2をよく見る。イベント1つ無視してるじゃん。ここが怪しそうなので考える
よーく考えると、イベントを無視する意味は皆無なので、貪欲にイベントに参加することができる。
かなり扱いやすくなったので時系列順のDPを考える。(DP[i][j]:=都市iで時刻jのときのイベント参加最大数)がうまくいきそうなので書く。サンプル通る。ACした～。よく考えたらグラフじゃなくないか？
D問題を見る。沙耶花さんの問題に似たようなの（yukicoder No.1297）あったな～と思う
左から,右から貪欲にいい感じに点検項目を埋めていく方針を少し考えたけれど、D問題でただの貪欲は出なそうだったし、大工の座標とかの管理でキツそうなのですぐに捨てた
問題文をしっかりと読む。「最短で何分」のワードからにぶたんが連想される。明らかに単調性があるので時間を決め打ったときに判定をO(N),O(NlogN)あたりでできれば解けそう。解けるわ
右から貪欲に大工を割り振っていけばなんかうまくいくので、解けた。ここまでで1時間25分
本番(1:25~2:45)
E問題はややこしいので放置してB問題に戻る。放置したのでDFS/BFSが見える
最近DFS書いてないな～と言いながら30分かけてDFSを書いて提出する。64点???????????????????
(N<=13,Q=1)のケースが通って(N<=5,Q<=100000)のケースでWAが出るのわけわからん。嘘解法かもな～(笑)
ここらへんで残り40分の方針を考える。確実に点数を重ねるために E(7)→B(10)→E(38) の順で解くことにする
E(7) を10分くらいで通して、B(10)を考える。なんで通らないのかが全くわからない。バグらせない戦略どこいったんだ
(N<=5)に限りDFSが通らないのでBFSを書く(???????) いろいろバグらせながら実装する。WAがなくなった。TLEが1個
ここで天啓(マジで)が降りてくる。(N<=5)のとき精々Sは1000通りくらいなのでメモ化ができる。これでB(10)を確保して、ここで381点
本番(2:45~)
E(38)を急いで考える。少なくとも今の情報で確定できるものだけ探索したいな～となって、O((N+M)^2)が許されるのでベルマンフォードのお気持ちが使えることに気が付く。実装して、残り7分
確定していないところどうしよ、"適当な奴をスパイにして探索" を繰り返せばなんかいい感じに計算量落ち着いてくれるやろ。WA?????????????
スパイだと決めつけるのではなくnotスパイとも決めつける。必死こいて実装とバグ取りをして提出してE(38)が取れて419点。あと23秒..........
