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)
シンプルな問題は、たいてい過去にどこかのコンテストで出題されていて、それに対する解説記事があったりする。
$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)))
解説読むと、ずらすだけ、と書かれていて「それでいけるのかー」ってなる。
以下、自分の取った解法。
破綻する条件を考えると「$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$ があったら不可能となる。
以下、構築は可能とする。
$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+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$ の大きい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
繰り返す前の数列で以下を計算しておくと
整数 $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で表すと、以下のようになっている。
ここで、$k$ と $m$ の大小で場合分けする。
矛盾したので、衝突しない。よって、$G_{max}$ だけずらして問題ない。
発想は単純でも、ちゃんとした証明はindexを式で表し、場合分けするという地道な作業が必要。
$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 ~~~<->~~~ ~ <-> ~