Eまで五完。
コンテスト後のツイート
G x=sum(A)/Nとすると、各要素をxかx+1にしたい。x+1にした個数とかをもってDPかと思ったが上手くいかなかった。今までで使った最後のA[i]ももって雑にDPしたがWAが出た。
— titia (@titia_til) June 24, 2023
F - Virus 2
解説AC。
（感染した日, 感染した場所からの最短距離）を持つダイクストラでやった。これだと、「l日以降でx以上の数字がXに表れる一番最近のindexはどこ？」に答える必要があったので、セグ木二分探索を使った（使わなくてもできるらしいが、よく分からず……）。
ダイクストラすることは明らかで、どんな解法でもできそうに思えるけど、実際に実装しようとするとつまる……みたいな問題だと思う。
多分、解説見なくてもごちゃごちゃやっていれば解けたと思うけど、素早くこなすためにはどうすれば良いのかね。
G - Approximate Equalization
解法ツイートを見るとツイートで書いた内容で大体あってそうで、
・x+1にした個数をもってDP
だけ持てば良かった。
それだと次の数字が何か分からない（一意に定まらない）気がしてしまったが、累積和を取っておけば、そこまでで使ったxやx+1の個数が分かっているため、差分計算で求まり、一意に定まる。
制約を見ても二乗DPできそうなので、ツイートした内容のところまでいけば、正しい解法に至ることはできそうなのにねぇ。うーん。
なお、解法が分かったつもりで実装しようとしたら、再度、「やっぱり次の数字は分からないのでは？」と思ってもう一度再考してしまったし、その上、一番最後にx+1を使う場合を考え損ねてWAを出したりした。
解けなきゃいけない問題だったと思うのに、この様はまずい……。
0 件のコメント:
コメントを投稿