目次
AtCoder Beginner Contest 136 D～F問題メモ
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個らしい。
なので、多くともこれ以下の約数しか調べなくてよい。 それぞれにつき $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)
