目次
AtCoder Beginner Contest 174 C,D,E,F問題メモ
F問題は問題文もシンプルだし、いかにも過去にどこかで出題されてそう。
こういうのは解法を知っているか知らないかに左右される部分はあるが、知らなかったなら次までに覚えておけばよし。
C - Repsept
問題
- $7,77,777,...$ と無限に続く数列の中で、$K$ の倍数が登場するか判定し、登場するなら最初は何番目か答えよ
- $1 \le K \le 10^6$
解法
解法の思いつきにくさはDより上かも知れない。
数列を素因数分解してもパターンが見えてくるわけでも無く、順番に試し割るのが速そう。
だが、$K$ が大きくなると急激に数値が大きくなっていくため、そのままの計算は無理。
割り算の筆算のように、頭の桁からの計算をシミュレートすると、桁数が大きくなっても大丈夫。
____2_6__________
K = 29 ) 7 7 7 7 7 7 ... (無限に供給される7)
_5_8_
1 9 7
_1_7_4_
2 3 7
...
77を29で割った余りは19で、割り切れていない。
筆算では、この'19'に次の桁の'7'を下ろして197とする。
プログラム的には $19 \times 10 + 7$ となる。
続いて197を29で割ると23余り、まだ割り切れてないので237として……と繰り返す。
割り切れたらその時点での 777… の桁数が最初に割り切れる要素となる。1桁の'7'から数えて何回割ったかを数えておけばよい。
永遠に割り切れないこともあるのが厄介だが、処理の性質上、余りが過去に出てきたのと被ったら、そこからは全く同じ展開がループするので割り切れないと分かる。 たとえば上記なら $7,19,23,...$ などが再度余りとして出てきたら、ループすることになる。
$K$ で割った余りの取りうる値は、$0～K-1$ しかない。
せいぜい $K$ 回まで調べれば、必ず、ループするか割り切れるかのどちらかには行き着く。
ところで、1をずらっと並べた数を、レピュニット という（rep-unit）。 今回は7（septem）を並べているので rep-sept。
def solve(k):
x = 7
checked = set()
ans = 1
while True:
x %= k
if x == 0:
return ans
if x in checked:
return -1
checked.add(x)
x = x * 10 + 7
ans += 1
k = int(input())
print(solve(k))
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 仮に、この目標状態にするのに必要な操作数を調べる
|--2--|----3----| それぞれの陣営で初期状態と異なる個数
ここでR陣営とW陣営から、初期状態と目標状態が異なる文字を1つずつ選んで交換すると、必ず互いに目標状態と一致する。
目標状態 R R R|W W W W W
初期状態 W R W|W R W R R
~ | ~
R R W|W R W W R
つまり、初期状態と目標状態が異なる（＝何らかの操作をしなければならない）要素が $2+3$ 個あって、
- 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 仮にそこに境界を置いたときに、境界より左の'W'の個数
4 4 3 3 3 2 2 1 0 仮にそこに境界を置いたときに、境界より右の'R'の個数
-------------------
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))))
もっと単純に、「常に最も左にある'W'と最も右にある'R'を入れ替える操作のみを行い、書き換えは行わない」でも最小を達成できるみたい。たしかに。
この場合は '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$ として切る回数を少なく抑えようと思えば、なるべく1本ずつを長く、つまり $L$ ごとに切ればよい。
ちょうど割り切れる境界あたりが混乱しやすいので詳しく見ていくと、
L = 3 Ai 1 2 3 4 5 6 7 8 9 10 ... 切る回数 0 0 0 1 1 1 2 2 2 3 ...
なので、$\dfrac{(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)
仮に長さが実数も取り得るなら、演算誤差が生じるので難しくなる。 二分探索は2でしか割らないので、1回ごとに全体を2倍していって、整数比較できる状態を保つとよいかな。
それとも、入力が整数なら必ず2の冪乗分の○○と表現できる数になるので、意外とそのまま計算しても大丈夫だったりする？
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$
解法1
コンテスト中に上記の記事とかのアクセス数が謎の伸びを示してそう。
セグメント木は無理そう
区間クエリというとセグメント木を使った解法が多いが、今回の場合は無理そうというのはわかる。
たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる具体的な要素が分からないと答えが求められない。
bitフラグなんかで集合を管理すれば可能だが、それには1回の操作に $O(N)$ の計算量がかかるので、間に合わない。
$C_i$ の種類毎に出現個数の累積和を作れば任意区間にある同じ数字の個数が分かるが、1回のクエリごとに全ての $C_i$ についてチェックしなければならず $O(N)$ の計算がかかり、やはり無理。
「同じ数字を含むこと」の区間への言い換え
要は上記記事の解法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] 最も近い2同士
[1 3] 最も近い5同士
[4 9] 最も近い2同士
[6 8] 最も近い7同士
クエリ区間
[1 5] → [1 3] が含まれる = かぶる数字は1個
[0 8] → [0 4][1 3][6 8] が含まれる = かぶる数字は3個
上図のように、「クエリ区間に同じ数字が2つ入ってしまう」というのは、「クエリ区間に対象区間が完全に含まれる」と言い換えられる。
同じ数字が3つなら2個、4つなら3個の対象区間が含まれることになる。
つまり、「クエリ区間に完全に含まれる対象区間の個数」＝「重複する数字の個数」なので、クエリ区間の長さから重複数を引いたものが種類数となる。
これを求めるには、区間を $[L_i,R_i]$ と表現するとして、対象区間もクエリ区間もまとめて $R_i$ を基準にソートする。
ソートした区間を順番に処理する。$R_i$ が同じものは対象区間を優先的に処理する。
状態管理に、長さ $N$ の配列 $T$ を用意しておく。
- 対象区間の場合
- $T[L_i]$ に、1加算する
- クエリ区間の場合
- $T[L_i]～T[R_i]$ の合計値が求める値となる
区間和なので、$T$ はFenwick Treeなどで実装すればよい。
計算量は、対象区間が $O(N)$ 生成され、$Q$ 個のクエリ区間と一緒にソートする部分が最もかかり、$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)))
解法2
より計算量の少ない解説pdfの方法。
右端が $R_i$ のクエリを処理する段階では、「$R_i$ までに登場する中で、各要素が最後に登場した箇所のみ1、他は0の配列 $T$」があれば、
そのクエリの答えは $T[L_i]～T[R_i]$ の和で求められる。
$T$ は解法1と同様Fenwick Treeなどで実装すればよい。
Ri 未反映
i 0 1 2 3 4 5 6 (7 8 9)
Ci 2 5 6 5 2 5 7 (9 7 2)
Ti 0 0 1 0 1 1 1 (0 0 0)
後で気付いたが、$T$ は解法1で作るやつの0-1を反転させたものだ。解法1は、不要になったものに1を立てていくという操作をしていた。
さて、$T$ をどうやって管理するか。毎クエリ、ゼロから作るわけにもいかないので、順次更新する方法を考える。
クエリ $[L_i, R_i]$ を $R$ 順にソートしておき、その順に処理することにする。
$T$ の他、以下の情報を管理しておく。
- 現在、要素 $c$ が最後に登場した $i$ の位置 $last[c] = i$
c 1 2 3 4 5 6 7 8 9 last[c] - 4 - - 5 2 6 - -
$R=6$ のクエリの次に、$R=8$ のクエリが来たとする。
現在、$T$ には $i=6$ までの状態を反映しているのを、$i=7,8$ について更新する。
i 0 1 2 3 4 5 6 7 8 Ci 2 5 6 5 2 5 7 9 7 Ti 0 0 1 0 1 1 1 0 0 （R=6 まで）
$C_7=9$ は、過去にまだ登場したことがないので $T[7]=1$ とするのみ。$last[9]=7$ としておく。
Ti 0 0 1 0 1 1 1 [1] 0 （R=7 まで）
$C_8=7$ は $last[7]$ を参照すると既に $i=6$ で出てきている。この場合は新たに右端となる位置が変わるので $T[6]=0$、$T[8]=1$ とする。
また、$last[7]=8$ に更新しておく。
Ti 0 0 1 0 1 1 [0] 1 [1] （R=8 まで）
これで状態の更新ができたので、$R=8$ であるクエリはこの $T$ を元に $T[L_i]～T[R_i]$ を合計すればよい。
解法1はPyPyでも間に合わなかったが、こちらならソートするのがクエリだけで済むため計算量は $O(N+Q(\log{N}+\log{Q}))$ で、PyPyでも間に合う。
本質的ではないが、解法1でも2でも $(R_i,L_i,i)$ などのタプルのソートが必要となるが、これをビットシフトして1つの整数にまとめてソートさせると、その部分は数倍高速化される。
import sys
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, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
itr = zip(mp, mp)
rli = [0] * q
for i in range(q):
l, r = next(itr)
rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0
for j in range(q):
k = rli[j]
r = k >> 40
l = (k >> 20) & mask
i = k & mask
while p < r:
c = ccc[p]
before_appeared = appeared[c]
if before_appeared != -1:
bit_add(bit, bn, before_appeared + 2, -1)
bit_add(bit, bn, p + 2, 1)
appeared[c] = p
p += 1
ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))
