今回は 66:54 でABCDEFの 6 完だった。 やっぱり実装の際に色々考えないといけないF問題で少し詰まっちゃったか。 でも別に悪い順位でもない。Gも考えたが解けなかったんでテンションがあまり上がらないのだｗ
偶数だけ見るforを回す。
count 関数を使って勝った数を求めて、インデックスをマイナスにしたものをいれるようなペアを作る。 これで降順にソートすると、インデックスについて要望通りのものがでてくる。
どうやるのがいいのかよくわからない。まず現在の最高点の人を求めておく。 この人は 0 である。他の人は、Aとインデックスをペアにしたものを降順にした配列を用意して、 総合得点が上回るまで入れていく。みたいな実装になった。9分はちょっとかかり過ぎかなぁ。まあでもWAがなかったから 良いか。
スライムのサイズをキーにしたmapを作る。これは現在のあるスライムのサイズの数が何匹いるかを記憶する。 サイズが小さい方から合成していって、すべてのサイズのスライムが1匹になるようにしたらその数が答えになる。
自分の実装は $O(N \log NK)$ とかで結構やばい計算量なんだけれども、なんかうまくやれば速くなる気もする。 1013msだった。
よくわからないDPをした。dp[x][k] ... ちょうどxで曲が終わる確率, k=0のとき曲1が終わる確率を示し、 k=1 のときその他の曲が終わる確率を示す。
こうすると、dp[X+1][0] + dp[X+2][0] + ... + dp[X+T[1]][0] が答えになる。
意味合いとしては、X+0.5 で曲が再生されている時、終わるのは X+1, ... , X+T[1] になるからだと思う。
遷移が単調なのでなんか速くなるかもしれない。自分はTLEギリギリで通した。
考察もくそもない。あるのは実装に対する考察のみ。という感じの問題だ。 まず荷物の位置と移動先の位置の位置関係を $X_B < X_C$ かつ $Y_B < Y_C$ にしておく。 なんか flip とかしてやっておこう。
まず荷物が曲がらないで移動できる際は高橋くんがその荷物を動かすための座標についてから、 単にマンハッタン距離だけで移動が完了する。 しかし、曲がる場合は、マンハッタン距離+2だけ移動しないといけない。 移動方向を変えるときに高橋くんが2マス移動しないといけないからだ。
あと、高橋くんが荷物を動かすための座標につくためにどう移動するかだが、 最短距離で移動するときにその先に荷物がある場合があって、この時、+2しないといけない(避けるため)。 これをちゃんと判定する。
さっきflipしたことで荷物を動かすための座標というのは、$(X_B -1, Y_B)$ か $(X_B, Y_B -1)$ しかない。 ここに移動するシミュレーションをしておいて、その後、荷物を動かす処理をすれば、 最小の行動回数は求まってくれる。
うーん、こういうのは慣れれば速く解けるはずなんだがなぁ。 ちゃちゃっと解いちゃって後半問題の考察に時間を回したいよね。
うーん、なんかうまいことDPできないかなと思ったんだけど、よくわかんねぇ。 エスパーしようとしないほうが良い。
Perf=2041 と上々ですね。まあ、それなりに迷わず実装はしたからね。 E 問題とかはかなり危なかったと思う。Nを遷移ごとに割ってたんだが、これは怖いｗ いま改めてinvNを作って解いてみたら 12, 13 倍くらい実行時間に差が出たのだ。 D の方は１秒かかっても想定解っぽかったかな。
Gがあまり解かれてないのを見ると、速解きできればもっと良いところを狙えたっぽい。 うーん、今回はFまでは実装をいかに速くするかっていうセットかな。 ICPCの問題集とか解いてみるかね。
明日はARCがあるらしい。前みたいに爆死するかねぇ。まあやってみる。
(2023/10/07 23:24)