AtCoder Regular Contest-- 229 B,C,D,E,F問題メモ

AtCoder Regular Contest-- 229

B - Halving Subtraction

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
あなたは $A$ に対して以下の操作を $0$ 回以上好きな回数行うことができます：
- 正整数 $x_0$ を選び、$x=x_0$ とする。その後、$i=1,2,\ldots,N$ の順に以下を行う：
  - $A_i$ から $x$ を引き、$x$ を $\displaystyle \left\lfloor \frac x2\right\rfloor$ で置き換える。
$A$ の要素を全て $0$ にすることが可能か判定し、可能な場合は全て $0$ にするために必要な操作回数の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^4$
$1\le N\le 30$
$0\le A_i\le 10^9$
入力される値は全て整数

解法

まず、問題を以下のように言い換える。元の問題とは $x$ の動く範囲が異なり、それに伴い最適な操作回数が異なるが、その差は後で回収する。

与えられた $A$ を逆順にして考える。
以下を繰り返す。
- 好きな $j$ を選ぶ。$j=1$ なら $x$ は好きな数に、$j \ge 2$ なら $x=1$ に設定する。
- $i=j,j+1,j+2,...,N$ の順に以下をおこなう。
  - $A_i$ から $x$ を引き、$x$ を $2x$ で置き換える。

この時、先頭から $0$ でない最初の $j$ を貪欲に操作起点としていって問題ない。途中で $A_i \lt x$ となったら不可能である。

    A  0  1  2  7 16
操作1     1  2  4  8
残り   0  0  0  3  8
操作2           1  2
操作3           1  2
操作4           1  2
残り   0  0  0  0  2
操作5              1
操作6              1
残り   0  0  0  0  0    完了

ここで、2つの操作起点 $j_1 \lt j_2$ があったとして、 $j_2$ から開始する操作1回は、$j_1$ から開始する操作1回で吸収できる。

        A  0  1  2  7 16
操作1+2+5     1  2  5 11
残り       0  0  0  3  5
操作3+6             1  3
操作4               1  2
残り       0  0  0  0  0    完了

元の問題の通り、操作を右から行い $x$ を半分ずつにしていった場合に、ちゃんと1回で可能な操作であることが確認できる。

よって、答えは「言い換えた問題を解いたとき、同じ $j$ が操作起点となる回数の最大値」となる。

Python3

def solve(n, aaa):
    aaa.reverse()

    ans = 0
    for j in range(n):
        if aaa[j] == 0:
            continue
        x = aaa[j]
        y = 1 if j == 0 else x
        for i in range(j, n):
            if aaa[i] < x:
                return -1
            aaa[i] -= x
            x <<= 1
        ans = max(ans, y)

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)

C - Sum of Average 2

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$A$ を好きな順序に並べ替えた後の $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ としてあり得る最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^5$
$2\le N\le 2\times 10^5$
$1\le A_i\le 10^9$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

場合分けをしっかり。

ベースを、$\displaystyle B=\sum_{i=1}^{N-1}\left\lfloor\frac{A_i}{2} \right\rfloor + \left\lfloor\frac{A_{i+1}}{2} \right\rfloor$ とする。

答えがベースより増えるのは、奇数を隣接させてしまった場合に、その箇所毎に1増える。

また、$\left\lfloor\frac{A_i}{2} \right\rfloor$ は $i=1,N$ のみ $1$ 回しかカウントされないが、他は $2$ 回ずつカウントされるので、大きい要素を端に持っていきたい。

基本は大きい方から2個を両端にするのが良さそう。
そして、それは正しい。

正当性: 損するのは、偶数が端に置かれることで内側に奇数の隣接箇所が増えてしまう場合だが、その偶数を端に置かないことで減らせる奇数の隣接は高々 $1$ 個。それなら、最大値（制約より偶数なら $2$ 以上）を端にすることで減らせるコストの方が同じか安い。

端に置かない偶数を除いてそれ以外を並べ、後から偶数を、奇数の隣接箇所があれば優先的に挟み込むと考えれば、 $\max(0,$奇数が隣接する箇所$-$残りの偶数$)$ で奇数の隣接箇所を計算できる。

$A$ における奇数・偶数の個数を $O,E$ とする。端に置く数が (奇,奇),(奇,偶),(偶,偶) の3通りで場合分けして、奇数の隣接数が $O,E$ から $O(1)$ で計算できる。

Python3

def solve(n, aaa):
    if n == 2:
        return (aaa[0] + aaa[1]) // 2

    odd = sum(a % 2 for a in aaa)
    even = n - odd
    aaa.sort()
    m1 = aaa[-1]
    m2 = aaa[-2]

    ans = 0
    for a in aaa:
        ans += a // 2 * 2
    ans -= m1 // 2
    ans -= m2 // 2

    if (m1 % 2 + m2 % 2) == 0:
        cost = max(0, odd - 1 - (even - 2))
    elif (m1 % 2 + m2 % 2) == 1:
        if even == 1:
            cost = n - 2
        else:
            cost = max(0, odd - 2 - (even - 2))
    else:
        cost = max(0, odd - 1 - even)
    ans += cost
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)

D - Nim_k ?

問題文

$K+1$ 個の石の山があります。$i$ 個目の山には石が $A_i$ 個積まれています。
Alice と Bob はゲームをします。ゲームでは Alice を先攻として交互に手番を行います。
手番では以下の操作をちょうど $K$ 回行います。
- 石が $1$ 個以上ある山を選び、そこから石を $1$ 個以上取り除く。ここで、同じ手番の中で同じ山を複数回選んでも良い。
ゲームは自分の手番で操作を $K$ 回行うことができなかったプレイヤーの負けです。双方が最適に行動した時どちらが勝ちますか？

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq K \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
全てのテストケースに対する $K$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

解法

NimのようでNimでない論理パズルの問題。山が(操作回数+1)個というところがポイント。

負ける側の最後の手番は「★:残る山の石の総数が $K$ 未満（$\sum_i A_i \lt K$）」の時。 1回の操作で1個は石を取らないといけないので $K$ 回操作できない。逆に $K$ 個以上あったら少なくともその手番の操作は可能。

初期の $A_i$ の最小値を $m$ とする。

$d$ を、$dK \le m \lt (d+1)K$ を満たす値とする。
$x$ を、$\sum_i(A_i-dK)$ とする。

K = 5
A  6  8  8 12 21    m=6, d=1, x=1+3+3+7+16=30

この時、$x \lt K$ なら後手勝ち、$x \ge K$ なら先手勝ちとなる。

K = 5

d=0 の時（制約上、x >= K は確定）
A  3  8  8 12 21
    ↓              最小値以外のK個の山を全て0にすれば★の状態を相手に渡して先手必勝
   3  0  0  0  0

d=1, x<K の時
A  5  5  6  6  7    どうやっても d=0,x>=K の状態を相手に渡すしかない
    ↓              Ai>=K の山が1つ以上残り、それ以外で Aj<K の山が1つはできてしまうので
   5  4  5  5  5    後手必勝

d=1, x>=K の時
A  6  6  7  8  9
    ↓              d=1, x<K の状態を相手に渡せるので先手必勝
   6  5  5  5  5

d=2, x<K の時
A 10 10 11 11 12    どうやっても d<=1,x>=K の状態を相手に渡すしかない
    ↓              Ai>=2K の山が1つ以上残り、それ以外で Aj<2K の山が1つはできてしまうので
  10  9 10 10 10    後手必勝

d=2, x>=K の時
A 10 11 12 13 14
    ↓              d=2, x<K の状態を相手に渡せるので先手必勝
  10 10 10 10 10
 :

Python3

def solve(k, aaa):
    aaa.sort()
    m = aaa[0]
    d = m // k
    if d == 0:
        return True
    if sum(a - d * k for a in aaa) >= k:
        return True
    return False


t = int(input())
for _ in range(t):
    k = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(k, aaa)
    if ans:
        print('Alice')
    else:
        print('Bob')

E - Taka and Hashi

問題文

高橋君は有名お笑いコンビ『タカアンドハシ』、すなわちタカとハシに分裂できることで知られています。タカとハシが合体すると元の高橋君に戻ります。
$N$ 頂点 $M$ 辺の連結無向グラフがあり、各辺には $1,2,3$ のいずれかのラベルが貼られています。
- $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結び、ラベル $l_i$ が貼られています。
- グラフは自己ループを含みませんが多重辺を含む可能性があります。
- 各辺は高橋君・タカ・ハシのうち $1$ 人しか通行できず、ラベル $1,2,3$ の辺を通行できるのは、それぞれ高橋君、タカ、ハシのみです。
はじめ、高橋君は頂点 $1$ にいます。高橋君たちは次の操作を自由な順序で $0$ 回以上行えます。
- 高橋君が自身のいる頂点上でタカとハシに分裂する。このとき、タカとハシはともにその頂点にいる。
- 現在存在する人のうち $1$ 人が、その人の通行可能な辺を $1$ 本通って移動する。
- タカとハシが同じ頂点にいるとき、その頂点で二人が合体して高橋君に戻る。
一連の操作を行った後に高橋君がいることのできる頂点を、全て昇順に列挙してください。

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

$1 \leq T \leq 10^5$
$2 \leq N \leq 2 \times 10^5$
$N-1 \leq M \leq 2 \times 10^5$
$1 \leq u_i \lt v_i \leq N$
$1 \leq l_i \leq 3$
入力で与えられるグラフは連結
全てのテストケースに対する $N$ の総和は $2 \times 10^5$ 以下
全てのテストケースに対する $M$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

WA解法

以下の解法はWAとなる。

頂点 $1$ から、高橋君、タカ、ハシ、3種類個別に、到達できる頂点を管理する。
高橋君が到達可能な頂点はタカ、ハシも到達可能とする。
タカ、ハシがともに到達可能な頂点は、高橋君も到達可能とする。

反例は以下のようなグラフの時、②はタカもハシも到達可能ではあるが、高橋君はそこに存在できない。

①--2→○--2-↘
 `--3→②--3→③--1→④
        ↖-2--○←2--'

到達可能なのは「③→④の辺を通る前に分裂したハシ」と「③→④の辺を通った後で分裂したタカ」なので、「同時に」到達可能にはならないからである。

解法

タカ・ハシを単独状態で管理するとWA解法のようなケースを除きづらいので、「高橋君が $u$ にいるとき、途中で一度タカとハシに分裂してもいいので、再び高橋君として存在できる頂点 $v$ はどこか」という方向性で考える。

ラベル $1$ の辺のみを使ったグラフを $G_1$、同じくラベル $2,3$ のみを使ったグラフをそれぞれ $G_2,G_3$ とする。
$u$ から、再び高橋君として存在できるのは、以下の2種類である。

$G_1$ で $u$ が属する連結成分の、他の頂点
「$G_2$ で $u$ が属する連結成分」と「$G_3$ で $u$ が属する連結成分」で共通する頂点

前者はともかく、後者はそれぞれの $u$ について毎回求めていたらTLEとなる。

だが、同じ連結成分の組は、以下のように2つのIDの組で表現できるので、

$G_2,G_3$ の各連結成分のIDを一意に決めておく。（Union-Findのリーダーの頂点番号などを使えばよい）
$u=1,2,...,N$ につき、
- $G_2$ で $u$ が属する連結成分のIDを $t_u$
- $G_3$ で $u$ が属する連結成分のIDを $h_u$
- $(t_u,h_u)$ を1つの頂点と見なし、$G_1$ に（まだないなら）追加する。$u$ と $(t_u,h_u)$ を辺で繋ぐ

とすると、$u$ から一度分裂して再び存在できる頂点同士が、$(t_u,h_u)$ を通して $G_1$ 上で繋がるようになる。

このようにした $G_1$ で①と連結なオリジナルの頂点が、答えである。

Python3

from atcoder.dsu import DSU


def solve(n, m, edges):
    dsus = [DSU(n * 2)] + [DSU(n) for _ in range(2)]
    for u, v, l in edges:
        u -= 1
        v -= 1
        dsus[l - 1].merge(u, v)

    pairs = set()
    for u in range(n):
        l1 = dsus[1].leader(u)
        l2 = dsus[2].leader(u)
        pairs.add((l1, l2))
    pairs = sorted(pairs)
    mapping = {p: i + n for i, p in enumerate(pairs)}

    for u in range(n):
        l1 = dsus[1].leader(u)
        l2 = dsus[2].leader(u)
        i = mapping[l1, l2]
        dsus[0].merge(u, i)

    l0 = dsus[0].leader(0)
    ans = [u + 1 for u in range(n) if dsus[0].leader(u) == l0]
    ans.sort()
    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, edges)
    print(len(ans))
    print(' '.join(map(str, ans)))

F - Angst for All Pairs 2

問題文

正整数 $N$ と長さ $N$ の正整数列 $C=(C_1,C_2,\ldots,C_N)$ が与えられます。
カードを $1$ 枚以上好きな枚数用意し、それぞれのカードの表と裏に $1$ 以上 $N$ 以下の整数を $1$ つずつ書き込むことで、以下の条件を満たすようにしたいです。
- $1$ 以上 $N$ 以下の相異なる整数 $x,y$ をどのように選んでも、以下を満たすカードが $1$ 枚以上存在する。
  - $x,y$ のうちちょうど一方が、そのカードの少なくとも一方の面に書かれている。
$1$ 枚のカードの表と裏に同じ整数を書き込むことも許されます。
ただし、$1$ 枚のカードの表に $a$ を、裏に $b$ を書き込むためにはコストが $C_a+C_b$ かかります。
条件を満たすために必要なコストの総和の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^5$
$2\le N\le 2\times 10^5$
$1\le C_i\le 10^9$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

コスト $C$ は昇順にソートしても答えに影響しない。

同じ値の組 $(a,b)$ の書かれたカードを2枚以上用意する必要は無い。同じ値の組は高々1枚としてよい。

コスト最大の $N$ は書き込まなくていい。$1～N-1$ が書かれたカードがそれぞれ1枚以上あれば条件は満たされる。
他の値は1回は書き込まなくてはならないが、そのうち条件を満たさないのは、以下のような $(i,j)$ が存在する場合に限られる。

2数 $i,j$ が書かれたカードはあるが、$i$ も $j$ も、その1枚にしか書かれていない。

そのような $(i,j)$ が無いとすると、条件を満たすカードが必ず存在することを証明できる。
各カードに書かれた値の組 $(i,j)$ と選ばれた $(x,y)$ に対して、

$(x,y)=(i,j)$ の時
- 前提より、$i$ または $j$ のどちらか一方のみが書かれたカードが他に存在する。
$(x,y)=(i,他の値)$ や $(他の値,j)$ の時
- $(i,j)$ が条件を満たす。
その他の時は、$x,y$ と被るような他の $i,j$ で同じことが言える

言い換えると、頂点 $1,2,...,N-1$ に対し、孤立頂点およびサイズ2の連結成分を作らずに辺を追加すれば良い。

頂点を、ハブとスポークに分ける。コストの低い方をハブとしていい。

←低    コスト    高→
①②③④⑤⑥⑦⑧⑨⑩⑪  ⑫←不使用

④--①--⑤  ⑧--②--⑨  ⑩--③--⑪
⑥--'`--⑦

スポークは1回のみいずれかのハブと繋げばよい。
ハブは2回以上使う必要があるが、②以上のハブは2回でよく、他は全て①に繋げばよい。

ハブとスポークの境界線（$k$ 以下の頂点をハブとして使う）を決めれば、その時の最適コストは累積和の事前計算の元、 $O(1)$ で求められる。境界 $k$ を全探索すればよい。

Python3

from itertools import accumulate


def solve(n, ccc):
    ccc.sort()

    if n == 2:
        return ccc[0] * 2
    if n == 3:
        return ccc[0] * 3 + ccc[1]

    acc = [0] + list(accumulate(ccc))

    ans = 1 << 60
    for lo_cnt in range(1, n):
        hi_cnt = n - 1 - lo_cnt
        if lo_cnt * 2 > hi_cnt:
            break
        min_ex_cnt = hi_cnt - lo_cnt * 2
        hi_cost = acc[n - 1] - acc[lo_cnt]
        lo_cost = acc[lo_cnt] * 2 + ccc[0] * min_ex_cnt
        ans = min(ans, hi_cost + lo_cost)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    ccc = list(map(int, input().split()))
    ans = solve(n, ccc)
    print(ans)

目次

AtCoder Regular Contest-- 229 B,C,D,E,F問題メモ

B - Halving Subtraction

問題文

制約

解法

C - Sum of Average 2

問題文

制約

解法

D - Nim_k ?

問題文

制約

解法

E - Taka and Hashi

問題文

制約

WA解法

解法

F - Angst for All Pairs 2

問題文

制約

解法