目次
AtCoder Beginner Contest 173 D,E,F問題メモ
黄復帰。逆から読むとキッフキ。
D - Chat in a Circle
問題
- $N$ 人がいて、人 $i$ の「フレンドリーさ」は $A_i$
- 1人ずつ順番に、以下の要領で輪の好きな位置に入っていく
- 最初、輪に人はいない
- 最初に入った人の「心地よさ」は0
- 2番目以降の人の「心地よさ」は、入った時点で両隣にいる人のフレンドリーさの小さい方
- 上手く順番と入る位置を決めて、全員の心地よさの総和を最大化せよ
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
解法
それっぽい解法を思いつく→それを適用したときの解法を求める→性質上、それ以上改善できないことを証明する（できてない）
結果的には貪欲解が答え。
まず、なるべく $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)
E - Multiplication 4
問題
- $N$ 個の整数 $A_1,A_2,...,A_N$（負もあり得る）
- ここからちょうど $K$ 個を選んで掛け合わせたときの最大値を $10^9+7$ で割った値（$0 \le Ans. \lt 10^9+7$）で求めよ
- $1 \le K \le N \le 2 \times 10^5$
解法
場合分けと注意力勝負。
本番は嘘で通してしまっていた。注意力は無いようだ。
$A$ を $A_正,A_負,A_0$ の3つに分類する。
基本は、絶対値の大きい方から $A_正$ か $A_負$ を2個ずつペアにしてかけていけばよいが、
- 0を含めざるを得ない場合、0
- 結果が負にならざるを得ない場合、絶対値の小さい方からかける
等はあらかじめ個別に対応していく。
負にならざるを得ない場合というのは、負を奇数回かけざるを得ない場合だが、以下のいずれかの場合にそうなる。
- $N=K$ かつ $A_負$ が奇数（ただ、この場合は何も考えず全てかけるので、答えも自明）
- $K$ が奇数かつ $A$ が全て負
正負の入り交じった積を求める問題は「最終結果が非負か、負か」で大きく場合分けすれば多少は整理しやすい、かもしれない。
今回の場合、結果的には $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))
F - Intervals on Tree
問題
- $N$ 頂点の木、辺 $i$ は頂点 $u_i$ と $v_i$ を結ぶ
- 関数 $f(L,R)$ を以下のように定義する
- 頂点番号が $L$ 以上 $R$ 以下の頂点集合を $S$ とする
- $S$ と、両端がともに $S$ に含まれる辺のみを取り出す
- 取り出されたグラフの連結成分の個数を $f(L,R)$ とする
- $1 \le L \le R \le N$ を満たす $L,R$ の組は $\dfrac{N(N+1)}{2}$ 個あるが、全てについて $f(L,R)$ を求め、総和を答えよ
- $1 \le N \le 2 \times 10^5$
解法
木の性質は使うものの、実際に木のデータ構造を作らなくても解ける問題。
元々が木なので、取り出されるグラフにも閉路は無い。 よって、連結成分は頂点数 $|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)
