速解きをしただけの人その2、F難しいよ～
23:13 5完 194位
え、70分温めてた人なの？
A Apple
一瞬「DPか？」と思うけど冷静になると3個ずつ買っていけばいい
3個買う時はもちろん安い方で
(AC 2:52)
B Explore
やることは単純で、ボーナス部屋に入ったら+、移動の時に-するのをシミュレーションするだけ
最初「≦」と「＜」を間違えてたけど、サンプルに「1から2に移動できません」ってあったので確認したら気づいた、あぶないあぶない
(AC 6:52)
C Belt Conveyor
愚直にシミュレーションします
同じマスに2回きたら、結局同じルートを通るので無限に回ります
言うことあんまりないね
(AC 11:02)
D Iroha and Haiku (New ABC Edition)
初期ARCにあった問題のオマージュでエモい
全部正なのですごい考えやすい
値が3つあるんですが、1個の場合を考えてみればよいです
区間[l,r]の和がX -> sum[r] - sum[l-1] = X
の典型ですね
なので、sum[l-1]の値があるかどうか判定できればよいです
これを3回繰り返すだけです
累積和の値をsetに入れておくと割と簡単に書けます
(AC 14:59)
E Warp
とりあえずdp[x][y] := 座標(x,y)にいるときの通り数みたいなDPが思いつきます
ただ、すごく単純に考えると取りうる経路は3^N個あってやばそうな気がします
でも、選択肢1->2の順番で動くのと、選択肢2->1の順番で動くのでは到達地点は変わらないので、実は少なくなるかなとも思います
どのくらい通り数があるか考察してもいいんですが、愚直書くだけならすぐ＆最後のサンプルがほぼ最悪ケースなので、とりあえず愚直を書いて遅かったら考えることにします
書きます.......1700msなのでＭ大きくてもギリギリなんとかなりそうです！
ちょっと怖いのでmod回数減らすとか小手先の高速化をして投げると通ります
やったね
(AC 23:13)
F Manhattan Cafe
制約と内容からいかにもDPっぽいです
ただ、dp[i][x][y] := i番目まで考えてdist(p,r) = xかつdist(q,r) = yを考えると重すぎる気がします
もうちょっと考えると、abs(p[i] - q[i])分のコストは必ずかかるのでここだけ決めればいいんじゃない？って思います
そうすると、残りは余った数をどっちかに動かすだけ...なんですが、動かしていい場所・動かしてはいけない場所(端っこじゃないなら動かせない)まで管理するとDPが爆発します
うーーーんと考えていると、コンテストが終わりましたかなしい
解説読むと斜め累積和...なるほど勉強になりました
(AC 間に合わず)
G 012 Inversion
なーんか見たことあるんだよねこれ、って言いながらPASTやABCを漁ってないな～となったら、ACL Practiceでした(完)
めんどくさいなーと思ってやってなかった...
総括
早解き黄色しかとれない
