目次
文書の過去の版を表示しています。
AtCoder Beginner Contest 174 D,E,F問題メモ
F問題は問題文もシンプルだし、いかにも過去にどこかで出題されてそう。
こういうのは解法を知っているか知らないかに左右される部分はあるが、知らなかったなら次までに覚えておけばよし。
D - Alter Altar
問題
'R' と'W' からなる長さ $N$ の文字列が与えられる- 以下の2つの操作をいずれでも何回でも繰り返して、「
'R' の左隣に'W' が存在しない」状態にしたい - 操作
- 好きな2つの文字を入れ替える（隣接していなくともよい）
- 好きな1つの文字を書き換える（
'R' なら'W' に、'W' なら'R' に）
- 必要な最小操作数を求めよ
- $2 \le N \le 2 \times 10^5$
解法
'R' の左隣に 'W' が存在しないというのは、RRRR…RRWWWW…WW という状態になっているということ。
'R' と 'W' の境界はどこか？ を $0～N$ で全探索するとよい。
初期状態 W R W W R W R R
R R R W W W W W 仮に'R'が3文字続く状態の答えを調べる
|--2--|----3----| それぞれの陣営で矛盾している個数
ここで左陣営と右陣営から矛盾している文字を1つずつ選んで交換すると、必ず互いに解消される。
- 2つの文字を入れ替える操作をおこなうと、合計2解消される
- 1つの文字を書き換える操作を行うと、1だけ解消される
なので、できるだけ2文字の入れ替えをおこない、余った分は1文字の書き換えを行うのがよい。
この時の合計操作回数は、両陣営で変更が必要な個数の大きい方となる。つまりこの例では3回となる。
境界を1つずつずらしながら答えを効率的に求めるには、以下の2つを計算する。
- 左から、
'W' が出現した累積回数 - 右から、
'R' が出現した累積回数
ある境界で陣営を区切ると、それより左の'W'の個数と右の'R'の個数がわかるので、そのMAXをとればよい。
答えは、全境界を試した中での最小値となる。
初期状態 W R W W R W R R
0 1 1 2 3 3 4 4 4
4 4 3 3 3 2 2 1 0
-------------------
MAX 4 4 3 3 3 3 4 4 4 → このMINが答え
from itertools import accumulate
n = int(input())
s = input()
left_w = [0]
for c in s:
if c == 'W':
left_w.append(1)
else:
left_w.append(0)
left_w = list(accumulate(left_w))
right_r = [0]
for c in s[::-1]:
if c == 'R':
right_r.append(1)
else:
right_r.append(0)
right_r = list(accumulate(right_r))
right_r.reverse()
print(min(map(max, zip(left_w, right_r))))
E - Logs
問題
- 丸太が $N$ 本、長さはそれぞれ $A_1,A_2,...,A_N$
- 合計 $K$ 回まで切って、最長の丸太の長さを最短にしたい
- 実現できる長さが $L$ のとき、$L$ の小数点以下を切り上げた値を求めよ
- $1 \le N \le 2 \times 10^5$
- $0 \le K \le 10^9$
- $1 \le A_i \le 10^9$
解法
- 答えを決め打てば必要な切断回数は簡単に求まる
- 長さ $L$ が実現可能なら、$L$ 以上の長さは必ず実現可能
ので、二分探索の出番。
答えの言い方がまどろっこしいが、要は「$L-1$ が実現不可能で、$L$ が実現可能な整数値 $L$」を求めればよい。
なので、調べる $L$ は整数のみでよい。
仮に最長の長さを $L=3$ にしようと思えば、必要な切る回数は
Ai 1 2 3 4 5 6 7 8 9 10 ... 回数 0 0 0 1 1 1 2 2 2 3 ...
なので、$(A_i-1)//L$ を計算すればよいと分かる。
import sys
n, k, *aaa = map(int, sys.stdin.buffer.read().split())
l = 0
r = max(aaa)
while l + 1 < r:
m = (l + r) // 2
if sum((a - 1) // m for a in aaa) > k:
l = m
else:
r = m
print(r)
F - Range Set Query
問題
- 長さ $N$ の数列 $C_1,C_2,...,C_N$
- $Q$ 回のクエリに答えよ
- クエリ
- $C_{L_i}～C_{R_i}$ にある数字の種類数を求めよ
- $1 \le N,Q \le 5 \times 10^5$
解法
コンテスト中に上記の記事とかのアクセス数が謎の伸びを示してそう。
セグメント木は無理そう
区間クエリというとセグメント木を使った解法が多いが、今回の場合は無理そうというのはわかる。
たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる要素が分からないと答えが求められない。
bitフラグなんかで集合を管理すれば可能だが、それには1回の操作に $O(N)$ の計算量がかかるので、間に合わない。
$C_i$ の種類毎にセグメント木を作れば一定区間にある同じ数字の個数が分かるので答えが求まるが、それも1回のクエリに $O(N \log{N})$ の計算がかかる。
複数個ある数字のみセグメント木を作る？ しかし全ての数字が2個ずつある場合などにTLEするのは変わらない。
$C_i$ の区間への言い換え
要は上記記事の解法3なのだが。
「$C_i$ の、もっとも近い同じ数字同士を1対象区間とする」と、「クエリ区間に完全に含まれる対象区間の個数」が、被る数字の個数となる。
i 0 1 2 3 4 5 6 7 8 9
Ci 2 5 6 5 2 1 7 9 7 2
対象区間
[0 4]
[1 3]
[4 9]
[6 8]
クエリ区間
[1 5] → [1 3] が含まれる = かぶる数字は1個
[0 8] → [0 4][1 3][6 8] が含まれる = かぶる数字は3個
これを求めるには、対象区間もクエリ区間もまとめて（区間を $[L_i,R_i]$ と表現して） $R_i$ を基準にソートする。
ソートした区間を順番に処理する。ただし $R_i$ が同じものは対象区間を優先的に処理する。
状態管理に、長さ $N$ の配列 $T$ を用意しておく。
- 対象区間の場合
- $T[L_i]$ に、1加算する
- クエリ区間の場合
- $T$ の $L_i～R_i$ の合計値が求める値となる
区間和なので、$T$ はFenwick Treeなどで実装すればよい。
計算量は、対象区間が $O(N)$ 生成され、クエリ区間と合わせてソートする部分が最もかかり、$O((N+Q) \log{(N+Q)})$ となる。
わりと制約がでかくて、最大値の代入で $2 \times 10^7$ くらいになるため、PythonではNumbaを使った。
import os
import sys
import numpy as np
def solve(inp):
def bit_add(arr, n, i, x):
while i <= n:
arr[i] += x
i += i & -i
def bit_sum(arr, i):
result = 0
while i > 0:
result += arr[i]
i ^= i & -i
return result
n = inp[0]
q = inp[1]
ccc = inp[2:2 + n]
lll = inp[2 + n::2] - 1
rrr = inp[3 + n::2] - 1
just_left = {}
segments = []
for i in range(n):
c = ccc[i]
if c in just_left:
segments.append((i, 0, just_left[c], 0))
just_left[c] = i
for i in range(q):
segments.append((rrr[i], 1, lll[i], i))
segments.sort()
bit = np.zeros(n + 2, dtype=np.int64)
ans = np.zeros(q, dtype=np.int64)
for r, tp, l, i in segments:
if tp == 0:
bit_add(bit, n + 2, l + 2, 1)
else:
base = r - l + 1
ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
return ans
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', '(i8[:],)')(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit('(i8[:],)', cache=True)(solve)
print('compiled', file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
