AB二完という過去最低（灰パフォ相当は初めて！）の成績。
C - Final Day
今までの合計点でソートして大きい方からK番目の値が基準になる。今までの点数+300がそれ以上かで判定。
基準値を得るところで、ソートしたものではなく元の数列を見ていたためWA。そして、コンテストが終わるまでそれに気付けなかった。多分、質問に「"in the top K" means……」という文章があったため、「上位 K 位以内」の解釈がおかしいのかな……と疑っていたためだと思う。
自分のコードも何度も見直したつもりだったが、誤読の可能性の方が高いと思っていたため見直しが浅くなっていたのかもしれない。
D - Linear Probing
最初、左右を管理するリストを付けばできると思ったが、それだと1ケースTLE。(1, x)というクエリが繰り返しくるとき、左右の管理だけでは難しい。
なので、Union-findを使えば良いと思ったが、上手い実装を思い付けなかった。
冷静になれば、xとx+1をUnioinするとき、x+1側の最大値を得る配列を用意しておけば簡単に実装できる。
E - Integer Sequence Fair
問題を開いてすぐ、この記事を見に行った。
これで良いのだが、pow(a, b)がa=b=0のとき1になるというのに注意せねばならなかった。このコーナーケースは盲点でした。
今回、コンテスト中冷静じゃなかったけど、Dまで普通に解けていたとしても気付いたかどうか……。
F - Stamp Game
解説放送を見てAC。
実装の簡単さのため、縦横ともSparse tableを使った。
二次元Sparse tableの復習もしようと思ったけど、横向きにSparse tableを作っておき、縦方向へは、それぞれのnodeについてSparse tableを構成、というので良いのかな。（そう考えればそんなに混乱しなそう？）
G - Digits on Grid
解説放送を見てAC。
DPのキーとして何を使うかが重要だが、「同じ数字を取りうるものの集合」を使えば良いということですね。
ところで、この問題が類題な気がする。前に解説を読んでも理解できなかったのだけど、今なら解けるはず？
ACできたらその旨を追記します。 → ACできました！ なお、行列累乗で扱っている行列の行数が解説のものと1違ったので、少し違うことしているみたいです。
H - Histogram
解説放送を見てAC。
・まずAでソート
・愚直なDPを書く
・式の形を見ると累積和が使えそう
・累積和を取ってまとめるとConvex Hull Trickが使える
という流れ。難しいけれど、典型的な処理を繰り返せば解けるという意味で、解けなくてはいけない問題だと思う。
式を見ても累積和に気付けなかったこと、Convex Hull Trick (CHT)の具体的な処理を忘れていたことは反省。ただ、Convex Hull Trickの書き方は結構使い回せるようなので、使うと分かったら以前の提出を参考にするようにしたい。
今回の提出やDPまとめコンテストZの提出で、最小値の場合を書いている。
ライブラリ化するのも有りか。
0 件のコメント:
コメントを投稿