今回は、ABCDEFの6完。 60:11。
S + " san" を出力。
ただ、$X$ でソートして区間の左の+8まで許すだけ。$X$ に $24$ 足したものをもう一つ作っておくと便利。
ただつながってる#を消すだけ。半分鬼気迫る状況だったのでガリガリ書いて早めにACした。
座圧して左から見て、区間の終了するのが早い順に処理する。
社用車に対する都市 $1$ からのダイクストラ。 電車に対する都市 $N$ からのダイクストラ。 これを各都市でmincostを足せば終わり。 得意な問題しか無いのに、Bが遅すぎたことををとにかく悔やんだ。
現在使ったセンサーの数を保存してDPするだけ。遷移が計算量ヤバそうな感じがするが、 使うと減るので大丈夫だろうと思ってやった。そうしたら通った。
ACしていないのでわからないが、後ろから f のところを見て、ペアで処理できる最小の o の位置を見つけれれば 良いのかなとは方針が立っている。後で冷静になって考えようと思うが、今は冷静さを欠いている。 何回か提出したがWAがでてそのままコンテストが終了した。
Perf=2243, 気持ちとしては、前回のARCのほうが出来が良かったと個人的な評価が立つ。 このセットはちゃんとパフォを取ってないと駄目なやつだ。
(2023/10/21 23:18)まあ、パフォは悪くないし、WAはでてないし。WAでてたら強制的に+5分だからね。 あと、F 危ないと思ってたんだけど、なんか、多分dp配列に値が入ってるのが min(k1, k2) 個くらいしか無いんじゃないか となんとなくわかった。だからTLEしなかったのかも。自分の解法だとややそれから増えるのでちょっと危うかったのは事実。 想定解を見てみたら、そもそもコストは何回使ったかでわかるんだから、k1をつかったときの k2 の最小を求めるだけで良かったみたい。 あー、見ますこういうDP。昔話をしたくなる。
G も盗み聞きによるとDPみたい。あー、DPでも行けそうだ。多分自分の貪欲は嘘っぽいな。どっかで死ぬケースがあるんだろう。 ちょっと後で解いてみたい。
(2023/10/22 06:37)