A一完で終了。レートを大きく下げてしまった。Cは解法はあっていたので、ACしなくてはいけなかった。
A. Basic Diplomacy
時間がかかってしまったが、結構思いつきにくいと思うので仕方ないか。
「m/2の切り上げより多い回使わないようにする」というこの値が重要。どういうときダメか、と考えると、友達の人数が少ないときの方がダメになりやすいが、全日程で友達１，2の二人を選べるなら、その二人で分ければOK。
じゃあ、その二人のうち一人を選択しなくてはいけない日が、ダメにならないギリギリまであった場合どうか、というとそれでも他の日程で別の人を選べばOK。
これがギリギリのケースなので、自明なダメなケース、つまり、一人しか選択する余地がない日がダメな回数ある場合を除けば良いとなる。
ギャグ問題といえばそうだけど、「m/2回」という数字を見て、ほとんどの場合大丈夫なんじゃないの？ という直感を持つことが重要、という意味では発想が必要な問題か。
B. Playlist
「dequeを使う」というツイートを参考にAC。
次に処理すべきindexをdequeでもってシミュレーションできるのですね、なるほど……。全く気付かなかった（し、言われても長いこと理解できなかった）けど、分かると自然ですね。
シミュレーション部分は、各indexについて、「自分の左のindex」「自分の右のindex」のリストを更新していく感じで処理しました。（この方法が自然だと思うけれど、この代わりにUnion-findを使うこともできる）
C. Skyline Photo
一目DP。
高さhのもの（index i）を採用する場合、左右で自分より小さいものが初めてあらわれるindex l, rを求め、
・l～iのうち最大のもの+B[i]で、i～rの最大値を更新する。
というのでOK。
これは、遅延セグ木を使えばできます。
結構すぐに解法は分かったのに、実装に結構時間がかかり、添え字のミスでWA。約15分色々試したけど、WAの原因が分からず終了。
この問題だと、愚直を書けば分かったという気もしないので、見直し不足というしかないです。ただ、遅延セグ木の実装が間違っているのでは、と見直したのは無駄だったかもしれない。遅延セグ木ライブラリを適切に実装していればそこが原因ではないと思えたはずなので。抽象化すべきですね。
D. Useful Edges
ACはしてないけど、解説は理解したつもり。
全点からダイクストラ（もしくはワーシャルフロイド）を行った後、各辺について、全てのUsefulな条件を調べる……という方法がまず思いつくが、これだと、四乗かかる。（辺の数が二乗、Usefulの条件が二乗なので）
ここで、重みwの辺ABが、path UVの条件に関してUsefulであるとすると、
・$UA+w+VB \leq l$
と書ける。移項すると、
・$-l+UA \leq -w-VB$
となる。
これは、端点の片方をVに持つようなUseful条件をまとめて扱えることを示している。
つまり、全ての$V$を端点に持つようなUseful条件について、-l+UAの最小値を前計算しておけば、
・$最小値\leq -w-VB$
が成り立てばUseful条件のいずれかが満たされる、ということになる。
この方法だと、前計算も、最後の計算も三乗なので、四乗から三乗に計算量が落ちている。
……ということで良いと思うのだけど、自分の書いたPyPyのコードはTLEしてしまった。頂点数600で、定数倍も結構思い三乗なので、ちゃんと高速化しても通るかは分からないです。あまり他の言語に書き直す気にならないので、ACせず置いておきます。
式変形→前計算で計算量を減らす手法は結構使うと思うので、注意したい。
0 件のコメント:
コメントを投稿