ABC315 (キーエンスプログラミングコンテスト2023夏)

5完60分+4WA 931st performance:1531
1ヶ月で100近く落としてるんだが俺なにかやっちゃいました？（何もしてないのでは）
atcoder.jp

A 正規表現使えば早いと思いつつ正規表現がぱっと書けないのでsetなんか書いてしまうの、ダメ。まあここは縮められて10秒とかだろうが (21:01)
atcoder.jp

正規表現
atcoder.jp

B 中間の日数を求めず条件式をぐだぐだ書いてしまった。奇数だしさっさと求めたほうがよい (21:06)
atcoder.jp

C なぜか味が異なるときのおいしさを(s0+s1)/2にして1WA、テストケースで落ちないのが悪い (21:17)
atcoder.jp

C++20だしrangeを使ってみたい
atcoder.jp

D setで消えた行と列管理してシミュする。消去判定を愚直に縦横で回して2TLE。落ち着いて色を元に判定させてAC。setで管理せず毎回全部の行・列調べても多分間に合う。 (21:50)
atcoder.jp

構造体を作って、色々関数作って、行・列の消去判定をO(1)でやるやつ
atcoder.jp

E 見るからにトポロジカルソートなのでコピペって帳尻を合わせる。無思考でdsuで塊を管理して、1を含むやつだけ出力。1の先を出力してしまい1WA。よくよくトポロジカルソートのコードを見れば、塊ごとにDFSしてるだけなので1からDFSするだけでよい。(21:59)
atcoder.jp

1からDFSするだけのやつ
atcoder.jp

F DPっぽいなと思ったんだけどパスできる頂点の個数をO(N)と見積もってしまいやめに。ダイクストラ法っぽいやり方でいけるやろうと挑戦したが時間が足らず10:39提出TLE。(チェックポイント,無視数)を頂点とするグラフでダイクストラするのだが、単純にやると枝数が多くなりすぎてTLEする。最初に全チェックポイントを巡るルート長を求めておく。各頂点からは、いまいるチェックポイントの先のチェックポイントをそれぞれ、コストを求めていく。そのコストが最大コストを超えた場合はそれ以上先のチェックポイントにいかないようにすればよい（なんかぎりぎりすり抜ける例とかできそうだけど、今のテストケースはこれで通るぜ！）。C++20で900msぐらいで通る。訪れた頂点の管理を（無視数の見積もりをせずに）setで管理しているが、適当な大きさのvectorにするともう少し速くなる。

vectorで管理
atcoder.jp