−目次

AtCoder Beginner Contest 178 D,E,F問題メモ
- D - Redistribution
  - 問題
  - 解法
- E - Dist Max
  - 問題
  - 解法
- F - Contrast

AtCoder Beginner Contest 178 D,E,F問題メモ

AtCoder Beginner Contest 178

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$

解法

シンプルな問題は、たいてい過去にどこかのコンテストで出題されていて、それに対する解説記事があったりする。

$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の定理から言える
- Hallの結婚定理とその証明 | 高校数学の美しい物語
- [AtCoder 参加感想] 2020/09/13:ABC 178 | maspyのHP

以下、構築は可能とする。

$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

AtCoder Beginner Contest 178 F - Contrast - ARMERIA

$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
   ~~~<->~~~ ~ <-> ~