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
   ~~~<->~~~ ~ <-> ~
本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
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