AtCoder Regular Contest 119 A,B,C,D,E問題メモ

AtCoder Regular Contest 119

ひっさびさに正のRating差分が得られた。

A - 119 × 2^23 + 1

• AtCoder でたびたび割った値を求めるのに使用される $998244353$ は、実は $119 \times 2^{23} + 1$ と表される
• $N$ が与えられるので、$N=a \times 2^{b} + c$ となる非負整数 $a,b,c$ のうち、$a+b+c$ が最小となる組を求めよ
• $1 \le N \le 10^{18}$

$b$ から探索していけば $2^{60}$ くらいで $10^{18}$ を超えるので、全部調べればよい。

Python3

n = int(input())
ans = 1 << 60

for b in range(100):
    b2 = 1 << b
    a, c = divmod(n, b2)
    ans = min(ans, a + b + c)

    if b2 > n:
        break

print(ans)

B - Electric Board

• '0'と'1'からなる長さ $N$ の文字列 $S$ と $T$ が与えられる
• 以下の操作を繰り返し、$S$ を $T$ に一致させられるか判定し、可能なら最小の操作回数を示せ
• 操作
  • '111..1110' という箇所を '0111…111' にする（'1'は1個以上何個続いていてもよい）
  • '0111..111' という箇所を '111…1110' にする（'1'は1個以上何個続いていてもよい）
• $1 \le N \le 5 \times 10^5$

操作前後で'0'と'1'の個数は変化しないので、個数が異なれば不可能。同じなら、操作回数はともかく端から埋めていけば必ず可能。
以下、個数は同じとする。

'1'は一つにまとめればまとめて移動させられるというのがトリッキーで、下手に細かな'1'の塊から動かすと、回数が増えてしまう。

また、'0'の連続はまとめては移動させられないため、以下は'1'を1回ずつ移動させる必要がある。

S 111110  1回でOK
T 011111

S 100000  5回必要
T 000001

端から順に'1'の位置を合わせていくことを考える。 '1'を何個ストックしてるか管理する。

【ストック無し】
S 1????  →  後のTに持っていくストックが1増える
T 0????      操作回数は1増える

S 0????  →  後のSから1持ってこないといけない（負のストック）
T 1????      操作回数は1増える

S 0????  1????  →  操作の必要は無い
T 0????  1????

【ストックあり】（たとえば3とする）
               ↓ストック分を移動させてきたらこうなってる
S ..1????  →  1111????    ここで'1'の塊を切り離して右に移動させる必要がある。
T ..0????      0????       操作回数は1増え、ストックは1増える

S ..0????  →  111????     操作回数は1増える
T ..0????      0????       ストックは変化無し

S ..0????  →  111????     操作の必要は無い
T ..1????      1????       ストックは1減る

S ..1????  →  1111????    操作の必要は無い
T ..1????      1????       ストックは変化無し

【負のストックあり】（たとえば-3とする）
    v 注目中の箇所   ↓負のストック分を考慮するとこうなってる（後の方の1を先取りしている状態）
S ..110011.. →  ..000001..    操作の必要は無い
T ..0?????..     ..0?????..    ストックは1増える

S ..110011.. →  ..100000..    Sの4つの1のうち、先の3つはより左にもっていかないといけない
T ..1?????.. →  ..1?????..    それにくっつけて移動させれば、
                               4つめの1をこの位置に持ってくるのは実質ノーコスト

S ..010111.. →  ..100000..    Sの4つの1のうち、先の3つはより左にもっていかないといけないが
T ..1?????.. →  ..1?????..    その際にSの'0'を飛び越えるのに1操作必要、ストックは1減る

S ..010111.. →  ..000001..    Sの4つの1のうち、先の3つはより左にもっていかないといけないが
T ..0?????.. →  ..0?????..    その際にSの'0'を飛び越えるのに1操作必要

ストックの正負と、$S,T$ の各箇所の組み合わせによって、答えを加算していけばよい。

Python3

def solve(n, s, t):
    s1 = s.count('1')
    t1 = t.count('1')
    if s1 != t1:
        return -1

    ans = 0
    stock = 0
    for i in range(n):
        sc = s[i]
        tc = t[i]
        if sc == '0' and tc == '0':
            if stock != 0:
                ans += 1
        elif sc == '1' and tc == '1':
            pass
        elif sc == '1' and tc == '0':
            if stock >= 0:
                ans += 1
            stock += 1
        else:
            if stock <= 0:
                ans += 1
            stock -= 1

    return ans


n = int(input())
s = input()
t = input()

print(solve(n, s, t))

公式解説によると、「個数の少ない方に着目すると考察が進む場合がある」。なるほど。

今回、1回の操作で'0'は必ず1個しか含まれないため、'0'の方に着目する。

すると、操作は「'0'を、他の'0'を飛び越さない範囲で、移動させることができる」と言い換えられる。
つまり、'0'を互いに区別するとすると、$S→T$ でその順番は変わらない。左から順に対応させることになる。

i 0123456    0の場所(昇順)
S 1110001    [3, 4, 5]
T 1010101    [1, 3, 5]

'0'の移動については、

• 順番を適切に決めれば、1つの'0'は必ず1回で目的の場所に移動させられる
• ある'0'の移動によって、他の'0'の位置が変わることは無い

ので、結局「左から順に $S,T$ での'0'の位置を列挙したとき、異なっている箇所の数」が答えとなる。

例えば上記の例で、位置3は最初から両方とも'0'だが、互いに区別したときに2つは別々の'0'なので、移動が必要となる。
一方、位置5は同じ'0'なので、この場合のみ、移動の必要は無い。

C - ARC Wrecker 2

• 一列に $N$ 個のビルが建ち、高さは $A_1,A_2,...,A_N$
• 区間 $[l,r]$ に対して、以下の条件を満たす区間を「解体可能な区間」とする
• 条件
  • 隣り合う2つのビルの高さを「ともに1増やす」か「ともに1減らす」ことを繰り返して、区間内の全てのビルの高さを0にできる
  • 途中でビルの高さを負にすることはできない
  • 区間外（$A_{l-1}$ より前や $A_{r+1}$ より後）のビルの高さは変えてはいけない
• 全ての区間 $[l,r]$（$1 \le l \lt r \le N$）のうち、解体可能な区間の個数を求めよ
• $2 \le N \le 3 \times 10^5$

隣り合った2つという操作を考えると、区間内の奇数番目と偶数番目のビルの高さの和が同じだったらよいとわかる。

区間の和と言えば累積和。
偶数と奇数に分けて累積和を取る。

A偶数        8     3     5     7     1  
A奇数           6     9     4     2     10

       0     8    11    16    23    24
          0     6    15    19    21     31

で、ある区間 $l,r$ を選ぶとき、計算がどうなるかというと、

                 [ l                 r]
       0     8    11    16    23    24         → 24 - 8 = 16
          0     6    15    19    21     31     → 21 - 6 = 15

加算される値（24,21）は必ず／か＼に隣り合った2つとなる。減算される値（8,6）も同様。

で、この差が偶奇で等しければいいというのは、この隣り合った／＼同士の差が等しければよいと言い換えられる。

                 [ l              r]
       0     8    11    16    23    24         → 23 - 8 = 15
          0     6    15    19    21     31     → 21 - 6 = 15
             ` 2 '            ` 2 '

なので、累積和の／＼の差分を取って、同じ値となる組がどれだけ取れるか、という問題となる。

             0     8    11    16    23    24    
                0     6    15    19    21     31
累積和の差分  0   8  2  5 -4  1 -3 4  2  3  -7

常に「偶数側から奇数側を引いた値」とする点に注意

たとえば累積和の差分が $x$ となる箇所が $k$ 個あったら、その中から2箇所選ぶことが、区間を1つ決めることに対応する。
その場合の数は $\dfrac{k(k-1)}{2}$ で計算できる。

累積和の差分の値ごとに、これを足し合わせればよい。

Python3

from collections import Counter
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))

even = [0]
odd = [0]
for i, a in enumerate(aaa):
    if i % 2 == 0:
        even.append(a)
    else:
        odd.append(a)

even = list(accumulate(even))
odd = list(accumulate(odd))

diff = []
for e, o in zip(even, odd):
    diff.append(e - o)
for e, o in zip(even[1:], odd):
    diff.append(e - o)

cnt = Counter(diff)
ans = 0
for c in cnt.values():
    ans += c * (c - 1) // 2

print(ans)

D - Grid Repainting 3

• $H \times W$ のグリッドが、はじめ、赤か青で塗られている（各マスの初期状態の色は与えられる）
• 以下の一連の操作を好きなだけ繰り返す
  • 赤のマスを1つ選ぶ
  • そのマスと「同じ行の全てのマス」または「同じ列の全てのマス」のいずれかを白で塗り変える
• 操作後の白マスの数を最大化させる操作手順の一例を構築せよ
• $1 \le H,W \le 2500$

上手いことしないと、赤マスの操作によって、同じ行や列にある他の赤マスが消えてしまう。

このように「グリッドで、行全体または列全体に対して操作する」問題では、行、列をそれぞれ1グループとした二部グラフで表現する解法がある。

ぶっちゃけ公式解説が親切なのでそれ読む。

• 解説 - AtCoder Regular Contest 119

連結成分毎に操作を求める。

合計 $N$ 頂点の二部グラフなら、最大の操作回数は $N-1$ 回となり、連結成分が表す行・列の全体の集合のどれか1方向の操作は諦めないといけない。 逆に言うと、$N-1$ 回の操作は上手くすると達成できる。

  012345678
0 _________    連結成分は、1,3行、2,4,6列の5頂点。
1 __R_R_R__    この内、どれか1つ以外の計4つの行・列は白く塗れる。
2 _________
3 __R_R_R__    行を残すならどの行を残しても同じ。
4 _________    列を残すならどの列を残しても同じ。

連結成分について、適当に根を決めて全域木をとってやると、とりあえずは根から葉に向かう方向に、その辺が表す赤マスを使えばよい。 ただし最後に調整が必要となる（後述）。

  0123
0 R___        _ :青マス
1 ____
2 ____
3 R_R_

    列0         辺が各赤マスを表す
   ↙  ↘
 行0    行3     (0,0) は行(X)方向
        ↓      (3,0) は行(X)方向
        列2     (3,2) は列(Y)方向 に使う

操作順に関しては葉から操作していくと、連結成分内の他の赤マスを邪魔しない。

つまり、最後に操作するのは根から伸びる1辺のうちのどれか1つ¹⁾、ということになる。
この最後の1辺に関しては、XY方向を逆転させた方が多く白マスを塗り替えられる可能性がある。

  0123456789  
0 RRRRRR____            行0
1 __________        ↙↙↓↓↘↘
2 __________     列0,1, 2,3, 4,5

このままでは全てY方向に塗ることになってしまうが、
どれか1つはX方向に塗った方が明らかによい（最後の操作として）

しかし、結局どちらがよいのかは、他の連結成分の配置にも依存してくるので、すぐにはわからない。
なので、各連結成分につき最後の1操作だけは「保留」としておく。

  0123456789  
0 RRRRRR____    こんなんだったら、
1 __________    右下の連結成分も多くはY方向に塗ることになるので、
2 __________    X方向に塗る価値が下がる
3 ______RRRR

新規に白く塗り替えられるマスが行・列でいくつ残っているかを管理しながら、保留以外の操作を求めていく。

全ての連結成分を決め終えると、連結成分の個数分だけ、保留中の赤マスが残っている。

  0123456789  
0 Rxxxxx_xxx  x:白マス
1 _xxxxx_xxx  残っている非白マス  (行・列)＝(4, 2)
2 _xxxxx_xxx
3 _xxxxxRxxx

この残った赤マスは、元々別々の連結成分だったことから互いに干渉することはないので、独立に、残っている白マスのうち多い方向の操作を選ぶことができる。

上記の例では、行方向に多く残っているので、両方ともY方向に操作したら4マスを新規に塗り替えられる、ということになる。

これで保留中の赤マスも確定し、答えが求められた。

Python3

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


h, w = map(int, input().split())
field = [input() for _ in range(h)]

red = []
for i in range(h):
    for j, c in enumerate(field[i]):
        if c == 'R':
            red.append((i, j))

uft = UnionFind(h + w)
links = [set() for _ in range(h + w)]

for i, j in red:
    if uft.unite(i, j + h):
        links[i].add(j + h)
        links[j + h].add(i)


def dfs(s, used, remain):
    q = [s]
    used[s] = True
    parents = {}
    result = []
    while q:
        v = q.pop()
        if v == s:
            pass
        elif v >= h:
            i = parents[v]
            j = v - h
            result.append([1, i, j])
            remain[1] -= 1
        else:
            i = v
            j = parents[v] - h
            result.append([0, i, j])
            remain[0] -= 1
        for u in links[v]:
            if used[u]:
                continue
            used[u] = True
            parents[u] = v
            q.append(u)

    result.reverse()

    last = result.pop()
    assert last[0] == 1
    remain[1] += 1

    return result, last


ans = []
used = [False] * (h + w)
remain = [h, w]
lasts = []
for v in range(h):
    if used[v] or len(links[v]) == 0:
        continue

    result, last = dfs(v, used, remain)
    for d, i, j in result:
        xy = 'XY'[d]
        ans.append(f'{xy} {i + 1} {j + 1}\n')
    lasts.append(last)

rev = remain[0] < remain[1]
for d, i, j in lasts:
    xy = 'XY'[d ^ rev]
    ans.append(f'{xy} {i + 1} {j + 1}\n')

print(len(ans))
print(''.join(ans))

E - Pancakes

• $N$ 枚のパンケーキが積み重なり、上から $i$ 番目の大きさは $A_i$
• ある区間のパンケーキの重なり順を、1回だけまるっとひっくり返せる
  • 1回もひっくり返さなくてもよい
• パンケーキの「見栄えの悪さ」を以下で定義する
  • 隣り合う2枚の大きさの差の総和
  • つまり、$1 \le i \lt N$ について、$|A_i-A_{i+1}|$ の総和
• ひっくり返す区間を適切に決めて、見栄えの悪さを最小化せよ
• $2 \le N \le 3 \times 10^5$

式を立てて、絶対値を場合分けにより外す。

1回しかひっくり返さないので、ほとんどのパンケーキの両隣は変わらない。

変わるのは、区間を $[l+1,r]$ と決めたとすると、以下の通り。

     l [ l+1      r ] r+1
... 10    5  ...  8    3  ...    (10-5) と (8-3) が消え、
              ↓
... 10    8  ...  5    3  ...    (10-8) と (5-3) が追加される

• 差分
  • $D_{l,r}=-|A_l-A_{l+1}|-|A_r-A_{r+1}|+|A_l-A_r|+|A_{l+1}-A_{r+1}|$

この差分を比較して、最小のものを求めればよい。
1回もひっくり返さない場合は $0$ であり、どれだけ負側に絶対値を大きく出来るか、ということになる。

ただし、区間の左端が $l=0$ や、右端が $r=N-1$ の場合は、外側のパンケーキが存在しないため少し変わる。
この2つの場合は $O(N)$ でそれぞれ全探索できるので、それで処理する。

• $[l,r]=[0,i]$ のとき、$D_{-1,i}=-|A_i-A_{i+1}|+|A_0-A_{i+1}|$
• $[l,r]=[i,N-1]$ のとき、$D_{i,N-1}=-|A_i-A_{i+1}|+|A_i-A_{N-1}|$

以下、区間の両端とも全体の端でない場合を考える。

絶対値が4つも出てくるが、大小関係を決め打って、そのうち2つを外してやる。

• $A_l \le A_{l+1}, A_r \le A_{r+1}$ のとき
  • $D_{l,r} = 2\max(A_l,A_r)-2\min(A_{l+1},A_{r+1})$
• $A_l \le A_{l+1}, A_r \gt A_{r+1}$ のとき
  • $D_{l,r} = 2\max(0, A_l-A_r)+2\max(0, A_{r+1}-A_{l+1})$
• $A_l \gt A_{l+1}, A_r \le A_{r+1}$ のとき
  • $D_{l,r} = 2\max(0, A_r-A_l)+2\max(0, A_{l+1}-A_{r+1})$
• $A_l \gt A_{l+1}, A_r \gt A_{r+1}$ のとき
  • $D_{l,r} = -2\min(A_l,A_r)+2\max(A_{l+1},A_{r+1})$

このうち2番目と3番目に関しては、0未満にならないため、考えても無駄とわかる。

1番目と4番目は $A_i$ と $A_{i+1}$ の大小関係で2つにグループ分けでき、

• $A_i \le A_{i+1}$ グループから2個選び、$2\max(A_l,A_r)-2\min(A_{l+1},A_{r+1})$ を最小化する
• $A_i \gt A_{i+1}$ グループから2個選び、$-2\min(A_l,A_r)+2\max(A_{l+1},A_{r+1})$ を最小化する

この2つを試せばよい。
（記号の付け方がまずかったが）この考え方では、$l,r$ といっても $l$ が必ず左に位置しなくてもよく、 単にペアの片方であればよいことが、$l,r$ を入れ替えても式の内容が変わらないことからわかる。

1番目のグループについて、ここでさらに、$A_l \le A_r$ を仮定する。
グループを $A_i$ 順にソートして、小さい方から順に $(l,r)$ ペアの $r$ とし、 既に処理済みのどれかとペアにすることを考えると、その状態が保たれる。

すると、

• $\max(A_l,A_r)=A_r$
• $\min(A_{l+1},A_{r+1})$ は、減算されるので大きければ大きいほどよい
  • $A_{l+1}$ は、「今までに処理された $i$ の中で、$A_{i+1}$ が最大のもの」を使えばよい

$A_{i+1}$ の最大値を順次更新していけば、$r$ を固定したときの $D_{l,r}$ の最小値が $O(1)$ で求まる。

全体では、グループサイズを $G$ として $O(G \log{G})$ でグループ内の最小値を求められる。ソートがボトルネックとなる。

同様の処理を4番目のグループについても行う。

これらの差分の最小値を、初期状態の見栄えの悪さと合わせれば答え。

Python3

n = int(input())
aaa = list(map(int, input().split()))

diff = [abs(a0 - a1) for a0, a1 in zip(aaa, aaa[1:])]

ans = 0
le = []
gt = []

for i in range(n - 1):
    ans = min(ans, abs(aaa[0] - aaa[i + 1]) - diff[i])
    ans = min(ans, abs(aaa[i] - aaa[n - 1]) - diff[i])
    if aaa[i] <= aaa[i + 1]:
        le.append((aaa[i], aaa[i + 1]))
    else:
        gt.append((aaa[i + 1], aaa[i]))

if len(le) >= 2:
    le.sort()
    tmp_max = le[0][1]
    for a0, a1 in le[1:]:
        ans = min(ans, (a0 - min(a1, tmp_max)) * 2)
        tmp_max = max(tmp_max, a1)

if len(gt) >= 2:
    gt.sort()
    tmp_max = gt[0][1]
    for a0, a1 in gt[1:]:
        ans = min(ans, (a0 - min(a1, tmp_max)) * 2)
        tmp_max = max(tmp_max, a1)

print(sum(diff) + ans)

$D_{i,j}$ の絶対値を外すとき、仮定する方を $(A_i,A_{i+1})$ 間の大小関係でなく $(A_l, A_r)$ 間としてしまうと、 同じグループに属する中での最小値を簡単に求めることができず、考察が進まなくなってしまった。

ここの組合せを変えてみるってのは思いついても良かったね。