AtCoder Beginner Contest 475 E,F,G問題メモ

AtCoder Beginner Contest 475

E - Quiz Competition: Qualifiers

問題文

クイズ大会の予選が行われました。参加者は $1$ から $N$ の番号がついた $N$ 人で、予選を通過できるのは最大で $M$ 人です。
予選は $K$ 問の $2$ 択クイズからなり、各問題の答えは o または x です。参加者 $i$ の $j$ 問目の問題に対する回答は文字列 $S_i$ の $j$ 文字目として与えられます。$j$ 問目の問題の正解は文字列 $T$ の $j$ 文字目として与えられます。
予選通過者は以下の手順により決定されます。
- 最初、予選通過者および予選脱落者は $0$ 名であり、参加者 $N$ 人全員が未確定者である。
- $k=1,2,\dots,K$ の順に以下の処理を行う。
  - 予選通過者と、未確定者のうち $k$ 問目の正解者をあわせた人数が $M$ 人以下なら、未確定者のうち $k$ 問目の正解者全員を予選通過者とする。
  - そうでないなら、未確定者のうち $k$ 問目の不正解者全員を予選脱落者とする。
- 未確定者全員を予選脱落者とする。
$Q$ 個のクエリが以下の形式で与えられます。順に処理してください。
- 整数 $i, j$ が与えられる。参加者 $i$ の $j$ 問目の問題に対する回答を o なら x に、x なら o に変更する。その後、参加者 $i$ が予選通過できるかどうかを判定する。
なお各クエリにおける回答変更は以降のクエリを処理する際にも残り続けます。

制約

$1 \leq M \leq N \leq 3\times 10^4$
$1 \leq K \leq 200$
$S_i,T$ は o, x のみからなる長さ $K$ の文字列
$1 \leq Q \leq 5\times 10^4$
各クエリについて、$1\leq i \leq N$、$1 \leq j \leq K$

解法

正解 $T$ が全て “ooooo…o” となるように “x” の箇所を反転させる。参加者の回答もそれに合わせて同じ位置を反転させる。
初期状態をこのように変更しても答えには影響しない。

さらに、これを “o”→$0$、“x”→$1$ と変換し、それを2進数として捉える。以下、この値を各参加者の「回答」とする。

T  oxo  →  ooo  →  000

S  oxo  →  ooo  →  000
   oxx  →  oox  →  001
   xxo  →  xoo  →  100
   xoo  →  xxo  →  110
   xox  →  xxx  →  111

予選通過者とは、「全ての参加者の回答を小さい順に並べたとき、$M+1$ 番目の参加者の回答より真に小さい回答をした人」と言い換えられる。ただし、$N=M$ のとき $M+1$ 番目の参加者の回答は “1111…1” であるとする。

「通過枠が余っていても、次点の同率を全て通過させたら $M$ 人を超えるなら通過できない」「1問は正解しないと通過判定の俎上にすら載せられない」という問題設定上、このような判定となる。

参加者の回答は最大 $K \le 200$ bitの整数値となるが、 Python なら多倍長でそのまま整数として扱い、sortedcontainers.SortedList などで更新を反映させればよい。

SortedList の追加・削除を $O(\log{要素数})$ として ¹⁾、 $O(NK+Q\log{N}\frac{K}{\mathrm{word}})$ 程度で解ける。

Python3

from sortedcontainers import SortedList


def solve(n, m, k, t, sss, q, queries):
    ss = SortedList()
    rev = ['ox'.index(x) for x in t]
    sss2 = []
    for s in sss:
        val = 0
        for i in range(k):
            x = 'ox'.index(s[i]) ^ rev[i]
            if x == 1:
                val |= 1 << (k - i - 1)
        ss.add(val)
        sss2.append(val)
    buf = []
    ss.add((1 << k) - 1)
    for i, j in queries:
        i -= 1
        j -= 1
        before = sss2[i]
        after = before ^ (1 << (k - j - 1))
        sss2[i] = after
        ss.remove(before)
        ss.add(after)
        x = ss[m]
        if after < x:
            buf.append('Yes')
        else:
            buf.append('No')
    return buf


n, m, k = list(map(int, input().split()))
t = input()
sss = [input() for _ in range(n)]
q = int(input())
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, k, t, sss, q, queries)
print('\n'.join(ans))

F - Rectangle Filling

問題文

白（“.”）または黒（“#“）に塗られた $H$ 行 $W$ 列のマス目が与えられます。
あなたは、以下の操作を高々 $1$ 回行うことができます。
- ある矩形領域を $1$ つ選び、その領域内のマスをすべて黒く塗る。
得られるマス目の状態として考えられるものの個数を求めてください。

制約

$1 \leq H, W$
$H \times W \leq 2 \times 10^5$
$H, W$ は整数
$S_i$ は ., # からなる長さ $W$ の文字列

解法

$H \le W$ を仮定する。違う場合は転置しておく。

選んだ矩形領域について、「上下左右、少なくともどれか1辺が元から全て黒である」ものは、その黒い辺を除いた矩形領域を選んだ場合とできあがる盤面が重複する。

..[####].
.#[..#.]#  ここを選んだのは
#.[#..#].

...####..
.#[..#.]#  ここを選んだときとできあがる盤面が重複する。
#.[#..#].

よって、「上下左右いずれの辺も全て黒ではない矩形領域の個数」を求めたい。
それに、操作しなかった場合の $1$ 個を加えたものが答えとなる。

包除原理で求める。

$T_i:=$ 上下左右の内、明示的に $i$ 辺が全て黒であるような矩形の個数（$i=0～4$）
$\mathrm{Ans}=T_0-T_1+T_2-T_3+T_4+1$

包除原理の定義上、同じ矩形領域であっても着目している辺が異なる場合は重複して数える。

####  T1には 上、左、右 の3回分数える。
#..#  T2には (上左)、(上右)、(左右) の3回分数える。

「マス $(i,j)$ から上/下/左/右に、$(i,j)$ を含めて黒マスがいくつ連続しているか」 $U[i,j],D[i,j],L[i,j],R[i,j]$ を計算しておく。

$T_0$ は（色関係なく）全ての矩形領域の取り方。$T_0=\dfrac{H(H+1)}{2} \times \dfrac{W(W+1)}{2}$

$T_1,T_2$ は割愛。

$T_3$ は、凵の下辺として使う行を固定する。
行の中の黒マスの連続ごとに考える。$j$ を黒マス連続の左端とし、$r=R[i,j]$ とする。

   ..#..#..
   ..#.##..
i→..####..
     [---)
     j  j+r

$j \le k \le l \lt j+r$ なる $k,l$ を左辺・右辺として選んだ時、 $\min(U[i,k],U[i,l])$ が、凵の形になるような最大高さとなる。これを全ての $k,l$ について合計したい。

愚直にやると行毎に $O(W^2)$ かかるが、上手くやると $O(W \log{W})$ で求められる。
$U[i,j:j+r]$ をソートしたものを $U'$ とする。 $k$ を固定すると $k \le l$ の範囲にある $l$ とのペアは全て $\min(U'[k],U'[l])=U'[k]$ なので、 $\displaystyle \sum_{k=1}^{r}U'[k]\times (r-k+1)$ として求められる。

これを4方向でやると $T_3$ となる。

$T_4$ は、$O(H^2W)$ で求められる。
下端となる列 $d$ を固定し、そこから上端となる列 $u$ を上方向に試していく。$u$ 毎に、以下を計算する。

$\mathrm{valid}[k]:=$ 列 $k$ において、$d$ から $u$ まで黒マスが続いていたら $1$、途切れてたら $0$
$\mathrm{acc}[k]:=\mathrm{valid}$ の累積和

その後、左端となる列 $j$ を固定すると、$r=\min(R[u,j],R[d,j])$ とし、 $[j,j+r)$ の間にある $\mathrm{valid}[k]=1$ の個数が、$d,u$ を固定した時の答えとなる。これは $\mathrm{acc}$ から求められる。

Python3

from itertools import accumulate


def solve(h, w, grid):
    # h <= w となるように転置
    if h > w:
        grid = list(zip(*grid))
        h, w = w, h

    u_con = [[0] * w for _ in range(h)]
    d_con = [[0] * w for _ in range(h)]
    l_con = [[0] * w for _ in range(h)]
    r_con = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.':
                continue
            u_con[i][j] = u_con[i - 1][j] + 1 if i > 0 else 1
            l_con[i][j] = l_con[i][j - 1] + 1 if j > 0 else 1
    for i in range(h - 1, -1, -1):
        for j in range(w - 1, -1, -1):
            if grid[i][j] == '.':
                continue
            d_con[i][j] = d_con[i + 1][j] + 1 if i < h - 1 else 1
            r_con[i][j] = r_con[i][j + 1] + 1 if j < w - 1 else 1

    t0 = (h * (h + 1) // 2) * (w * (w + 1) // 2)
    t1 = 0
    t2 = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.':
                continue
            t1 += l_con[i][j] * (h + 1)
            t1 += u_con[i][j] * (w + 1)
            t2 += l_con[i][j] * u_con[i][j]
            t2 += l_con[i][j] * d_con[i][j]
            t2 += r_con[i][j] * u_con[i][j]
            t2 += r_con[i][j] * d_con[i][j]
    for i in range(h):
        u_row = sorted(u_con[i])
        for j in range(w):
            t2 += u_row[j] * (w - j)
    for j in range(w):
        l_col = sorted(l_con[i][j] for i in range(h))
        for i in range(h):
            t2 += l_col[i] * (h - i)
    t3 = 0
    for i in range(h):
        j = 0
        while j < w:
            if grid[i][j] == '.':
                j += 1
                continue
            r = r_con[i][j]
            u_row = sorted(u_con[i][j:j + r])
            d_row = sorted(d_con[i][j:j + r])
            for k in range(r):
                t3 += (u_row[k] + d_row[k]) * (r - k)
            j += r
    for j in range(w):
        i = 0
        while i < h:
            if grid[i][j] == '.':
                i += 1
                continue
            d = d_con[i][j]
            l_col = sorted(l_con[k][j] for k in range(i, i + d))
            r_col = sorted(r_con[k][j] for k in range(i, i + d))
            for k in range(d):
                t3 += (l_col[k] + r_col[k]) * (d - k)
            i += d
    t4 = 0
    for i in range(h):
        valid = [0] * w
        valid_sum = 0
        for j in range(w):
            if grid[i][j] == '#':
                valid[j] = 1
                valid_sum += 1

        for u in range(i, -1, -1):
            if u < i:
                for j in range(w):
                    if valid[j] == 1 and grid[u][j] == '.':
                        valid[j] = 0
                        valid_sum -= 1
            if valid_sum == 0:
                break

            acc = [0] + list(accumulate(valid))
            for j in range(w):
                if valid[j]:
                    max_w = min(l_con[i][j], l_con[u][j])
                    t4 += acc[j + 1] - acc[j - max_w + 1]

    # print(f'{t0=} {t1=} {t2=} {t3=} {t4=}')
    ans = t0 - t1 + t2 - t3 + t4 + 1
    return ans


h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]
ans = solve(h, w, grid)
print(ans)

解法2

前項の $T_4$ を求める解法を少し変えることで、包除原理を使わなくても「4辺のいずれもが”全て黒マス”ではない矩形領域の個数」を直接数えられる。
前項だと $T_2,T_3$ あたりの実装にもそれなりに時間がかかるため、 $T_4$ と似たような解法で直接求められるこの解法の方が（思いつきさえすれば）素早く実装できる。

以下を前計算する。

$R'[i,j]:=(i,j)$ から右に見て、$j$ 列目を含め、初めて白マスが出現する列（存在しなければ $W+1$）

下端となる列 $d$ を固定し、そこから上端となる列 $u$ を上方向に試していく。$u$ 毎に、以下を計算する。

$\mathrm{valid}[k]:=$ 列 $k$ において、$d$ から $u$ までに「白マスが1つでもあれば」$1$、全て黒なら $0$
$\mathrm{acc}[k]:=\mathrm{valid}$ の累積和

その後、左端となる列 $j$ を固定すると、$r=\max(R'[d,j],R'[u,j])$ として、右端とできる列は $[r,W+1)$ の範囲となる。この範囲にある $\mathrm{valid}[k]=1$ の個数が $d,u$ を固定した時の答えとなり、これは $\mathrm{acc}$ から求められる。

G - Has Many Divisors

問題文

$2$ 以上の整数 $N, D$ が与えられます。
$N$ 以下の正整数であって $D$ の倍数でないもののうち、正の約数の個数が最も多いものを求めてください。
ただし、そのような正整数が複数存在する場合には、いずれか $1$ つを出力してください。

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

制約

$1 \leq T \leq 10$
$2 \leq D \leq N \leq 10^{18}$
入力される値はすべて整数

解法

高度合成数の列挙の応用。高度合成数とは、$1,2,3,...$ と自然数の約数の個数を調べていったとき、それまでの最大値を更新するような数のこと。

約数の個数は、素因数分解が $p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3}...$ となるなら $(a_1+1)(a_2+1)(a_3+1)...$ で求められる。
$p_i$ の方は個数に影響しないので、「$D$ の倍数でない」という条件を無視すると、

$p_1=2,p_2=3,p_3=5,...$ と素数を小さい方から当てはめていけばいい
$a_1 \ge a_2 \ge a_3 \ge ...$ としていい

つまり、経路探索的に、以下のように調べていける。

$(x,d,i,c)=$(値, 約数の個数, 最大素因数のindex, 最大素因数の個数) をノードとする。
$x$ の小さい順にキューから取り出す。
$d$ がこれまでの最大値を更新するか確認する。更新するなら答え候補として覚えておく。
以下の2通りをキューに積む。
- (a) $p_{i+1}$ を1つ新たな素因数に加えた値
- (b) $p_{i}$ をもう1つ素因数に加えた値
- 新しい $(x',d',i',c')$ は $(x,d,i,c)$ から計算できる。

ここに「$D$ の倍数でない」という条件を考慮すると、

キューに積む前に、新たな値が $D$ で割り切れるか確認する。
割り切れる場合、
- (a) なら、代わりに $p_{i+2}$ を加えた値をキューに積む。
- (b) なら、キューには積まない。

とすると、$D$ の倍数を回避できる。キューの先頭が $N$ を超えるまで繰り返し、最後に $d$ の最大を更新した $x$ が答えとなる。

ただし、これだと結局、ほぼ $N$ 個全ての数がキューに積まれ、調べ尽くされることになる。

TLEを防ぐため、高度合成数の可能性がなくなったものは枝刈りする必要がある。

適当＆未証明な上限見積もり

以下のサイトをざっと確認すると、$10^{18}$ 以下の高度合成数に、各素因数の指数として現れる最大値は次のようになる。

高度合成数の一覧 | アルゴ式

素因数 p     2   3   5   7  11  13～37
指数最大値   9   5   3   2   2     1

$D$ の制約が無い場合、探索は、使う素因数 $2～37$ の $12$ 個、各指数の上限は上の範囲のみとして行えば十分である。

$D$ の制約がある場合、「$D$ の素因数分解 $\prod p_i^{a_i}$ の少なくとも1つの $p_i$ の指数が $a_i$ に足りてなければいい」ので、その1つを除いては制約がない。

素因数が1つ使えない分は他の素因数に転嫁されることになるが、それで他の特定の素因数の指数が一気に増える、ということは考えづらい。素因数の上限を $41,43$ あたりまで使うとし、上限もそれぞれ $2～3$ 程度増やし、その範囲を探索すると通る。

適当に拡張した上限例
素因数 p     2   3   5   7  11  13  17～43
指数最大値  12   8   6   4   3   2   1

ちゃんとした上限

前述の、制約が無い場合に $10^{18}$ までの高度合成数に現れる素因数 $p_i$ に対する指数上限を $u_i$ とする。 $u=(9,5,3,2,2,1,1,...,1)$（$i=1～12$）

「$D$ がどんな値であろうと、$10^{18}$ までの $D$ 制約下での高度合成数に現れる $p_i$ の指数は $v_i$ を超えない」という $v=(v_1,...,v_n)$ を求めたい。

先述の通り、$D$ の素因数分解 $\prod p_i^{a_i}$ の少なくとも1つの $p_i$ の指数が $a_i$ に足りてなければいい。

この “明示的に足りさせないようにする” 素因数を $q$ に固定したとする。

$q$ の指数の上限は $\min(D$ に含まれる $q$ の個数$, u_i)$ としてよい。 $D$ に $q$ が $u_i$ より多く含まれていても、$u_i$ より多く使った数は高度合成数になり得ない。（そもそも制約が無い状態でも $u_i$ より多くは使われないので）
よって、「$D$ がどんな場合でも」の上限は $u_i$ となる。

$q$ 以外の素因数に付いて考える。$q$ を除いたら、素因数は小さい方から使うことになる。

$r$ を「制約の中で使用される可能性がない、最も小さな素因数」とする。簡単な上限としては、$2 \cdot 3 \cdot 5 \cdot ...$ とかけていって $10^{18}$ を超えない最大が $47$。 1つを $q$ として飛ばしたとすると最大の可能性があるのは次の素数 $53$ となり、よって $r=59$ となる。

次に、$r$ 未満の各素因数 $p$ について、$r$ を超える最小の指数 $k$ を考える。
例えば $p=2$ なら、$2^6=64 \gt 59$ より、$k=6$ である。

高度合成数候補 $x$ が $2^6$ を含んでいた場合、それを $r$ に置き換えた $y$ を考える。

$y=x \cdot r / 2^6 \lt x$
約数の個数は、$x$ の素因数分解の $2$ の指数を $e$ として、
- $2$ が減ることで $(e-6+1)/(e+1)$ 倍
- $r$ が増えることで $2$ 倍

よって、もし $2(e-6+1)/(e+1) \ge 1$ であれば、$x$ より小さい $y$ が $x$ 以上の約数を持つこととなり、 $x$ は $D$ 制約下の高度合成数ではありえないことになる。

ここから、$e \le 10$ という $e$ に関する上限が導ける。これがそのまま、$v_i$ として利用できる。

他の $p$ についても同様に考えていくと、

素因数 p     2   3   5   7  11～53
指数上限    10   6   4   4    2

が導ける。この範囲を探索すればよい。

他にもより良い上限はあると思う。

Python3

from heapq import heappop, heappush


def hcn_heapq(N, d):
    """ d の倍数以外の高度合成数 """
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
    limits = [10, 6, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]

    # 初期状態
    if d == 2:
        q = [(3, 2, 1, 1)]
    else:
        q = [(2, 2, 0, 1)]  # (n, nの約数の個数, 最後に追加した素数のi, その個数)
    prev_n = 1
    prev_val = 1

    def add_new_prime(n, pi):
        if pi >= len(primes):
            return
        if n > N // primes[pi]:
            return
        new_n = n * primes[pi]
        if new_n % d == 0:
            pi += 1
            if pi >= len(primes):
                return
            if n > N // primes[pi]:
                return
            new_n = n * primes[pi]
        heappush(q, (new_n, val * 2, pi, 1))

    while q and q[0][0] <= N:
        n, val, last_i, last_count = heappop(q)

        # 約数の個数を更新するなら答を更新
        if val > prev_val:
            prev_n = n
            prev_val = val

        # 新しい素数で横に伸ばす
        add_new_prime(n, last_i + 1)

        # 最後の約数の個数を増やす
        if last_count < limits[last_i] and n <= N // primes[last_i]:
            new_n = n * primes[last_i]
            if new_n % d != 0:
                new_val = val // (last_count + 1) * (last_count + 2)
                heappush(q, (new_n, new_val, last_i, last_count + 1))

    return prev_n


def solve(queries):
    buf = []
    for n, d in queries:
        result = hcn_heapq(n, d)
        buf.append(result)
    return buf


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

¹⁾

厳密には違うらしいが、まぁだいたい近似できる

目次

AtCoder Beginner Contest 475 E,F,G問題メモ

E - Quiz Competition: Qualifiers

問題文

制約

解法

F - Rectangle Filling

問題文

制約

解法

解法2

G - Has Many Divisors

問題文

制約

解法

適当＆未証明な上限見積もり

ちゃんとした上限