ABC143 バチャメモ - tinumu's reminder

atcoder.jp
これは単なる生活崩壊なのじゃ

A

max(0, A - 2*B) だね

B

D[i] * D[j] をたします

C

連結している奴をひとつとみればいい
左から見て一つ着目して同じだったらずらしていくっていう方針で良いんじゃないかな

D

普通にやると $O(N^3)$ なので、予め大きさでソートしておけば２つ決めた時にlower_boundで何個作れるかわかるので $O(N^2 \log N)$ になる

E

$O(N^3)$ で最短経路なのでまずWarshall Floydをするすると、どこまでが距離 $L$ でいけるのかがわかるので、 $L$ 以下の経路を $1$ にして残して、それ以外を消す。
その後もう一回 Warshall Floyd をすると、何回補給すれば良いのかが求まる

F

数字の種類についてこの問題は聞いているので、数字の種類 $i$ が何個あるのかというものに変換する。
$c_i$ ... 数字の種類 $i$ が $c_i$ 個あるといった数列を形成する。
そして種類の選び方も任意のため、どの数字だったかによらずにソートしてしまって良い。

さて、 $K$ 回取る操作を $t$ 回操作を行うと仮定する。
この時、任意の $i$ について、 $min(c_i, t)$ 回しか取られない。よって $c_i \gt t$ の時は $t$ と見ても変わらない。
実は、 $\sum_{i=1}^{N}min(c_i, t) \geq tK$ であれば、 $t$ 回以上取ることが出来る。
問題を言い換えると、

$a_i \leq t$
$\sum_{i=1}^{N}a_i \geq tK$

の時、 $t$ 回操作を行えると見るとする。
さらに、

$a_i \leq t$
$\sum_{i=1}^{N}a_i = tK$

の時 $t$ 回操作を行えたならば、先ほどの条件は満たされる。
$\sum_{i=1}^{N}a_i = tK$ になるように数字を減らせるからである。

この時、 $a_i=T$ であるような $i$ の数は $K$ 以下である。
もしも $K$ より多かったら、 $\sum_{i=1}^{N}a_i > tK$ となり矛盾するからである。
そのため、 $1$ 回操作を行った時点で、 $a_i=T$ のものから一つ取ることで、次のような条件を達成できる。

$a_i \leq t-1$
$\sum_{i=1}^{N}a_i = (t-1)K$

このようなことになるので、あと $T-1$ 回繰り返すことが出来、 $T$ 回取れることが証明できた。

あとは、 $K$ について $t$ が単調減少になるかつ $c_i$ を大きい順にソートしておけば、 $min(c_i, t)$ の処理がならしで $O(1)$ でできるので、各 $K$ について高速に動き、
ソートに一番時間がかかり、 $O(N \log N)$ でこの問題は解ける。

難しいな

ソース

void Main() {
	int N; cin >> N;
	vint A(N); cin >> A;
	vint cnt(N, 0);

	for (int i = 0; i < N; i++) cnt[--A[i]]++;
	sort(rbegin(cnt), rend(cnt));
	
	vint rsum(N);

	for (int i = N-1; i >= 0; i--) {
		rsum[i] = cnt[i];
		if (i < N-1) rsum[i] += rsum[i+1];
	}

	int t = N;
	int k = 0;
	for (int K = 1; K <= N; K++) {
		while (t > 0) {
			while (cnt[k] > t) k++;
			int sum = k * t + rsum[k];
			if (sum >= K * t) {
				cout << t << el;
				break;
			}
			t--;
		}
		if (t == 0) cout << 0 << el;
	}
}

感想

生活習慣を直さなきゃ…！(悲嘆)