コンテストへのリンク
A. Recommendations
今読んでも難読だと思う……。
結局、全てのiに対して、A[i]全てが異なるようにしたい。各A[i]を+1するコストがB[i]という内容。
私がやった解法は、
・各A[i]について、B[i]の和を前計算 & B[i]たちをheapqに入れておく。
・A[i]が小さいものから見て、（そのA[i]の地点でのB[i]たちの和）ｰ(B[i]の最大値)を答えに加え、差分計算。
という方法。結構面倒だった。他の人の提出を見ると、もう少し良い方法がありそうだけど、そこまで楽にはならなそうかな……。
B. Double Elimination
公式解説を読んでAC。
言われてみれば自然な解法だけど、解説を読んでも長い時間理解できなかったし、実装にも苦しんでしまった……。
とはいえ、状況を整理できいれば思いつけて良い解法に思えます。
たとえば、5～8番目の人を考える。
その人たちは、二回試合をすると勝者はただ一人になる。
敗者組についても同じ。敗者組の試合が二回行われた後、敗者組の中での勝者も一人。
つまり、勝者組二試合、敗者組二試合が行われた後では、それぞれの勝者は一人ずつしかいない。なので、「その二人の中にfanがいるかどうか」でDPできる。
具体的には、DP[n][left][Upper][Lower]を、
n試合後、[left番目～left+$2^n$)番目の人で、
n試合後、[left番目～left+$2^n$)番目の人で、
・Upper=1: ファンの人が勝者組で勝ち残っている Upper=0: 勝ち残っていない
・Lower=1: ファンの人が敗者組で勝ち残っている Lower=0: 勝ち残っていない
ときの、そこまでのファンの試合数の最大値。
と定義すればDPが回る。
そう理解した後も実装に苦しんでしまったけど、上手くやれば結構綺麗に書けるのかな……。
D. Tourism
公式解説にもある乱択解法でAC。
コンテスト後に「乱択で通した」というツイートを見た記憶はありましたが、その場では理解できず、復習してようやく理解しました。
・全ての町を0と1の色で塗って、「次の町は別の色でしかいけない」という条件で最短経路を求める
と条件を満たすルートになっている。そして、
・経由するのは高々9個の町なので、$2^9$分の1の確率で条件を満たす。
ということですね。
分かってしまえば難しくないけれど、「二色に塗り分ける」という方針がそれほど容易に思いつくものじゃない気が。
0 件のコメント:
コメントを投稿