目次
AtCoder Beginner Contest 178 D,E,F問題メモ
D - Redistribution
問題
- 各項が3以上の整数で、総和がちょうど $S$ となる数列の個数を $\mod{10^9+7}$ で求めよ
- $1 \le S \le 2000$
解法
3という下駄が厄介なので、はじめに全要素に配る。
配った後に $S$ がいくつ残るかは、数列の長さに依存する。
$L=1～\dfrac{S}{3}$（切り捨て）の範囲だけ調べればよい。
長さを $L$ と決めると、全要素を3にするのに $3L$ かかる。 和を $S$ にするには残り $M=S-3L$ を $L$ 個の項に配分すればよくて、 これは「$L$ 個の選択肢から重複を許して $M$ 個取る」と考えて重複組み合わせ ${}_{L}H_{M}$ で求められる。
計算量は、$O(S)$ かけて階乗を事前計算しておけば、$O(S)$ 通りある $L$ のそれぞれに対して答えが $O(1)$ で求まるので、全体で $O(S)$。
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f = f * m % MOD
factorials.append(f)
f = pow(f, MOD - 2, MOD)
finvs = [1] * (n + 1)
finvs[n] = f
for m in range(n, 1, -1):
f = f * m % MOD
finvs[m - 1] = f
return factorials, finvs
s = int(input())
MOD = 10 ** 9 + 7
facts, finvs = prepare(s, MOD)
ans = 0
for l in range(1, s // 3 + 1):
m = s - 3 * l
ans = (ans + facts[l + m - 1] * finvs[m] * finvs[l - 1]) % MOD
print(ans)
E - Dist Max
問題
- $N$ 個の点があり、$i$ 番目の点は $(x_i,y_i)$
- 2点間マンハッタン距離の最大値を求めよ
- $2 \le N \le 2 \times 10^5$
- $-10^9 \le x_i,y_i \le 10^9$
解法
シンプルな問題は、たいてい過去にどこかのコンテストで出題されていて、それに対する解説記事があったりする。
- arc047（B問題）
$x'←x+y, \ \ y'←x-y$ と変換すると、マンハッタン距離 $|x|+|y|$ はチェビシェフ距離 $\max(|x'|,|y'|)$ になるので、
距離最大のものは $\max(x'_{max}-x'_{min}, y'_{max}-y'_{min})$ で求められる。
3次元以上にも拡張できる。
典型問題は知ってるか、知らなくてもググれば答えが見つかりそうと思えるか、によるところが大きい。
n = int(input())
xxx = []
yyy = []
for _ in range(n):
cx, cy = map(int, input().split())
xxx.append(cx + cy)
yyy.append(cx - cy)
print(max(max(xxx) - min(xxx), max(yyy) - min(yyy)))
F - Contrast
問題
- 長さ $N$ の2つの整数列 $A,B$ が与えられる
- それぞれは昇順にソートされている
- $B_i$ を並べ替えて、どの $i=1～N$ に対しても $A_i \neq B_i$ としたい
- 可能か判定し、可能なら例を1つ示せ
- $1 \le N \le 2 \times 10^5$
解法
解説読むと、ずらすだけ、と書かれていて「それでいけるのかー」ってなる。
以下、自分の取った解法。
破綻する条件を考えると「$A,B$ にある個数の和」が多い数字から破綻しやすいので、そこから貪欲に確定。
判定
まず不可能なのを考えると、同じ数字が $A$ にも $B$ 一杯あるのは無理そう。
具体的には、一番ギリギリのケースは全ての $i$ において $A_i$ か $B_i$ のどちらかに同じ数字が詰まっている状況で、ここからどちらかが1個でも増えると無理。
A 1 1 1 _ _ _ _ B _ _ _ 1 1 1 1
なので、整数 $k$ の「$A$ にある個数」「$B$ にある個数」を $C_k,D_k$ として、$C_k+D_k \gt N$ なる $k$ があったら不可能となる。
- 不可能となるのは分かったが、これさえ満たされていれば大丈夫、というのはHallの定理から言える
以下、構築は可能とする。
$B$ をいったん空にして、確定できるところから割り当てていくことを考える。
どういう順で割り当てていくのがよいか。
こういう時、 「途中状態も、初期状態と同じような制約があり、割り当てた後も満たされた状態が保たれるならOK」 という考え方が使える場合がある。
$B$ に既にいくつかの配置を割り当てたのがあったとして、
A 1 1 1 3 3 3 3
B 1 1 2 2 2 3 3
↓
B _ _ _ 2 2 2 _ {未割り当て: 1 1 3 3}
改めて $C_k,D_k$ を以下のように定義しなおすと、
- $C_k$: まだ相手のいない $A_i$ の中での $k$ の個数
- $D_k$: まだ割り当てていない $k$ の個数
「$C_k+D_k \gt$ 未割り当て数」となったら同様の理由で構築は不可能となる。
初期状態で $C_k+D_k \gt N$ となる $k$ が無ければ、配置さえ上手くやれば大丈夫 （途中まで割り当ててはじめて不可能とわかるケースはない）なので、 途中過程でこれを避けるように割り当てていく。
つまり $C_k+D_k$ が大きい方から割り当てていくのがよさげ。
ちゃんと考えると、$A_i=k$ である $i$ に $l$ を割り当てると、未割り当て数、$C_k+D_k$、$C_l+D_l$ が1ずつ減る。
未割当数はどの数字でも共通なので、仮に $C_m+D_m \le C_k+D_k$ なる $m$ があったとして、
$k$ に $l$ を割り当てたために $m$ で破綻したとすると、$k$ 以外に割り当てたら $k$ でも同様に破綻するはずである。
従って、「$C_k+D_k \le$ 未割り当て数」を保とうと思えば、大きい $k$ から優先的に減らして損は無い。
実装
以下を管理する。
- $C_k+D_k$ の大きい方から $k$ を取り出せる優先度キュー
- 各 $k$ につき現在の $C_k, D_k$
- 各 $k$ につき、未割り当ての $A_i=k$ の中で最小の $i$
- $C_k \gt 0, D_k=0$ の $k$ の集合
- $A$ にだけ未割り当てが残り、$B$ のどの要素を割り当てても問題ない
$C_k+D_k$ の大きい2つを $k=l,m$ として、$A_i=m$ である $i$ に $l$ を割り当てていく。
この際、一部だけ割り当てて残ったものはまた後で処理しないといけない、ということがありそうなので、 常にその時の最大が取れるよう、優先度キューで管理する。
しかし、「$C_k=0$ だが $D_k$ が大きいためにキューの先頭に来る $k$」またはその逆みたいなのがあると、
取り出しても割当元・割当先が無いので飛ばさなければならず、邪魔である。
そのため、優先度キューに入れるのは、$C_k$ と $D_k$ が共に正である
（互いに未割り当てが残り、上手くしないと破綻する可能性がある）$k$ のみに限るとする。
優先度キューが最後の1個になったら、$C_k \gt 0,D_k=0$ である $k$ があるはずなので、ストックしておいてそこから割り当てればよい。
優先度キューが空になったとき、未割り当てで残る数字で $A$ と $B$ に重複はないので、どこに何を割り当ててもよい。
from collections import Counter
from heapq import heapify, heappop, heappush
from itertools import groupby
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cnt_b = Counter(bbb)
hq_both = []
free_a = []
idx_a = {}
cnt_a = {}
i = 0
for a, itr in groupby(aaa):
cnt = len(list(itr))
idx_a[a] = i
cnt_a[a] = cnt
if a in cnt_b:
cnt_ab = cnt + cnt_b[a]
if cnt_ab > n:
print('No')
exit()
hq_both.append((-cnt_ab, a))
else:
free_a.append(a)
i += cnt
heapify(hq_both)
ans = [-1] * n
remaining = n
while hq_both:
cnt_ab, b = heappop(hq_both)
cnt_ab = -cnt_ab
assert cnt_ab == cnt_a[b] + cnt_b[b]
assert cnt_ab <= remaining
cb = cnt_b[b]
while cb:
if hq_both:
_, a = heappop(hq_both)
else:
a = free_a.pop()
ca = cnt_a[a]
fill_len = min(ca, cb)
i = idx_a[a]
ans[i:i + fill_len] = [b] * fill_len
remaining -= fill_len
idx_a[a] += fill_len
cnt_a[a] -= fill_len
cnt_b[b] -= fill_len
cb -= fill_len
if cnt_a[a] > 0:
if a in cnt_b and cnt_b[a] > 0:
heappush(hq_both, (-(cnt_a[a] + cnt_b[a]), a))
else:
free_a.append(a)
free_a.append(b)
for b, cb in cnt_b.items():
if cb == 0:
continue
while cb:
a = free_a.pop()
ca = cnt_a[a]
fill_len = min(ca, cb)
i = idx_a[a]
ans[i:i + fill_len] = [b] * fill_len
idx_a[a] += fill_len
cnt_a[a] -= fill_len
cb -= fill_len
if cnt_a[a] > 0:
free_a.append(a)
print('Yes')
print(*ans)
賢い解法
ソートされていることを利用して、ずらすだけ。
先述の通り「$A$ と $B$ に出てくる回数の合計が $N$ より大きくなる数字が存在したら不可能」として、そうではないことを前提とする。
$A$ を2回繰り返して、$B$ をずらすだけにして考える。
前半サイクルと後半サイクルのそれぞれで、重ならない条件を考える。
前半←|→後半 A 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 B 1 2 2 2 2 2 2 3 3
繰り返す前の数列で以下を計算しておくと
- $E_k$: $A$ の中で整数 $k$ が終了する次のindex
- $F_k$: $B$ の中で整数 $k$ が開始するindex
- $G_k$: $A$ と $B$ で共通して出てくる $k$ に対して、$E_k-F_k$
整数 $k$ が前半サイクルと $B$ で重ならないためには、$B$ を $G_k$ だけずらせばよい。
たとえば下図で'1'だけに着目すると、$G_1=3$ だけ右にずらすと、'1'に関しては重なりを回避できる。
E1 E2 E3
3 6 9
A 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3
B 1 2 2 2 2 2 2 3 3 → 1 2 2 2 2 2 2 3 3
0 1 7 Aで'1'が終わったところにBの'1'の先頭を合わせるイメージ
F1 F2 F3
すると、$G_k$ の最大値を $G_{max}$ とすると、$B$ を $G_{max}$ だけずらした結果は前半サイクルではどの数字も重ならない。
さて、次は後半サイクルだが、この時点で、後半サイクルでも重ならないことが言えてしまう。
なぜか。
$B$ を $G_k$ ずらすことで $m$ が衝突してしまうような整数の組 $(k,m)$ を仮定して、矛盾を導く。
また、$A$ における $m$ の前を $l$、$B$ における $m$ の後を $n$ とする。
こんな感じになってる。
El Em
A .......... l m m m m ........
B ........ m m m m m m m m n ...
Fm Fn
衝突時 El+N
v
A .......... l m m m m ......... l m m m m .....
B --Gkずらす→ ........ m m m m m m m m n ...
~~~~~ ^
衝突 Fn+Gk
$m$ が端のために $l,n$ が存在しない場合は、$E_l=0$ または $F_n=N$ としておく。
衝突時の位置関係をindexで表すと、以下のようになっている。
- $E_l+N \lt F_n+G_k = F_n+E_k-F_k$
ここで、$k$ と $m$ の大小で場合分けする。
- $k \lt m$:
- 昇順に並んでいるので $E_k \le E_l$
- $E_k+N \le E_l+N \lt F_n+E_k-F_k$
- $N \lt F_n - F_k$
- しかし、$1 \le F_n \le N, \ 0 \le F_k \le N-1$ の2数の差が $N$ を越えることは無い
- $m \lt k$:
- 昇順に並んでいるので $F_n \le F_k$
- $E_l+N \lt F_n+E_k-F_k \le F_k+E_k-F_k$
- $N \lt E_k - E_l$
- しかし、$1 \le E_k \le N, \ 0 \le E_l \le N-1$ の2数の差が $N$ を越えることは無い
- $k=m$
- そもそもこれで衝突するなら全体で $N+1$ 個以上あることになる
矛盾したので、衝突しない。よって、$G_{max}$ だけずらして問題ない。
発想は単純でも、ちゃんとした証明はindexを式で表し、場合分けするという地道な作業が必要。
賢い解法2
$B$ をひっくり返して、矛盾した箇所を適当に他の場所に持っていけばOK。
可能不可能判定は上記と同様。
ひっくり返して $A$ にくっつけたとき、$A_i=B_i$ となる箇所がなければそれでいいし、あってもそのような $k$ は1通りに限られる。
また、$k$ が重なって矛盾している数以上に、$A_i \neq k,B_i \neq k$ となる $i$ がある。（なかったら $C_k+D_k \gt N$ になる）
そのような $i$ で入れ替えれば矛盾を解消できる。
A 1 1 1 2 2 2 3 3 3
B 3 3 2 2 2 2 2 2 1
^ ^ ^ 矛盾 k=2
^ ^ ^ A≠k, B≠k
↓
A 1 1 1 2 2 2 3 3 3
B 2 2 2 3 3 1 2 2 2
~~~<->~~~ ~ <-> ~
