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$

解法

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

$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$ があったら不可能となる。

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

$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
   ~~~<->~~~ ~ <-> ~
programming_algorithm/contest_history/atcoder/2020/0913_abc178.txt · 最終更新: 2020/09/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0