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

AtCoder Regular Contest-- 224

B - Adjacent Tiles

問題文

同じ大きさの正方形のタイル $N$ 枚を、平面上に重ならないように配置します。
このとき、一辺を完全に共有している相異なるタイルのペアの個数は最大でいくつになりますか？
- ただし、タイルのペア $(a,b)$ が一辺を完全に共有するとは、 $a$ のある辺と $b$ のある辺が完全に一致することをいいます。

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

制約

$1 \le T \le 2 \times 10^5$
$1 \le N \le 10^{18}$
入力はすべて整数

解法

こうだろうという直感が概ね正解ではあるが、ちゃんと証明しようと思うと丁寧な思考が必要。

$\left \lfloor \sqrt{N} \right \rfloor$ 四方の正方形に置いて、余った分はもう1つ外側の行・列にL字に追加していく、という方法が1つの正解となる。

N=11      N=14
■■■■  ■■■■
■■■■  ■■■■
■■■□  ■■■■
          □□■■

まぁ直感的に、長方形が強そうというのは分かる。外周以外の全タイルが4辺全てを共有できるので。
同じ面積の長方形なら2辺の差が小さいほど外周が短くなることから連想すると、この場合も、同じ長方形に並べるのでも正方形に近い方がより強そう。

全長方形の辺 $4N$ 個から、ペアにできない辺の最小化を考える。
ペアにできない辺数を $m$ とすると、答えは $\dfrac{4N-m}{2}$ となる。

$m$ は、図形に穴が無ければ外周の長さと一致する。
さらに凹みが無ければ、その図形の外周はそれをすっぽり覆う長方形と一致する。
凹みや穴があれば、明らかに外周はそれより増える。

よって、すっぽり覆う長方形がなるべく正方形に近くなるように置けば、$m$ を最小化できる。

より厳密な説明
- physics0523氏によるEditorial

Python3

from math import sqrt


def int_sqrt(n):
    r = int(sqrt(n))
    while (r + 1) ** 2 <= n:
        r += 1
    while r * r > n:
        r -= 1
    return r


def solve(n):
    r = int_sqrt(n)
    ans = 0
    for h in range(max(1, r - 10), r + 3):
        w = n // h
        rem = n - h * w
        tmp = 2 * h * w - h - w
        if rem == 1:
            tmp += 1
        elif rem > 1:
            tmp += rem * 2 - 1
        ans = max(ans, tmp)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    ans = solve(n)
    print(ans)

C - Ascending Labels

問題文

$N$ 頂点 $M$ 辺の連結な単純無向グラフが与えられます。
頂点には $1,2,\ldots,N$ の番号が付けられており、$i$ 個目の辺は頂点 $U_i$ と頂点 $V_i$ を結びます。
以下の条件をすべて満たす整数列 $A=(A_1,A_2,\ldots,A_N)$ を $1$ つ構築してください。
- すべての頂点 $v$ について、$0 \le A_v \le N$ である。
- $A_1=0$ である。
- 頂点 $1$ 以外のすべての頂点 $v$ について、$v$ に隣接する頂点 $w$ のうち $A_w=A_v-1$ を満たすものがちょうど $1$ つ存在する。
なお、本問題の制約下で、上記の条件をすべて満たす整数列が少なくとも $1$ つ存在することが証明できます。また、条件を満たす整数列が複数存在する場合、どれを出力しても正答とみなされます。

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

制約

$1 \le T \le 3 \times 10^4$
$1 \le N \le 3 \times 10^5$
$N-1 \le M \le 3 \times 10^5$
$1 \le U_i \lt V_i \le N$
$i \neq j$ ならば $(U_i,V_i) \neq (U_j,V_j)$
与えられるグラフは連結
ひとつの入力における $N$ の総和は $3 \times 10^5$ 以下
ひとつの入力における $M$ の総和は $3 \times 10^5$ 以下
入力はすべて整数

解法

DFS木を構築し、頂点 $1$ からの距離を $A_v$ とすればよい。

基本、（DFS木で無くても）何らかの全域木で頂点 $1$ からの距離を $A_v$ とすれば、「★ $v$ に隣接する頂点 $w$ のうち $A_w=A_v-1$ を満たすものが存在する」ようにはできる。（距離 $d$ にたどり着くには $d-1$ を経由しなければならないのは当然）

問題は、全域木に元の辺を戻して考えたとき、★が「ちょうど $1$ つ」になることを保証できない点。

①
↓↘      ↓:全域木の辺
②  ③    ：:全域木以外の辺
↓↘：
④  ⑤    A2=A3=1, A5=2 となるのに、⑤が②③の両方と繋がってしまっている

DFS木なら、一度訪れた頂点と繋がっている未訪問頂点は探索され尽くすので、使われない辺は、必ずDFS木での「祖先と子孫を結ぶ辺」となる。別の部分木同士の頂点が結ばれることは無い。

よって、DFS木に使われていない辺同士が結ぶ2頂点は $|A_w-A_v| \ge 2$ となるので、木の親の他に★が増えることは無い。

Python3

def dfs(n, links, s=0):
    q = [s]
    progress = [0] * n
    values = [-1] * n
    values[s] = 0
    while q:
        u = q[-1]
        if progress[u] == len(links[u]):
            q.pop()
            continue
        v = links[u][progress[u]]
        progress[u] += 1
        if progress[v] != 0:
            continue
        values[v] = values[u] + 1
        q.append(v)
    return values


def solve(n, m, edges):
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)
    ans = dfs(n, links)
    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(*ans)

D - Angst for All Pairs

問題文

$N$ 枚のカードがあり、$1$ から $N$ までの番号が付けられています。はじめはどのカードも何も書かれていません。
あなたはそれぞれのカードに $0$ 個以上の正整数を書き込むことができます。
正整数 $k$ を $1$ 回書き込むときにかかるコストは、$k$ の十進表記での桁数に等しいです。
以下の条件を満たすことが可能か判定し、可能であれば必要な総コストの最小値を、不可能であれば $-1$ を出力してください。
- $1 \leq x \lt y \leq K$ を満たすどの正整数組 $(x,y)$ についても、そのうち片方だけを含むカードが存在する。

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

制約

$1 \leq T \leq 10^5$
$1 \leq N \leq 10^6$
$2 \leq K \leq 10^6$
ひとつの入力における $N$ の総和は $10^6$ 以下
ひとつの入力における $K$ の総和は $10^6$ 以下
入力はすべて整数

解法

整数 $x$ を書き込むカードの集合を $S_x \subset \{1,2,...,N\}$ とする。
もし $S_x$ と $S_y$ が一致すれば、「$x,y$ の一方のみが書かれたカード」は存在しない。
逆に1つでも異なればよいので、$N$ 枚のカードでは $1～2^N$ の範囲の整数組を区別できることになる。

まず $K \gt 2^N$ なら不可能、そうでなければ可能となる。以下、可能とする。

$x$ の桁数を $k_x$ とすると、$k_x|S_x|$ が $x$ を書き込む総コストとなる。 $k_x$ が大きい方から、なるべく $|S_x|$ が小さいような集合を与えればよい。

S_{K}     = {}  （空集合）
S_{K-1}   = {1}
S_{K-2}   = {2}
 :
S_{K-N}   = {N}
S_{K-N-1} = {1,2}
S_{K-N-2} = {1,3}
 :

のように、大きい整数から、小さい集合を割り当てていけばよい。

実装としてはいろいろあるが、

左辺側: $1～K$ の $(桁数, その桁数となる値の個数)$ を、桁数の降順に並べた列
- $K \le 10^6$ なので、高々 $7$ 要素
右辺側: $(要素数, その要素数となる集合の個数)$ を、要素数の昇順に並べた列
- 集合の個数は二項係数で計算できる。
- 要素数の小さい方から並べ、累計が $K$ 個を超えたら打ち切ってよい。だいたい $20$ もあれば超える。

この2つを、先頭から同個数分だけマッチングさせていけばよい。
右辺側は、枝刈りせず例えば要素数 $N$ まで毎ケース作るとTLEしてしまうので、枝刈りは必須。

Python3

def iter_binom(n, k):
    # k=0,1,2,... の順に、nCk を返す。mod取らないので大きくなるような状況で呼ばないように。
    res = 1
    yield res
    for i in range(1, n + 1):
        res *= n - i + 1
        res //= i
        yield res


def solve(n, k):
    if (1 << n) < k:
        return -1

    tmp = 1
    binoms = [(0, 1)]
    total = 1
    while total < k:
        i = len(binoms)
        tmp *= n - i + 1
        tmp //= i
        binoms.append((i, tmp))
        total += tmp

    d = len(str(k))
    if d == 1:
        digits = [(d, k)]
    else:
        digits = [(d, k - 10 ** (d - 1) + 1)]
        for dd in range(d - 1, 0, -1):
            digits.append((dd, 10 ** dd - 10 ** (dd - 1)))

    binoms.reverse()
    digits.reverse()
    ans = 0
    while digits:
        b, c1 = binoms.pop()
        d, c2 = digits.pop()
        if c1 == c2:
            ans += b * d * c1
        elif c1 < c2:
            ans += b * d * c1
            digits.append((d, c2 - c1))
        else:
            ans += b * d * c2
            binoms.append((b, c1 - c2))
    return ans


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

E - ABC|AB|A

問題文

A, B, C からなる文字列 $S$ が与えられます。
以下の操作を $0$ 回以上何回でも行えます。
- $S$ から A または AB または ABC である部分文字列 (連続部分列) を $1$ つ選択して削除する。残った文字は順序を保って連結される。
最終的な $S$ の長さとして達成可能な最小値を求めてください。

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

制約

$T$ は $1$ 以上 $10^5$ 以下の整数
$S$ は A, B, C からなる長さ $1$ 以上 $10^6$ 以下の文字列
ひとつの入力における $|S|$ の総和は $10^6$ 以下

解法

'AABCBC' など、間を削除した結果、前後の 'A' と 'BC' が繋がって新たに削除可能になる、ということもある。
このようなケースはスタックを用いて管理し、削除可能になったら pop していくと上手く管理できる。

ただ、先頭から溜めていくと、例えば 'AB' まで溜まったとして、これを即座に削除していいのか、後から 'C' が繋がって 'ABC' として削除できるのか、その時点で確定できない。

逆から考えると見通しが良くなる。

'CBA'|'BA'|'A' を削除できるとして、逆からスタックに溜めていくと、 'BA' と溜まった時点で、もうこれは 'BA' 以外の何者にも発展することはないので削除してよい。
（'A' のみ削除し、残った 'B' に後から別の 'A' が繋がって 'BA' として削除、という操作もできなくは無いが、それは現時点で 'BA' として削除し、別の 'A' は単独で削除するものと組み替えて、損しない）

'A' が来るたび、以下のようにすればよい。

スタック末尾が 'CB' なら 'CBA' として削除（2つpop）
スタック末尾が 'B' なら 'BA' として削除（1つpop）
スタック末尾がそれ以外なら 'A' として削除

それ以外はスタック末尾に追加していき、最終的なスタック長が答えとなる。

Python3

def solve(s):
    stack = []
    for c in reversed(s):
        if c == 'A':
            if len(stack) >= 1 and stack[-1] == 'B':
                if len(stack) >= 2 and stack[-2] == 'C':
                    stack.pop()
                stack.pop()
        else:
            stack.append(c)
    return len(stack)


t = int(input())
for _ in range(t):
    s = input()
    ans = solve(s)
    print(ans)

F - AND/OR

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ と整数 $K$ が与えられます。
はじめ、$x=0$ です。$i=1,2,\dots,N$ の順に、以下の $2$ つの操作のうち一方を選んで行います。
- 操作 $1$ : $x$ を $x$ ${\rm AND}$ $A_i$ に置き換える。
- 操作 $2$ : $x$ を $x$ ${\rm OR}$ $A_i$ に置き換える。
ただし、操作 $2$ を選ぶ回数は全体で $K$ 回以下でなければなりません。
全ての操作が終了した時点の $x$ として達成可能な最大値を $M$ とします。
最終的な $x$ が $M$ となる操作列の個数を $998244353$ で割った余りを求めてください。
ただし、$2$ つの操作列は、ある整数 $j$ ($1 \le j \le N$) について $j$ 回目に選んだ操作が異なるとき、またそのときに限り区別されます。

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

制約

$1 \le T \le 10^4$
$1 \le K \le N \le 2 \times 10^5$
$0 \le A_i \lt 2^{60}$
ひとつの入力における $N$ の総和は $2 \times 10^5$ 以下
入力はすべて整数

解法

落ち着いて考えれば難しくはない。

末尾 $K$ 要素を OR した結果を $m$ とすると、達成可能な最大値 $M=m$ となる。

略証

$m$ で立っている各 bit に対し、末尾から見たときにはじめて '1' が現れる index を求め、その中で最も小さいものを $l$ とする。

 i  A（2進表記）
    1234567 桁目
 :
 8  0110010  ← 3,6桁目の'1'が、末尾から見てはじめて i=8 で現れ、これが最小
 9  1100100     よって l=8 となる。
10  1000101
-----------
 m  1110111

この時、$l$ より後の $i$ では、必ず OR 操作が必要となる。 AND にすると、$m$ で立てなければならないはずの bit が '0' になってしまうので。

$l$ 自身は、OR と AND の両方の可能性がある。

OR にしたら、$l$ より前はどう操作しても結果が $m$ になることが保証される。
$l$ 以降の OR 操作分を除いた、$l$ より前に使える OR 操作の回数を $r$ として $\displaystyle \sum_{k=0}^{r} \binom{l-1}{k}$ があり得る操作の数となる。

AND にした場合、再帰的に同じ構造の問題に帰着できる。

$N←l-1$
$K←K-$（$l$ より後に必要な OR 操作分）
$m$ は、$l$ ではじめて '1' が現れたbitの集合とする。
- 上例の場合、3,6 桁目は $l$ ではじめて立つので、$m←0010010$

$i=l-1$ の操作終了時点で 3,6 桁目を '1' にできれば、$l$ をAND、それ以降をORにすることで、$M$ を達成できる。

よって、新しい $N,K,m$ で同様に

$l$ を求める。
- ただし、今度は必ずしも存在するわけではない。$m$ で立っている bit のうち1つでも、末尾 $K$ 個内に '1' が立っているのが無いものがある場合、そこで終了。
$l$ をORにした場合は確定。$l-1$ 以前の決め方を答えに加算
ANDにした場合は再帰的に同じ問題に帰着する

ということを繰り返せばよい。$N=0$ または $K=0$ または $m=0$ になったら終了。

後は、$l$ をORにした時、$\displaystyle \sum_{k=0}^{r} \binom{l-1}{k}$ を求める部分。
愚直にやってしまうと、1回につき $O(r) \simeq O(K)$ かかるので、 $K$ がなかなか減らないまま再帰が深くなる場合に $O(NK)$ の計算量を要してしまう。

二項係数の累積和 $\displaystyle f(n,r)=\sum_{k=0}^{r} \binom{n}{k}$ を計算する時のテクニックとして、 $f(n,r)$ の結果から $f(n-1,r)$ や $f(n,r-1)$ を $O(1)$ で計算できることを活かせば、$O(N+K)$ に抑えられる。

Python3

def precompute_factorials(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


# Codon は内部関数によるリストのクロージャ捕捉に失敗するため、トップレベルで全部引数渡し
def ncr(n, r, facts, finvs, MOD):
    return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD


def binom_prefix(pn, pr, pv, n, r, facts, finvs, MOD, INV2):
    # sum_{k=0}^{pr} pnCk = pv であることが分かっている状態から、sum_{k=0}^{r} nCk を求める。
    # 簡単のため、pn>n 前提
    if n <= r:
        return pow(2, n, MOD)
    while pn > n:
        if pr > r:
            pv = (pv - ncr(pn - 1, pr, facts, finvs, MOD)) * INV2 % MOD
            pn -= 1
            pr -= 1
        else:
            pv = (pv + ncr(pn - 1, pr, facts, finvs, MOD)) * INV2 % MOD
            pn -= 1
    while pr < r:
        pr += 1
        pv = (pv + ncr(pn, pr, facts, finvs, MOD)) % MOD
    while pr > r:
        pv = (pv - ncr(pn, pr, facts, finvs, MOD)) % MOD
        pr -= 1
    return pv


def solve(n, k, aaa, facts, finvs):
    # print(*(f'{a:b}' for a in aaa))

    MOD = 998244353
    INV2 = pow(2, MOD - 2, MOD)

    ma = max(aaa)
    if ma == 0:
        ans = 0
        for i in range(k + 1):
            ans += ncr(n, i, facts, finvs, MOD)
        ans %= MOD
        return ans

    max_d = len(bin(ma)) - 2
    bit_pos = [[-1] for _ in range(max_d)]
    for i in range(n):
        a = aaa[i]
        for j in range(max_d):
            if (a & (1 << j)) > 0:
                bit_pos[j].append(i)

    m_bits = []
    limit = n - k
    mostfront_i = n
    mostfront_bits = []
    for i in range(max_d):
        if bit_pos[i][-1] >= limit:
            m_bits.append(i)
            if mostfront_i > bit_pos[i][-1]:
                mostfront_i = bit_pos[i][-1]
                mostfront_bits = [i]
            elif mostfront_i == bit_pos[i][-1]:
                mostfront_bits.append(i)
    # print(f'{m_bits=} {mostfront_i=} {mostfront_bits=}')

    rem = k - (n - mostfront_i) + 1
    # mostfront_i より後はOR確定。mostfront_i を OR で取るなら、それより前は自由確定。ANDなら、再帰的
    ans = 0
    for i in range(rem):
        ans += ncr(mostfront_i, i, facts, finvs, MOD)
    ans %= MOD
    pn = mostfront_i
    pr = rem - 1
    pv = ans

    # 再帰の sub は Codon でクロージャを捕捉できないため末尾再帰をループに展開
    cn, ck, c_bits = mostfront_i, rem, mostfront_bits
    while ck > 0 and c_bits:
        # print(f'  sub {cn=} {ck=} {c_bits=}')
        limit = cn - ck
        mostfront_i = cn
        mostfront_bits = []
        ok = True
        for b in c_bits:
            while bit_pos[b][-1] >= cn:
                bit_pos[b].pop()
            if bit_pos[b][-1] < limit:
                ok = False
                break

            if mostfront_i > bit_pos[b][-1]:
                mostfront_i = bit_pos[b][-1]
                mostfront_bits = [b]
            elif mostfront_i == bit_pos[b][-1]:
                mostfront_bits.append(b)
        if not ok or mostfront_i == -1:
            break
        rem = ck - (cn - mostfront_i) + 1
        pv = binom_prefix(pn, pr, pv, mostfront_i, rem - 1, facts, finvs, MOD, INV2)
        ans += pv
        pn = mostfront_i
        pr = rem - 1
        cn, ck, c_bits = mostfront_i, rem, mostfront_bits

    ans %= MOD
    if ans < 0:
        ans += MOD
    return ans


def main():
    MOD = 998244353
    facts, finvs = precompute_factorials(200_000, MOD)

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


main()

目次

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

B - Adjacent Tiles

問題文

制約

解法

C - Ascending Labels

問題文

制約

解法

D - Angst for All Pairs

問題文

制約

解法

E - ABC|AB|A

問題文

制約

解法

F - AND/OR

問題文

制約

解法