−目次

AtCoder Beginner Contest 136 D～F問題メモ

AtCoder Beginner Contest 136 D～F問題メモ

AtCoder Beginner Contest 136

AtCoder Beginner Contest 136 解説放送 - YouTube

久々の全完。6問体制になってから普通にむずい。

D - Gathering Children

問題

横一列の $N$ 個のマス目に'L'か'R'が書かれている
- 各マスにどちらが書かれているかは入力で与えられる
- 1番目のマスには'R'が、 $N$ 番目のマスには'L'が書かれている
はじめ、各マスに1人ずつ人がいる
以下の移動を $10^{100}$ 回繰り返す
- 現在、'L'のマスにいる人は左に、'R'のマスにいる人は右に移動する
終了後、それぞれのマスに何人の人がいるか
$2 \le N \le 10^5$

解法

昔、各マスに矢印が書かれていて「矢印の書いた方向にしか進めません」みたいな迷路があった記憶がある。その迷路では、「→←」みたいなマスがあると、実質行き止まりである。

この問題もそうで、 $10^{100}$ 回も移動すると全ての人は「RL」と連続するマスに集約され、そこを行ったり来たりするだけになる。

マスを、1区分が 'RRR…RRRLLL…LLL' となるように分割する。

RRLLLLRRRLRLRRRLL
↓
RRLLLL  RRRL  RL  RRRLL

人は区分を超えて移動できず、ある区分上にいた人は全て、終了後にはその区分の 'RL' に集約される。他のマスには残れないので0人。

次に考えることは、 $10^{100}$ 回ちょうどの後には、'RL'の2マスのどちらにどれだけの人がいるかである。

これは、 $10^{100}$ が偶数なので、偶数回の移動では、偶数個離れたマスにしか移動できないことを使う。

'RL' の 'R' が、区分の左から奇数番目なら、その区分の中で最初に奇数番目のマスにいた人は'R' に、偶数番目のマスにいた人は'L'に集約されることが分かる。

偶数番目なら逆。

        
          
          
              
              def update(ans, switch, i, prev_i):
    total = i - prev_i
    if (switch - prev_i) % 2 == 0:
        ans[switch - 1] = total // 2
        ans[switch] = total - total // 2
    else:
        ans[switch] = total // 2
        ans[switch - 1] = total - total // 2
 
 
s = input()
switch = -1  # RRR...RL...LLL の、'L'に切り替わったindex
prev_c = 'R'  # すぐ左のマスの文字
prev_i = 0  # 現在の区分の左端のindex
ans = [0] * len(s)
for i, c in enumerate(s):
    if prev_c == 'R' and c == 'L':
        switch = i
        prev_c = 'L'
        continue
    if prev_c == 'L' and c == 'R':
        update(ans, switch, i, prev_i)
        prev_i = i
        prev_c = c
update(ans, switch, len(s), prev_i)
print(*ans)

            

        
      

ダブリング解法

解説pdfにあった解法。

             i   0  1  2  3  4  5  6  7
                 R  R  L  L  L  R  R  L
1回の移動後のi   1  2  3  2  3  6  7  6

最初、 $i$ にいた人が1回の移動後にいるマスは、 $i$ から'R'なら+1、'L'なら-1される。

すると、2回の移動後にいるマスはどうなるか。

例えば $i=0$ の人は、1回目で0→1、2回目で1→2と移動する。

             i   0  1  2  3  4  5  6  7
                ↓↗↓
1回の移動後のi   1  2  3  2  3  6  7  6

1回の移動後にいる $i$ を取得し、再度同じ配列で $i$ の場所を辿れば、それが2回の移動後にいる場所になる。

2回の移動後のi   2  3  2  3  2  7  6  7

すると、今度は2回の移動後の配列に同じ事をすれば、4回の移動後の位置を求めることが出来る。

             i   0  1  2  3  4  5  6  7
                ↓,---'↓
2回の移動後のi   2  3  2  3  2  7  6  7

これを繰り返すと、8回、16回、32回……後の移動後の位置を知ることが出来る。

これで、例えば100回の移動後の位置を知りたいとき、100を2の冪乗の和にすると64+32+4であるので、これらの回数移動後の配列を順に通せば良い。

              i   0  1  2  3  4  5  6  7
                  v
  4回の移動後のi  2  3  2  3  2  7  6  7
                   `----v
 32回の移動後のi  2  3  2  3  2  7  6  7
                        v
 64回の移動後のi  2  3  2  3  2  7  6  7

100回の移動後のi  2  3  2  3  2  7  6  7  (例が短いので2回目以降の配列がみんな同じになっているが)

$10^{100}$ 回の移動は、2乗計算を繰り返すと333回程度でたどり着く。

ただし、今回の場合は正確に $10^{100}$ でなくとも「無限ループに陥った後の偶数回の移動後」ということさえ満たしていればよい。

無限ループには $|S|$ 回移動すれば必ず到達するので、2乗計算を繰り返し、 $|S|$ を超えた時点で打ち切れば、その状態が答えと一致する。

最後に、移動後のindexから「それぞれの数が何個あるか？」を集計したものが答えだが、これはnumpy.bincountが便利。

この解法なら、無限ループに陥る前の状態や、そもそも無限ループに陥らないような移動法則の問題でも、解くことが出来る。

        
              import numpy as np
 
s = input()
n = len(s)
a = np.arange(n) + np.array([1 if c == 'R' else -1 for c in s])
i = 1
while i < n:
    a = a[a]
    i <<= 1
print(*np.bincount(a, minlength=n))

E - Max GCD

問題

$N$ 個の整数 $A_1,A_2,...,A_N$ がある
以下の操作を $K$ 回まで行える。行わなくてもよい。
- 操作: 異なる2数を選び、一方を+1、もう一方を-1する
- 数が負になってもよい
操作後、 $N$ 個の全ての整数の最大公約数を $g$ とすると、上手く操作を行うことで得られる $g$ の最大値を求めよ
$2 \le N \le 500$
$1 \le A_i \le 10^6$

解法

約数列挙+貪欲。

$N$ 個の整数の全体の和を $S$ とすると、 $S$ は操作を行っても変わらない。また、各整数の最大公約数 $g$ は、当然 $S$ の約数でもある。

なので、 $S$ の約数を大きい順に列挙して、可能かどうか順に試していく。 $S$ は最大 $5 \times 10^8$ である。

約数の個数の目安は、高度合成数を調べるとおおよそつけることができる。これは「自分未満に、約数の個数を自分以上持つ数が存在しない」数で、551350800が1200個らしい。

Highly composite numbers list · GitHub

なので、多くともこれ以下の約数しか調べなくてよい。それぞれにつき $O(N)$ とか $O(N \log{N})$ とかで処理できればよい。

決め打ったdでの判定

ある約数 $d$ を決め打ちして、それが $K$ 回以内の操作で可能かどうかを判定したい。

$A_i$ を $d$ の倍数にするには、 $A_i \% d$ を $m$ として、 $m$ 回引くか、 $d-m$ 回足せばよい。（10を7の倍数にするには、10%7=3なので、3回引くか、4回足せばよい）

なるべく少ない回数の方を選びたい気持ちはあるが、全体で「引く回数」と「足す回数」は揃えないといけない。

d = 7
A      10   1   2  22
引く    3   1   2   1
足す    4   6   5   6

いずれの数も引く方が足すより操作回数が少ないが、
数を揃えるためにはどれかを足さないといけない

たとえば10を足すことにすれば、引く数と足す数を同じにできる

引く    3  ①  ②  ①
足す   ④   6   5   6

同じ数に「引く」「足す」操作を両方することは無駄なので、全ての数は「引くのみ」「足すのみ」に分離できる。

よって、引くべき数が小さい順にソートし、（このとき、当然「足すべき数が大きい順」でもある）小さい方から $t$ 個を「引くのみ」、残りを「足すのみ」に分類する。

両者の必要回数合計が同じで、かつ $K$ 以下となれるような $t$ が存在すれば、達成可能となる。累積和を用いればよい。

引く      1   1   2   3
足す      6   6   5   4
引_累積   1   2   4 | 7
足_累積  21  15   9 | 4
                    |  ←ここに境界を引いた時、最小回数4を達成。
                         これがK以下なら答えはd (大きい順に調べているので)

ほんとぉ？

このままでは、以下の証明が曖昧である。

本当に分類は、引く数の小さい順に「引く」グループに加えていっていいの？引く数が小さくても足すグループに使わないと達成不可能になったりしない？
本当にその時に最小回数が達成されるの？

以下で説明できる。ある分類で、引くと足すの合計回数が同じにできたとする。

d=11
引く   1   2   4 |  6   9     1+2+4=7
足す  10   9   7 |  5   2     5+2  =7

この時、「引く」から1つ、「足す」から1つを入れ替えてみる。すると合計回数は再び同じになった。

引く   1   2   9 |  6   4      1+2+9=12
足す  10   9   2 |  5   7      5+7  =12

しかしこれ、そもそも $(足す)=d-(引く)$ なので、「引く方での増分」と「足す方での増分」は必ず同じになる。引く数が $a$ の数字と $b$ の数字（ $a \lt b$ ）を入れ替えると、引く方は $b-a$ 増え、足す方は $(d-a)-(d-b)=b-a$ 増え、同じになる。よって、合計回数が同じ状態は必ず保たれる。

1個ずつの入れ替えで合計が同じ状態が必ず保たれるので、片方から片方へ一方的に移したり、2個と1個など個数の違う入れ替えでは、合計が同じ状態は保たれないこともわかる。

さらに、合計が等しいかどうかを判定する上で重要なのは、結局各分類に属する数字の個数のみであることがわかる。

それなら、引く回数が小さい方から貪欲に引くグループに入れても問題なく、その時に最小回数が達成されることが言える。

        
          
          
              
              from itertools import accumulate
 
 
def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return sorted(ret, reverse=True)
 
 
def solve(n, k, aaa):
    s = sum(aaa)
    div = divisors(s)
    for d in div:
        mods = [a % d for a in aaa]
        mods.sort()
        subs = [0] + list(accumulate(mods))
        adds = [0] + list(accumulate(d - p for p in reversed(mods)))
        adds.reverse()
        for m, a in zip(subs, adds):
            if m == a:
                if m <= k:
                    return d
                break
            if m > a:
                break
 
 
n, k = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, k, aaa))

            

        
      

F - Enclosed Points

問題

「バウンディングボックス」とは、ある点の集合が与えられたときに「全ての点を含む、各辺が軸に平行な最小の長方形」である
2次元平面上に $N$ 個の宝石があり、 $i$ 番目の宝石は $(x_i,y_i)$ （整数）
ここで、宝石の集合の取り方は、 $2^N-1$ 個ある（空集合を除く）
ある集合を $s$ で表し、 $f(s)$ を「 $s$ のバウンディングボックス内部に含まれる宝石の個数」とする
全ての集合に対して $f(s)$ を求め、その総和を、 $\mod{998244353}$ で求めよ
$1 \le N \le 10^5$
$-10^9 \le x_i,y_i \le 10^9$
全ての宝石の $x$ 座標は異なる
全ての宝石の $y$ 座標も異なる

解法

1つの集合を決め打った時、その内部に含まれる宝石の個数を各集合につき考えてもよいが、ちょっと面倒。

視点を変えると、「ある宝石を決め打った時、そいつがカウントされるような集合はいくつあるか？」を、全ての宝石について求めて合計すれば、求める答えと同じである。

自身がカウントされる集合の個数

まず、自分自身が含まれる集合は、必ずそのバウンディングボックス内に自身が含まれる。このような集合は $2^{N-1}$ 通りある。

また、自身が含まれない集合でも、以下の2つはバウンディングボックスに自身が含まれる。

1.「自身の左上のどれか」と「自身の右下のどれか」が共に含まれる集合
2.「自身の左下のどれか」と「自身の右上のどれか」が共に含まれる集合

この個数はどのようにして求めるか。

いま、ある宝石からナナメ4方向にある宝石の個数が分かっているとする。

  b  |  d
-----o-----
  a  |  c

この時、「自身の左下 $a$ 個のどれかが1つは含まれる集合」というのは、空集合でなければよいので、 $2^a-1$ （×a以外の宝石の選び方）となる。

よって、上記1.は $(2^b-1)(2^c-1)2^{a+d}$ で求められる。これを $BC$ とする。

同様に、2.は $(2^a-1)(2^d-1)2^{b+c}$ で求められる。これを $AD$ とする。

しかし、この中には「4方向の全てに、どれか1つが含まれる集合」が重複して数えられているので、それを除く。

$(2^a-1)(2^b-1)(2^c-1)(2^d-1)$ 、これを $ABCD$ とする。

これで、ある宝石について、自身が数え挙げられる集合の個数は、以下で求めることができた。

$2^{N-1}+BC+AD-ABCD$

a,b,c,dの求め方

まず、 $x$ 座標が小さい順にソートすると、その順番から $a+b$ と $c+d$ は分かる。

また、座標の範囲が大きいので、あらかじめ $y$ 座標を圧縮して、小さい順に $1,2,3,...$ と座標を振り直しておく。大小関係さえ保たれていれば、答えは変わらない。

すると、 $y_i$ の値によって $a+c$ と $b+d$ もわかる。

ここで $x$ 座標が小さい方から処理すれば、Binary Indexed Tree 等を使って、 $a$ 、つまり「 $x$ 座標が $x_i$ より小さく、 $y$ 座標が $y_i$ より小さいものの数」は $O(log{N})$ で求めることができる。

すると、残りも以下のように連鎖的に求められる。

$i = a+b$ なので、 $b=i-a$ 。( $i$ は0-indexedとする)

$y_i$ が1からの連番に振り直されているので、 $y_i = a+c+1$ なので、 $c=y_i-a-1$ 。

$N-i-1 = c+d$ より、 $d=n-i-1-c$

これで、 $i$ 番目の宝石の $a～d$ がわかり、答えが求められた。

        
          
          
              
              import sys
 
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
 
MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
bit = Bit(n)
 
p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)
 
ans = 0
for i, (x, y) in enumerate(xys):
    a = bit.sum(y)
    b = i - a
    c = y - a - 1
    d = (n - i - 1) - c
    bit.add(y, 1)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * (pb + pc - 1) % MOD
    tmp += (pb - 1) * (pc - 1) % MOD * pa * pd % MOD
    ans = (ans + tmp) % MOD
print(ans)

            

        
      