黄復帰。逆から読むとキッフキ。
それっぽい解法を思いつく→それを適用したときの解法を求める→性質上、それ以上改善できないことを証明する(できてない)
結果的には貪欲解が答え。
まず、なるべく $A_i$ が大きい人にさっさと輪に入ってもらって多くの回数足されてほしいので、この順に挿入した方がなんとなくよさそう。
$A_i$ が大きい方から順に番号を振り直し、$A_0,A_1,...,A_{N-1}$ とする。この順に、その時点で最も心地よさが高くなる位置に入ると、
のように、90度、45度、22.5度、… 刻みで間を埋めていく感じになる。その場合の心地よさは、以下のようになる。
i 0 1 2 3 4 5 6 7 ... ※ - 0 1 1 2 2 3 3 ... ※: 人i挿入時に両隣のうち小さい方のAiを持つ人
$A_0$ を1回、後は大きい順に $A_i$ を2回ずつ人数一杯まで足した値となる。
どうも2回というのがポイントらしい。これを確認する。
ある、とても大きな値(100)に挟まれた大きな値(10)があったとして、この10は何回答えに加算されうるかというと、
100 10 100 ↑ ↑
$A_i$ を大きい順に挿入する限り、矢印の位置に何かを挿入する2回が上限である。
2回の挿入後、さらに10の隣に置こうとしても、その時には隣に10以下の $A_i$ が入っているので、心地よさはそちらに引きずられる。
100 9 10 8 100 ↑ ↑
ただし、$A_0$ に関しては上の「100」に相当するものが存在せず、初手で挿入しておいて2番目の人で加算される1回が上限である。 逆に初手で挿入しないと加算されることはない。
A0 A0(1周回って自分自身) ↑
ならば、上記の貪欲解は最善手であり、これ以上よくする手段は存在しない。
もしかしたら順番を変えたりして上手くいくことがあるかも知れないが、それを洗い出すのに5分はかかるだろうので、とりあえず提出。通った。
なお、降順に挿入してよい証明は、解説pdfの通り「どこか1箇所の挿入順が降順で無い場合、入れ替えることで悪くはならない」を言うことで可能だった。 証明としてよくあるパターンなので、パッと思い出せるようにしたい。
import sys n, *aaa = map(int, sys.stdin.buffer.read().split()) aaa.sort(reverse=True) ans = 0 for i in range(n - 1): ans += aaa[(i + 1) // 2] print(ans)
場合分けと注意力勝負。
本番は嘘で通してしまっていた。注意力は無いようだ。
$A$ を $A_正,A_負,A_0$ の3つに分類する。
基本は、絶対値の大きい方から $A_正$ か $A_負$ を2個ずつペアにしてかけていけばよいが、
等はあらかじめ個別に対応していく。
負にならざるを得ない場合というのは、負を奇数回かけざるを得ない場合だが、以下のいずれかの場合にそうなる。
正負の入り交じった積を求める問題は「最終結果が非負か、負か」で大きく場合分けすれば多少は整理しやすい、かもしれない。
今回の場合、結果的には $A_正$ と $A_0$ を区別する必要は無く、まとめて $A_{非負}$ とした方が取り回しやすい。
* N=K? |- はい → 全てかける | |- いいえ * Aは全て負? |- はい | * Kは奇数? | |- はい → 負確定。絶対値の小さい方からかける | |- いいえ → 正確定。絶対値の大きい方からかける | |- いいえ (非負確定) * Kは奇数? |- はい → 非負の最大値を1個かけ、 残りを非負or負から2個ずつ絶対値の大きい方からかける |- いいえ → 非負or負から2個ずつ絶対値の大きい方からかける
import sys def solve(n, k, aaa): MOD = 10 ** 9 + 7 if n == k: ans = 1 for a in aaa: ans = ans * a % MOD return ans pos = [] # To be exact, Non-neg neg = [] for a in aaa: if a >= 0: pos.append(a) elif a < 0: neg.append(a) if len(pos) == 0: if k % 2 == 1: neg.sort(reverse=True) else: neg.sort() ans = 1 for a in neg[:k]: ans = ans * a % MOD return ans pos.sort() neg.sort(reverse=True) ans = 1 r = k if r % 2 == 1: ans = ans * pos.pop() % MOD r -= 1 while r > 0: if len(pos) <= 1: ans = ans * neg.pop() * neg.pop() % MOD elif len(neg) <= 1: ans = ans * pos.pop() * pos.pop() % MOD else: pm = pos[-1] * pos[-2] nm = neg[-1] * neg[-2] if pm > nm: ans = ans * pos.pop() * pos.pop() % MOD else: ans = ans * neg.pop() * neg.pop() % MOD r -= 2 return ans n, k, *aaa = map(int, sys.stdin.buffer.read().split()) print(solve(n, k, aaa))
木の性質は使うものの、実際に木のデータ構造を作らなくても解ける問題。
元々が木なので、取り出されるグラフにも閉路は無い。 よって、連結成分は頂点数 $|S|$ をベースとして、辺が1個含まれる毎に必ず1だけ減る。
閉路が無いと、1つの辺は、必ず異なる2つの連結成分をくっつけて1つにする。 (仮に閉路があると、辺が結ぶ2つの頂点は他の辺によって既に同一の連結成分に属しているかもしれないので、必ずしも1減ると言えない)
なので、まず全ての場合において $|S|$ を求めて足し合わせておいて、そこから各辺につき「この辺が採用される $L,R$ の組は何個あるか?」を求めて引けばよい。
たとえば $N=10$ で、頂点 $(3,6)$ を結ぶ辺は、「$L$ は $1,2,3$ のどれか」「$R$ は $6,7,8,9,10$ のどれか」で、計15通りの組について、取り出される。
一般化すると、辺 $i$ は $u_i \times (N-v_i+1)$ 通りの組において取り出される。
import sys n, *uv = map(int, sys.stdin.buffer.read().split()) ans = 0 for i in range(1, n + 1): ans += i * (n - i + 1) for u, v in zip(uv[0::2], uv[1::2]): if u > v: u, v = v, u connect = u * (n - v + 1) ans -= connect print(ans)