コンテンツにスキップ

ブログ

DOJ Beginner Contest 11 C - Farewell

整数列 A1,A2,…,ANA_1, A_2, \dots, A_N があります。要素を 1 つ選んで削除すると、その左にあった要素はすべて 11 増え、右にあった要素はすべて 11 減ります。

要素が 1 つになるまで削除を繰り返したとき、最後に残る値の最大値を求める問題です。値は負になってもかまいません。

最後に残す要素を AiA_i と決めます(1-indexed)。

AiA_i より左の要素を削除すると、AiA_i は削除した要素の右にあるので 11 減ります。AiA_i より右の要素を削除すると 11 増えます。左には i−1i - 1 個、右には N−iN - i 個の要素があり、どれもいつかは削除されるので、削除の順番によらず最後の値は

Ai−(i−1)+(N−i)A_i - (i - 1) + (N - i)

です。これを ii について最大化すれば答えです。O(N)O(N) で求まります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = -float("inf")
for i in range(N):
ans = max(ans, A[i] - i + N - i - 1)
print(ans)

コードでは 0-indexed なので、左に ii 個、右に N−i−1N - i - 1 個の要素があります。

DOJ Beginner Contest 11 B - Even Roasting

一列に並んだ NN 枚の肉があり、焼き加減はすべて 00 です。1 回の操作では、左か右の端を選び、火力 PP(1≤P≤1091 \le P \le 10^9)を決めます。選んだ側から dd 番目の肉の焼き加減が max⁡(0,P−d+1)\max(0, P - d + 1) 増えます。

すべての肉の焼き加減を同じ正の整数にするための最小の操作回数と、その操作を出力する問題です。

左から火力 11 で 1 回焼けば、焼き加減が 11 になります。答えは 11 回です。

1 回の操作では足りません。端から 1 番目の肉は PP、2 番目の肉は P−1P - 1 増えるので、この 2 枚の焼き加減が必ず異なります。

2 回なら作れます。左から火力 NN で焼くと、焼き加減は左から N,N−1,…,1N, N - 1, \dots, 1 増えます。右から火力 NN で焼くと、左から 1,2,…,N1, 2, \dots, N 増えます。合わせると、どの肉も N+1N + 1 になります。

Python
for _ in range(int(input())):
N = int(input())
if N == 1:
print(1)
print(1, 1)
else:
print(2)
print(1, N)
print(2, N)

DOJ Beginner Contest 11 A - 7 x 13 = 28

1 桁の正の整数 AA と正の整数 BB が与えられます。BB の 10 進表記の各桁に AA を掛けて、その結果をすべて足した値を求める問題です。

たとえば A=7,B=13A = 7, B = 13 なら 7×3+7×1=287 \times 3 + 7 \times 1 = 28 です。1≤B≤9991 \le B \le 999 です。

各桁に AA を掛けてから足すのは、桁和に AA を掛けるのと同じです。答えは A×(B の桁和)A \times (B \text{ の桁和}) です。

桁和は、BB を文字列にして 1 文字ずつ整数に戻して足せば求まります。

Python
for _ in range(int(input())):
A, B = map(int, input().split())
print(A * sum(map(int, str(B))))

DOJ Beginner Contest 6 E - Building a Binary Grid

長さ NN の 01 文字列が QQ 個与えられます。N×NN \times N の 01 のグリッドを 1 つ作り、どの文字列も、グリッド上の長さ NN の経路(上下左右に隣り合う相異なるマスの列)に沿って読めるようにする問題です。グリッドと、各文字列に対応する経路を 1 つずつ出力します。

2≤N≤1002 \le N \le 100 で、NQNQ の総和は 10610^6 以下です。

ii 行目(0-indexed)をすべて i mod 2i \bmod 2 にします。つまり、00 だけの行と 11 だけの行が交互に並びます。さらに、右下の角だけを 11 にします。

0000
1111
0000
1111

(N=4N = 4 の例。NN が偶数なら最下行はもともと 11 です。)

このグリッドでは、角以外のマスについて次のことがいえます。

  • 右か左に動くと、同じ行なので値は変わりません。
  • 上か下に動くと、行が変わるので値が反転します。

左上 (0,0)(0, 0) から始めます。ここは 00 です。次の文字が今のマスと同じ値なら右に、違う値なら下に動きます。

右か下にしか動かないので、同じマスを 2 回通ることはありません。N−1N - 1 回動いたあとも、行と列の番号の和は N−1N - 1 なので、グリッドからはみ出しません。また、右下の角(番号の和が 2N−2>N−12N - 2 > N - 1)には届かないので、角だけ値を変えたことの影響も受けません。

右下の角 (N−1,N−1)(N - 1, N - 1) から始めます。ここは 11 です。次の文字に合わせて、左か上に動きます。

角から左のマスと上のマスは、行が違うので値が異なり、どちらかは次の文字と一致します。そこから先は、0 で始まる場合と同じように「同じ値なら左、違う値なら上」と動けば、どの文字列も読めます。左か上にしか動かないので、角に戻ることもありません。

1 つの文字列の経路は O(N)O(N) で求まるので、全体で O(NQ)O(NQ) です。

Python
for _ in range(int(input())):
N, Q = map(int, input().split())
grid = []
for i in range(N):
grid.append([i % 2] * N)
grid[-1][-1] = 1
for i in range(N):
print(*grid[i], sep="")
for _ in range(Q):
S = input()
if S[0] == "0":
i, j = 0, 0
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j + 1] == int(S[k]):
j += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i, j = N - 1, N - 1
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j - 1] == int(S[k]):
j -= 1
ans.append(i + 1)
ans.append(j + 1)
else:
i -= 1
ans.append(i + 1)
ans.append(j + 1)
print(*ans)

隣のマス(右または左)の値が次の文字と一致すれば横に、一致しなければ縦に動いています。縦に動いた先は、横のマスと値が逆なので、必ず次の文字と一致します。

DOJ Beginner Contest 6 C - Dadas Is Short

NN 人が左から一列に並んでいて、ii 番目の人の身長は HiH_i です。ダダスは 11 番目の人です。

ダダスを含む連続した区間 [L,R][L, R] のうち、区間内でダダスの身長がほかの全員より真に高いものの個数を求める問題です。NN の総和は 3×1053 \times 10^5 以下です。

ダダスは 11 番目なので、区間は必ず L=1L = 1 です。数えるのは、H2,…,HRH_2, \dots, H_R がすべて H1H_1 より小さくなるような RR の個数です。

左から見ていき、Hi≥H1H_i \ge H_1 となる最初の ii を探します。条件を満たす RR は 1,2,…,i−11, 2, \dots, i - 1 の i−1i - 1 個です。そのような ii がなければ、R=1,…,NR = 1, \dots, N のすべてが条件を満たすので、答えは NN です。

Python
for _ in range(int(input())):
N = int(input())
H = list(map(int, input().split()))
for i in range(1, N):
if H[i] >= H[0]:
print(i)
break
else:
print(N)

コードは 0-indexed なので、H[i] >= H[0] となる最初の i がそのまま答えの i−1i - 1 にあたります。for 文の else は、break せずにループを終えたときに実行されます。

DOJ Beginner Contest 6 A - Dadas-style Acronyms

英字と空白からなる文 SS が与えられます。SS を空白で単語に分け、各単語の最初の文字を順につなげた略語を出力する問題です。大文字と小文字は変えません。

単語の間には空白がちょうど 1 つあり、文の最初と最後には空白がありません。

SS を空白で区切り、各単語の先頭の文字を取り出してつなげます。

Python では input().split() で単語のリストが得られるので、各単語の x[0] を "".join でつなげれば答えになります。

Python
for _ in range(int(input())):
print("".join(map(lambda x: x[0], input().split())))

DOJ Beginner Contest 7 B - tourist vs rainboy

NN 問の問題が難しさの昇順に並んでいて、ii 番目の問題を解くには時間 AiA_i がかかります(A1≤A2≤⋯≤ANA_1 \le A_2 \le \dots \le A_N)。

tourist と rainboy は時刻 00 に解き始め、休まずに 1 問ずつ解いていきます。各問題を解き終えた時刻の和がペナルティです。tourist は 1,2,…,N1, 2, \dots, N 番の順に、rainboy は N,N−1,…,1N, N - 1, \dots, 1 番の順に解きます。rainboy のペナルティから tourist のペナルティを引いた値を求める問題です。

解く順に AA を並べたとき、kk 問目を解き終える時刻は、最初の kk 問にかかる時間の和(累積和)です。ペナルティはその累積和を全部足したものです。

  • tourist のペナルティは、AA を前から足していったときの累積和の合計です。
  • rainboy のペナルティは、AA を後ろから足していったときの累積和の合計です。

それぞれを O(N)O(N) で計算し、差をとります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 0
x = 0
for a in A:
x += a
ans -= x
x = 0
for a in reversed(A):
x += a
ans += x
print(ans)

x が今の累積和(解き終えた時刻)です。前から足すときは ans から引き、後ろから足すときは ans に加えることで、差を直接求めています。

DOJ Beginner Contest 7 A - 49

国語を含む NN 個の試験を受けます。どの試験も満点は 100100 点ですが、国語だけは 4949 点を超えられません。合計点の最大値を求める問題です。

国語以外の N−1N - 1 個の試験で 100100 点、国語で 4949 点をとるのが最大です。答えは

100(N−1)+49=100N−51100(N - 1) + 49 = 100N - 51

です。

Python
for _ in range(int(input())):
N = int(input())
print(N * 100 - 51)

DOJ Beginner Contest 8 G - Nostalgia

N×NN \times N のマスに、11 から N2N^2 までの整数を 1 つずつ書き込みます(マス (i,j)(i, j) の値を Hi,jH_{i,j} とします)。各列の最大値の和を S1S_1、各行の最大値の和を S2S_2 とします。

整数 XX が与えられるので、S1−S2=XS_1 - S_2 = X となる書き込み方を 1 つ出力する問題です。存在しなければ −1-1 を出力します。N2N^2 の総和は 10510^5 以下です。

X≥0X \ge 0 の場合を考えます。X<0X < 0 の場合は、−X-X の答えを転置すれば行と列が入れ替わり、S1S_1 と S2S_2 が入れ替わるので求まります。

F=N(N−1)22F = \dfrac{N (N - 1)^2}{2} とすると、S1−S2≤FS_1 - S_2 \le F です。

  • S2S_2 の下限:行の最大値を小さい順に r1<r2<⋯<rNr_1 < r_2 < \dots < r_N とします。最大値が小さいほうから kk 行には、rkr_k 以下の相異なる数が kNkN 個あるので、rk≥kNr_k \ge kN です。よって S2≥N(1+2+⋯+N)S_2 \ge N(1 + 2 + \dots + N) です。
  • S1S_1 の上限:列の最大値は相異なるので、S1S_1 は大きいほうから NN 個の数の和 N2+(N2−1)+⋯+(N2−N+1)N^2 + (N^2 - 1) + \dots + (N^2 - N + 1) 以下です。

この 2 つの差を計算すると FF になります。したがって、∣X∣>F|X| > F なら −1-1 です。

対角線のマスの値を l1<l2<⋯<lN=N2l_1 < l_2 < \dots < l_N = N^2 とし、li≥iNl_i \ge iN を満たすように決めます。残りの数は、小さい順に、対角線以外のマスへ行ごとに左から書き込みます。最後に、最下行の対角線以外の N−1N - 1 マスだけ、左右の順を逆にします。

このとき、次のことがいえます。

  • 行の最大値は lil_i:ii 行目の対角線以外のマスには、残りの数のうち小さいほうから (i−1)(N−1)+1(i - 1)(N - 1) + 1 番目から i(N−1)i(N - 1) 番目が入ります。lil_i より小さい残りの数は li−1−(i−1)≥i(N−1)l_i - 1 - (i - 1) \ge i(N - 1) 個あるので、これらはすべて lil_i より小さいです。よって S2=l1+⋯+lNS_2 = l_1 + \dots + l_N です。
  • 列の最大値は大きいほうから NN 個の数:最下行の対角線以外のマスには、残りの数のうち大きいほうから N−1N - 1 個が入ります。左右を逆にしたので、大きいものほど左の列に入ります。大きいほうから NN 個の数のうち、対角線にあるものは lN,lN−1,…l_N, l_{N-1}, \dots と右下からつながっていて、その列の最大値になります。残りは最下行の左側の列に入り、どれもその列の最大値になります。よって S1S_1 は常に上限の値になります。

したがって S1−S2=(大きいほうから N 個の和)−(l1+⋯+lN)S_1 - S_2 = (\text{大きいほうから } N \text{ 個の和}) - (l_1 + \dots + l_N) です。

li=iNl_i = iN とすると、S2S_2 が下限になるので差は FF です。そこから lil_i を増やすと、増やした分だけ差が減ります。lN−1,lN−2,…l_{N-1}, l_{N-2}, \dots の順に、li+1−1l_{i+1} - 1 を超えない範囲で必要な分だけ増やしていきます。全部を限界まで増やすと、対角線が大きいほうから NN 個の数になって差は 00 になります。そのため、00 以上 FF 以下のどの XX でも作れます。

Python
from itertools import product, combinations
for _ in range(int(input())):
N, X = map(int, input().split())
t = abs(X)
f = N * (N - 1) // 2 * (N - 1)
if t > f:
print(-1)
continue
f -= t
l = [i * N for i in range(1, N + 1)]
for i in reversed(range(N - 1)):
if f == 0:
continue
p = min(f, l[i + 1] - l[i] - 1)
l[i] += p
f -= p
s = set(range(1, N * N + 1))
ans = [[-1] * N for i in range(N)]
for i in range(N):
s.remove(l[i])
ans[i][i] = l[i]
s = sorted(s, reverse=True)
for i, j in product(range(N), repeat=2):
if ans[i][j] != -1:
continue
ans[i][j] = s.pop()
ans[-1][:-1] = reversed(ans[-1][:-1])
if X < 0:
for i, j in combinations(range(N), r=2):
ans[i][j], ans[j][i] = ans[j][i], ans[i][j]
for a in ans:
print(*a)

コードは 0-indexed です。f は、差を FF から XX に減らすために対角線の値を増やす量の残りです。ans[-1][:-1] = reversed(ans[-1][:-1]) で最下行を左右逆にしています。

DOJ Beginner Contest 8 E - Swap Two Elements

長さ NN の順列 AA が与えられます。次の操作を何回でも行えます。

  • 1≤i<j≤N1 \le i < j \le N を選ぶ。Ai,Ai+1,…,AjA_i, A_{i+1}, \dots, A_j のうち最小の要素と 2 番目に小さい要素の位置を入れ替える。

AA を昇順にするための操作回数の最小値と、その回数を達成する操作の列を 1 つ出力する問題です。NN の総和は 10001000 以下です。

答えは AA の転倒数(位置が前なのに値が大きい組 (p,q)(p, q) の個数)です。

1 回の操作で転倒数は 1 しか変わらない

Section titled “1 回の操作で転倒数は 1 しか変わらない”

区間 [i,j][i, j] で入れ替える 2 つの値を x<yx < y、その位置を p<qp < q とします。

  • 区間内の pp と qq の間にある要素は、どれも xx と yy より大きいです(x,yx, y が区間で最も小さい 2 つだからです)。pp と qq の間にある要素から見ると、xx と yy はどちらも自分より小さいままです。そのため、この要素が関わる転倒の数は、入れ替えても変わりません。
  • pp より前、qq より後ろの要素から見ても、xx と yy の両方が同じ側にあることは変わらないので、転倒の数は変わりません。

変わるのは xx と yy の組だけで、転倒数はちょうど 11 増えるか 11 減ります。昇順の順列の転倒数は 00 なので、操作は転倒数の回数以上必要です。

隣どうしの入れ替えで達成できる

Section titled “隣どうしの入れ替えで達成できる”

j=i+1j = i + 1 とすると、区間は Ai,Ai+1A_i, A_{i+1} の 2 つだけなので、この操作は隣どうしの入れ替えです。バブルソートのように、Ai>Ai+1A_i > A_{i+1} となっている隣の組を入れ替えるたびに、転倒数は 11 ずつ減ります。したがって、ちょうど転倒数の回数で昇順にできます。

NN の総和が 10001000 以下なので、O(N2)O(N^2) のバブルソートで十分間に合います。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for _ in range(N):
for i in range(1, N):
if A[i - 1] > A[i]:
ans.append((i - 1, i))
A[i - 1], A[i] = A[i], A[i - 1]
print(len(ans))
for x, y in ans:
print(x + 1, y + 1)

バブルソートを行い、入れ替えた隣の組 (i,i+1)(i, i+1) を記録して出力しています。

DOJ Beginner Contest 8 D - Region of Twos

00 と 11 からなる長さ NN の数列 AA と、長さ MM の数列 BB が与えられます。NN 行 MM 列の配列 CC を Ci,j=Ai+BjC_{i,j} = A_i + B_j で定めます。値が 22 のマスだけを考え、辺を共有するマスどうしをつないだときの連結成分のうち、最大のものの面積を求める問題です。値が 22 のマスがなければ 00 を出力します。

N,M≤2×105N, M \le 2 \times 10^5 なので、CC を実際に作ることはできません。

Ci,j=2C_{i,j} = 2 となるのは、Ai=1A_i = 1 かつ Bj=1B_j = 1 のときだけです。

AA で 11 が連続している区間を行の区間、BB で 11 が連続している区間を列の区間として、その組み合わせごとに長方形ができます。

  • 長方形の中のマスはすべて値が 22 で、つながっています。
  • 隣の長方形との間には、Ai=0A_i = 0 の行か Bj=0B_j = 0 の列があるので、別の長方形とはつながりません。

したがって、連結成分はこの長方形そのものです。最大の面積は、AA で 11 が連続する最大の長さと、BB で 11 が連続する最大の長さの積になります。値が 22 のマスがない場合も、どちらかが 00 になるので、積は 00 で正しく求まります。

Python
for _ in range(int(input())):
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
x = 0
t = 0
for a in A:
if a:
t += 1
else:
t = 0
x = max(x, t)
y = 0
t = 0
for a in B:
if a:
t += 1
else:
t = 0
y = max(y, t)
print(x * y)

x が AA の、y が BB の、11 が連続する最大の長さです。t は今見ている位置で終わる 11 の連続の長さです。

DOJ Beginner Contest 8 C - Mochi

NN 個の餅があり、ii 番目の餅の大きさは AiA_i です。まだ使っていない餅を 2 個選んで 1 組にできますが、上に置く餅は下に置く餅より真に大きくなければなりません。作れる組の最大数を求める問題です。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

AA を小さい順に並べ替えておきます。

kk 組作れるなら、小さいほうから kk 個を下に、大きいほうから kk 個を上に、それぞれ小さい順に組にしても作れます。つまり、すべての ii (1≤i≤k1 \le i \le k) で Ai<AN−k+iA_i < A_{N - k + i} が成り立つかを調べれば判定できます。

理由を説明します。kk 組作れたとして、下の餅を小さい順に b1≤⋯≤bkb_1 \le \dots \le b_k、上の餅を小さい順に t1≤⋯≤tkt_1 \le \dots \le t_k とします。

  • 下の餅のうち大きいほうから k−i+1k - i + 1 個は、どれも bib_i 以上です。その上の餅は、それより真に大きいので bib_i より大きくなります。よって、bib_i より大きい上の餅は k−i+1k - i + 1 個以上あり、ti>bit_i > b_i です。
  • 小さいほうから ii 番目の AiA_i は bib_i 以下、大きいほうから数えた AN−k+iA_{N - k + i} は tit_i 以上です。

まとめると Ai≤bi<ti≤AN−k+iA_i \le b_i < t_i \le A_{N - k + i} が成り立ちます。

kk 組作れるなら、そこから 1 組外せば k−1k - 1 組も作れます。そのため、作れる最大の kk を二分探索で求められます。kk は ⌊N/2⌋\lfloor N / 2 \rfloor 以下です。

計算量は、並べ替えと二分探索で O(Nlog⁡N)O(N \log N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = (N + 2) // 2
while ok + 1 < ng:
mid = (ok + ng) // 2
if all(A[i] < A[N - mid + i] for i in range(mid)):
ok = mid
else:
ng = mid
print(ok)

二分探索では、ok 組は作れて、ng 組は作れない、という状態を保っています。ng の初期値 ⌊N/2⌋+1\lfloor N / 2 \rfloor + 1 は、どうやっても作れない組数です。

DOJ Beginner Contest 8 B - Subway Seats

地下鉄の車両に NN 個の座席があり、最初はすべて空いています。MM 人の乗客が順に乗ってきて、ii 人目は座席 AiA_i に座ろうとします。空いていれば座り、すでに誰かが座っていれば立ったままになります。最後に立っている人数を求める問題です。

座れるのは、各座席について最初にその座席を希望した人だけです。座れる人数は AA に現れる値の種類数に等しいので、答えは M−(A の値の種類数)M - (A \text{ の値の種類数}) です。

種類数は、set に入れて大きさを見れば求まります。

Python
for _ in range(int(input())):
N, M = map(int, input().split())
A = list(map(int, input().split()))
print(M - len(set(A)))

DOJ Beginner Contest 8 A - DOJ Beginner Contest

整数 NN が与えられるので、DOJ beginner contest の後ろに空白を 1 つと NN をつなげた文字列を出力する問題です。テストケースは T≤100T \le 100 個です。

そのまま出力します。beginner と contest は小文字です。

Python の print は、複数の引数を空白 1 つで区切って出力するので、print("DOJ beginner contest", N) で求める形になります。

Python
for _ in range(int(input())):
print("DOJ beginner contest", int(input()))

DOJ Beginner Contest 9 G - Pi Problem

正の整数 a,ba, b に対して、aa の十進表記を bb 回つなげた整数を rep(a,b)\mathrm{rep}(a, b) とします。たとえば rep(31,4)=31313131\mathrm{rep}(31, 4) = 31313131 です。

長さ NN の正整数列 AA が与えられるので、

∏1≤i<j≤Nrep(Ai,Aj)\prod_{1 \le i < j \le N} \mathrm{rep}(A_i, A_j)

を 998244353998244353 で割った余りを求める問題です。Ai≤109A_i \le 10^9 で、NN の総和は 2×1052 \times 10^5 以下です。

aa が kk 桁のとき、aa を bb 回つなげることは、aa に 1+10k+102k+⋯+10(b−1)k1 + 10^k + 10^{2k} + \dots + 10^{(b-1)k} を掛けることと同じです。等比数列の和を使うと

rep(a,b)=a⋅10kb−110k−1\mathrm{rep}(a, b) = a \cdot \frac{10^{kb} - 1}{10^k - 1}

です。以下、kk 桁の数を bb 回つなげたときに掛かる部分を fk(b)=10kb−110k−1f_k(b) = \dfrac{10^{kb} - 1}{10^k - 1} と書きます。

AiA_i の桁数を kik_i とすると、求める積は

∏i<jAi⋅fki(Aj)=(∏i<jAi)(∏i<jfki(Aj))\prod_{i < j} A_i \cdot f_{k_i}(A_j) = \left( \prod_{i < j} A_i \right) \left( \prod_{i < j} f_{k_i}(A_j) \right)

と分けられます。

前半では、AiA_i は自分より後ろの jj の個数だけ掛かるので、∏iAiN−i\prod_i A_i^{N - i} です。

後半は、jj ごとにまとめます。Ai≤109A_i \le 10^9 なので桁数 kk は 11 から 1010 までしかありません。i<ji < j で桁数が kk のものの個数を cj,kc_{j,k} とすると、後半は

∏j∏k=110fk(Aj)cj,k\prod_j \prod_{k=1}^{10} f_k(A_j)^{c_{j,k}}

です。cj,kc_{j,k} は桁数ごとの個数を数えながら jj を動かせば求まります。fk(Aj)f_k(A_j) は 11 つの jj につき 1010 通りしかないので、全体で O(10Nlog⁡A)O(10 N \log A) 回程度の計算で済みます。

fk(b)f_k(b) を 998244353998244353 で割った余り

Section titled “fk(b)f_k(b)fk​(b) を 998244353998244353998244353 で割った余り”

fk(b)f_k(b) は割り算を含みます。10k−110^k - 1 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。

M=998244353M = 998244353、d=10k−1d = 10^k - 1、X=10kb−1X = 10^{kb} - 1 とします。XX は dd で割り切れます。XX を dMdM で割った余りを rr とすると、X=q⋅dM+rX = q \cdot dM + r と書けて、rr も dd で割り切れます。両辺を dd で割ると

Xd=qM+rd\frac{X}{d} = qM + \frac{r}{d}

なので、Xd\dfrac{X}{d} を MM で割った余りは rd\dfrac{r}{d} を MM で割った余りと同じです。つまり、10kb10^{kb} を dMdM を法として計算し、11 を引いてから dd で割れば、fk(b)f_k(b) を MM で割った余りが求まります。

Python
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 1
d = [0] * 11
for i in range(N):
ans *= pow(A[i], N - i - 1, MOD)
ans %= MOD
d[len(str(A[i]))] += 1
for i in reversed(range(N)):
d[len(str(A[i]))] -= 1
for j in range(1, 11):
if d[j] == 0:
continue
b = 10**j - 1
x = pow(10, j * A[i], b * MOD)
x -= 1
x %= b * MOD
assert x % b == 0
x //= b
ans *= pow(x, d[j], MOD)
ans %= MOD
print(ans)

最初のループで前半の積を計算し、桁数ごとの個数 d を数えます。2 つ目のループでは後ろから見ていき、d から自分を引くことで、d[j] が「自分より前にある jj 桁の数の個数」になるようにしています。

DOJ Beginner Contest 9 E - 67

長さ NN の十進数 SS が与えられます。SS からいくつかの文字を消し、残った文字をそのままの順で並べた数を 66 の倍数か 77 の倍数にしたい問題です。残す文字は 11 個以上で、先頭が 00 になってもかまいません(00 も 66 と 77 の倍数です)。消す文字の個数の最小値を求め、できなければ −1-1 を出力します。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

42=6×742 = 6 \times 7 は 66 でも 77 でも割り切れるので、ある数が 66 の倍数か 77 の倍数かは、その数を 4242 で割った余り mm だけで決まります。mm が 66 の倍数か 77 の倍数であれば条件を満たします。

SS を先頭から 1 文字ずつ見ていき、

dp[m]=残した文字が表す数を 42 で割った余りが m になるときの、消した文字数の最小値\mathrm{dp}[m] = \text{残した文字が表す数を } 42 \text{ で割った余りが } m \text{ になるときの、消した文字数の最小値}

を更新します。最初は何も残していないので、dp[0]=0\mathrm{dp}[0] = 0、それ以外は ∞\infty です。

次の文字が数字 xx のとき、各 mm について 2 通りの遷移があります。

  • 消す:余りは mm のままで、消した文字数が 11 増えます。
  • 残す:余りは (10m+x) mod 42(10m + x) \bmod 42 になり、消した文字数は変わりません。

最後に、mm が 66 の倍数か 77 の倍数であるものについて dp[m]\mathrm{dp}[m] の最小値をとります。

ただし、全部消した場合も「余り 00、消した文字数 NN」として dp[0]\mathrm{dp}[0] に含まれています。残す文字は 11 個以上という条件があるので、dp[m]<N\mathrm{dp}[m] < N のものだけを答えの候補にします。候補がなければ −1-1 です。

計算量は O(42∑N)O(42 \sum N) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
dp = [float("inf")] * 42
dp[0] = 0
for c in S:
x = int(c)
ndp = [float("inf")] * 42
for i in range(42):
ndp[i] = dp[i] + 1
for i in range(42):
j = (i * 10 + x) % 42
ndp[j] = min(ndp[j], dp[i])
dp = ndp
ans = float("inf")
for i in range(42):
if i % 6 == 0 or i % 7 == 0:
if dp[i] < N:
ans = min(ans, dp[i])
if ans == float("inf"):
ans = -1
print(ans)

DOJ Beginner Contest 9 D - Harvesting the Farm

RR 行 CC 列の農場の NN 個のマスに作物があり、ii 番目の作物は YiY_i 行 XiX_i 列にあります。

収穫機は 1 つの列の中で、連続するいくつかの行を占めます。最初は SrS_r 行 ScS_c 列の 1 マスだけを占めています。収穫機には次の 2 つの操作ができます。

  • 拡張:収穫機の上端か下端に 1 マス付け足す。
  • 移動:収穫機全体を左か右に 1 マスずらす。

操作のあと収穫機が占めるマスに作物があれば、すぐに収穫されます。収穫機が農場の外にはみ出してはいけません。すべての作物を収穫するのに必要な操作回数の最小値を求める問題です。

テストケースは T≤5×104T \le 5 \times 10^4 個あり、NN の総和は 10510^5 以下です。

作物と収穫機の最初の位置を合わせて、

  • 行の最小値を uu、最大値を dd
  • 列の最小値を ll、最大値を rr

とします。答えは

(d−u)+(r−l)+min⁡(Sc−l,r−Sc)(d - u) + (r - l) + \min(S_c - l, r - S_c)

です。

拡張は d−ud - u 回必要で、それで足りる

Section titled “拡張は d−ud - ud−u 回必要で、それで足りる”

収穫機は常に SrS_r 行を含み、拡張 1 回で 1 行ずつしか広がりません。uu 行と dd 行の作物を収穫するには、収穫機がどこかで uu 行と dd 行に届く必要があります。収穫機は縮まないので、最終的には uu 行から dd 行まで全部を占めることになり、拡張は少なくとも d−ud - u 回必要です。

逆に、最初に ScS_c 列で uu 行から dd 行まで広げてしまえば、あとはどの列に行っても、その列の作物はすべて収穫できます。

移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回必要で、それで足りる

Section titled “移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c)(r−l)+min(Sc​−l,r−Sc​) 回必要で、それで足りる”

ll 列から rr 列までのすべての列に、収穫機が少なくとも 1 回は行く必要があります。ScS_c 列から始めて両端に行く最短の動き方は、近いほうの端に行ってから、反対の端まで行くことです。

  • 先に左端に行くと、(Sc−l)+(r−l)(S_c - l) + (r - l) 回
  • 先に右端に行くと、(r−Sc)+(r−l)(r - S_c) + (r - l) 回

なので、移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回です。

拡張を先に全部済ませてから移動すれば、両方の下限を同時に達成できます。

Python
for _ in range(int(input())):
R, C = map(int, input().split())
Sr, Sc = map(int, input().split())
N = int(input())
YX = [tuple(map(int, input().split())) for i in range(N)]
u = d = Sr
l = r = Sc
for y, x in YX:
u = min(u, y)
d = max(d, y)
l = min(l, x)
r = max(r, x)
ans = d - u
f = min(Sc - l + r - l, r - Sc + r - l)
print(ans + f)

ans が拡張の回数、f が移動の回数です。

DOJ Beginner Contest 9 C - Yet Another Permutation Problem 2

11 から NN までの整数の順列 PP が与えられます。P1+Q1,P2+Q2,…,PN+QNP_1 + Q_1, P_2 + Q_2, \dots, P_N + Q_N が広義単調増加になるような順列 QQ を 1 つ作る問題です。答えが複数あれば、どれを出力してもかまいません。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

Qi=N+1−PiQ_i = N + 1 - P_i とします。

PP が 11 から NN の順列なので、N+1−PiN + 1 - P_i も 11 から NN までを 1 回ずつとり、QQ は順列になります。そして、どの ii でも Pi+Qi=N+1P_i + Q_i = N + 1 です。和がすべて等しいので、広義単調増加の条件を満たします。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(int, input().split()))
print(*[N - p + 1 for p in P])

DOJ Beginner Contest 9 B - Rating Updates

最初のレーティングは R0R_0 です。NN 個のコンテストに順に参加し、ii 番目のパフォーマンスが PiP_i のとき、レーティングは

Ri=3Ri−1+Pi4R_i = \frac{3 R_{i-1} + P_i}{4}

に更新されます。最終的なレーティング RNR_N を求める問題です。どの RiR_i も正の整数になることが保証されています。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

式のとおりに RR を NN 回更新します。計算量はテストケース全体で O(∑N)O(\sum N) です。

RiR_i が整数になることが保証されているので、3Ri−1+Pi3 R_{i-1} + P_i は必ず 44 で割り切れます。そのため、整数の割り算 // で正確に計算できます。

Python
for _ in range(int(input())):
N, R = map(int, input().split())
P = list(map(int, input().split()))
for p in P:
R = (3 * R + p) // 4
print(R)

DOJ Beginner Contest 9 A - AI slop

英小文字からなる長さ NN の文字列 SS が与えられます。SS が ai を部分文字列(連続する部分)として含めば AI slop、含まなければ Human made と出力する問題です。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 5×1055 \times 10^5 以下です。

SS に ai が含まれるかを調べるだけです。

a と i がどちらも含まれていても、a のすぐ後ろに i が来ていなければ条件を満たしません(たとえば artificialintelligence は Human made です)。隣り合う 2 文字が a、i の順になっている場所を探します。

Python では "ai" in S で、ai が部分文字列として含まれるかを判定できます。

Python
for _ in range(int(input())):
N = int(input())
S = input()
if "ai" in S:
print("AI slop")
else:
print("Human made")

ShareOJ - A + B Problems

TT 個のテストケースそれぞれについて、2 つの整数 A,BA, B が与えられるので、A+BA + B を出力する問題です。T≤2×105T \le 2 \times 10^5、0≤A,B≤1090 \le A, B \le 10^9 です。

各テストケースについて、AA と BB を読んで和を出力します。

A+BA + B は最大 2×1092 \times 10^9 になり、32 ビット符号付き整数の上限 231−1≈2.1×1092^{31} - 1 \approx 2.1 \times 10^9 を超えます。C++ などでは long long のような 64 ビットの整数型を使う必要があります。Python の整数には上限がないので、気にしなくてかまいません。

Python
for i in range(int(input())):
print(sum(map(int,input().split())))

ShareOJ - Blank

半角スペースだけからなる文字列 SS が与えられるので、その長さを出力する問題です。1≤∣S∣≤1001 \le |S| \le 100 です。

入力の 1 行をそのまま読み、長さを数えます。

注意が要るのは読み込み方です。スペースを区切りとして読み飛ばす方法では、SS を読めません。たとえば C++ の cin >> S は空白を読み飛ばすので、SS は空になってしまいます。C++ なら getline(cin, S) のように、行全体を読む必要があります。

Python の input() は行末の改行だけを取り除き、スペースはそのまま残します。そのため、len(input()) で答えが求まります。逆に input().split() や input().strip() を使うと、スペースが消えてしまいます。

Python
print(len(input()))

ShareOJ - Truth or Lie

11 以上 NN 以下の秘密の整数 xx を当てるインタラクティブ問題です。

? l r と質問すると、xx が ll 以上 rr 以下かどうかが 11(はい)か 00(いいえ)で返ってきます。ただし、ジャッジは嘘つきかもしれません。嘘つきの場合は、常に逆の答えを返します。質問は 2020 回までで、N≤105N \le 10^5 です。

? 1 N と質問します。xx は必ず 11 以上 NN 以下なので、本当の答えは「はい」です。したがって、11 が返ってくればジャッジは正直者、00 が返ってくれば嘘つきだとわかります。

嘘つきなら、これ以降の応答をすべて反転すれば本当の答えになります。

あとは、ふつうの二分探索で xx を求めます。xx がありうる範囲を [l,r][l, r] として、真ん中 mm で区切り、xx が [l,m][l, m] にあるかを質問します。あれば r=mr = m、なければ l=m+1l = m + 1 とします。

範囲の大きさは 1 回ごとに半分(切り上げ)になるので、⌈log⁡2105⌉=17\lceil \log_2 10^5 \rceil = 17 回で 11 つに決まります。最初の 1 回と合わせて 1818 回なので、2020 回に収まります。

Python
N = int(input())
l = 1
r = N
print("?", 1, N, flush=True)
x = (int(input())) ^ 1
while l < r:
m = (l + r) // 2
print("?", l, m, flush=True)
res = int(input())
if res ^ x:
r = m
else:
l = m + 1
print("!", l, flush=True)

変数 x は秘密の整数ではなく、ジャッジが嘘つきなら 11、正直者なら 00 になるフラグです。res ^ x で応答を反転し、本当の答えに直しています。

ShareOJ - Smallest and Largest Subarray

長さ NN の隠された整数列 AA について、連続部分列のうち辞書順で最小のものと最大のものを 1 つずつ答えるインタラクティブ問題です。

? l r l' r' と質問すると、(Al,…,Ar)(A_l, \dots, A_r) が (Al′,…,Ar′)(A_{l'}, \dots, A_{r'}) より辞書順で真に小さいかどうかが返ってきます。N=1000N = 1000 で、質問は Q=1500Q = 1500 回までです。

連続部分列 (Ai,…,Aj)(A_i, \dots, A_j) について、次のことがいえます。

  • 先頭の 1 要素 (Ai)(A_i) はこの列の接頭辞なので、(Ai)(A_i) 以下です。したがって、最小のものは長さ 1 の列 (Ai)(A_i) にとれます。
  • この列は接尾辞 (Ai,…,AN)(A_i, \dots, A_N) の接頭辞なので、接尾辞以下です。したがって、最大のものは接尾辞にとれます。

そこで、接尾辞どうしを比べることにします。長さの違う接尾辞が等しくなることはないので、NN 個の接尾辞はすべて大小が決まります。

  • 最大の接尾辞 (Ar,…,AN)(A_r, \dots, A_N) が、そのまま最大の連続部分列です。
  • 最小の接尾辞 (Al,…,AN)(A_l, \dots, A_N) の先頭 AlA_l は、AA の最小値です。先頭の値がより小さい接尾辞があれば、そちらのほうが小さいからです。よって (Al)(A_l) が最小の連続部分列です。

あとは、NN 個の接尾辞の最小と最大を、比較 15001500 回以内で求めればよいです。

最小と最大を別々に求めると 2(N−1)=19982(N - 1) = 1998 回かかり、間に合いません。

そこで、接尾辞を 2 つずつ組にします。まず組の中で比べ、小さいほうだけを今の最小の候補と、大きいほうだけを今の最大の候補と比べます。1 組あたりの比較は 3 回です。

最初の組は比べるだけで最小と最大の候補になるので 1 回です。N=1000N = 1000 は偶数なので組はちょうど 500500 個できて、比較は全部で 1+3×499=14981 + 3 \times 499 = 1498 回です。15001500 回に収まります。

これは C++ の std::minmax_element と同じ方法です。

Python
N, Q = map(int, input().split())
print("?", 1, N, 2, N, flush=True)
x = int(input())
if x:
l = 1
r = 2
else:
l = 2
r = 1
for i in range(1, N // 2):
print("?", 2 * i + 1, N, 2 * i + 2, N, flush=True)
x = int(input())
if x:
a = 2 * i + 1
b = 2 * i + 2
else:
a = 2 * i + 2
b = 2 * i + 1
print("?", a, N, l, N, flush=True)
x = int(input())
if x:
l = a
print("?", r, N, b, N, flush=True)
x = int(input())
if x:
r = b
print("!", l, l, r, N)

接尾辞 (Ai,…,AN)(A_i, \dots, A_N) を i N で表しています。l は最小の接尾辞の、r は最大の接尾辞の開始位置の候補です。各組では、小さいほうを a、大きいほうを b としています。

Union-Find のリンク集

Union-Find について、参考になる記事や資料をまとめました。

Union-Find(素集合データ構造、DSU)は、互いに交わらない集合の族を管理し、「2 つの集合を併合する」「2 つの要素が同じ集合にあるか判定する」をほぼ定数時間で行えるデータ構造です。各集合を根つき木で表し、経路圧縮と union by size(または union by rank)の両方を使うと、1 回の操作がならし O(α(n))O(\alpha(n)) になります(α\alpha は逆アッカーマン関数)。片方だけでも、ならし O(log⁡n)O(\log n) です。

  • Union find(素集合データ構造)(AtCoder、スライド)
    • AtCoder Typical Contest 001 の B - Union Find の解説スライドです。集合を木で表す考え方から、経路圧縮・ランクによる高速化と C++ 実装までを図を中心に短く説明しています。
    • 実装では配列名に rank を使っているので、using namespace std; と一緒に書き写すと std::rank と名前がぶつかることがあります。
  • Union-Find Tree を理解する!素集合系を扱うデータ構造(アルゴリズムロジック)
    • 素朴な実装から、経路圧縮、union by rank・union by size へと段階的に改良していく解説です。両方の C++ 実装と練習問題がそろっています。
  • PythonでのUnion-Find(素集合データ構造)の実装と使い方(note.nkmk.me)
    • Python での実装を段階的に作っていく記事です。グループの列挙などの便利なメソッドつきのクラスも載っています。
    • 途中に出てくる経路圧縮だけの版は、要素数が多いと再帰の上限に当たることがあります。最後の完成形(union by size つき)なら問題ありません。
  • dsu のドキュメント
    • 公式の仕様です。merge は新しい代表元を返し、groups で連結成分をまとめて取り出せます。実装は union by size と経路圧縮の併用です(ソースのコメントに書かれています)。
  • Union-Find の計算量上界
    • 経路圧縮と union by size を併用したときの計算量が O(N+Qα(N))O(N + Q\alpha(N)) であることを証明する講座です。上級者向けです。
  • アッカーマン関数,逆アッカーマン関数
    • 上の講座の準備として、アッカーマン関数と逆アッカーマン関数の定義と、文献ごとの定義の違いを整理しています。
  • Union Find(Luzhiled’s Library)
    • 短くて読みやすい C++ 実装で、各関数の計算量が日本語で書かれています。同じライブラリに、重み付き、undo 付き、部分永続などの派生版もあります。
    • 部分永続版のドキュメントは find を O(α)O(\alpha) としていますが、経路圧縮をしていないので、実際は O(log⁡n)O(\log n) です。
  • Disjoint-set data structure(英語版 Wikipedia)
    • 経路圧縮・path halving・path splitting と union by size/rank の擬似コード、片方だけ使ったときと両方使ったときの計算量、歴史や変種まで網羅しています。右上の表の Search の最悪計算量が O(α(n))O(\alpha(n)) になっていますが、本文にあるとおり 1 回あたりの最悪は Θ(log⁡n)\Theta(\log n) です。
  • 素集合データ構造(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、基本操作と union by rank・経路圧縮の擬似コードを日本語で確認できます。経路圧縮だけを使ったときの計算量は載っていません。
  • Disjoint Set Union(cp-algorithms)
    • 基本に加えて、偶奇つき Union-Find による二部グラフ判定、区間塗りのオフライン処理など、応用を幅広くまとめています。
  • ABC478 E - lt and le
    • 公式解説の方針を紹介する節で、同じ値になる頂点のグループを DSU でまとめています。

Cartesian Tree のリンク集

Cartesian Tree について、参考になる記事や資料をまとめました。

Cartesian Tree は、数列の最小値を根にし、その左側と右側の部分列から左右の部分木を再帰的に作った二分木です(最大値を根にする流儀もあります)。添字について見ると二分探索木、値について見るとヒープになっています。スタックを使えば O(N)O(N) で構築できます。「区間を最小値で分割して再帰する」分割統治は、この木の上の再帰とみなせます。

同じ値があるときは、どちらを小さいとみなすかで木の形が変わります。下の資料の多くは左端の最小値を根にしていますが、右端を根にするものもあるので注意してください。

区間最小値(RMQ)は、Cartesian Tree の上の 2 頂点の最小共通祖先(LCA)に対応します。

  • 前処理O(n)クエリO(1)のLCAと静的RMQ(joisino)
    • RMQ を Cartesian Tree の上の LCA に帰着させ、前処理 O(n)O(n)・クエリ O(1)O(1) を実現する記事です。スタックによる構築も図で説明しています。
  • Solve RMQ by finding LCA(cp-algorithms、英語)
    • RMQ が LCA に帰着できることの説明と、スタックによる構築のコードがあります。このコードでは、同じ値があると右端の最小値が根になります。
  • LCA and RMQ 簡潔もあるよ!(井上祐馬、スライド)
    • RMQ から LCA への帰着から、簡潔データ構造まで扱う上級者向けの資料です。

Cartesian Tree を扱う講座はまだありません。

  • Cartesian Tree(Nyaan’s Library)
    • 日本語のドキュメントつきの実装です。同じ値があるときは左端の最小値を根にすると明記されています。戻り値は子のリストと根の組で、左右の子は区別されません。

百科事典・英語・中国語の資料

Section titled “百科事典・英語・中国語の資料”
  • Cartesian tree(英語版 Wikipedia)
    • 定義と同じ値の扱い、線形時間の構築法をいくつか、RMQ・LCA や Treap との関係までを網羅しています。日本語版の記事はありません。
  • 笛卡尔树(OI Wiki、中国語)
    • 右端の鎖を単調スタックで管理する O(n)O(n) 構築を図とコードで説明し、ヒストグラム中の最大長方形への応用を例題として扱っています。
  • Treap (Cartesian tree)(cp-algorithms、英語)
    • ロシア語圏などでは Treap のことも Cartesian tree と呼ぶため、この記事の題に入っています。中身は Treap の解説で、数列から作る Cartesian Tree の説明ではありません。

BIT のリンク集

BIT(Binary Indexed Tree、Fenwick Tree)について、参考になる記事や資料をまとめました。

BIT は、列に対して「1 点への加算」と「先頭からの和(prefix 和)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。区間 [l,r)[l, r) の和は、2 つの prefix 和の差で求まります。セグメント木よりできることは少ないものの、実装が短く高速です。BIT を 2 本使った区間加算や、BIT 上の二分探索(累積和が ww 以上になる最初の位置を O(log⁡N)O(\log N) で求める)もよく使われます。

  • Binary Indexed Tree のはなし(hos、JOI 春合宿 2014 の講義スライド)
    • BIT の動きを図で 1 ステップずつ追いながら、1 点加算・prefix 和、区間加算、2 次元 BIT、BIT 上の二分探索まで解説しています。日本語の BIT 解説の定番です。
    • p.75 の二分探索の擬似コードの「n 以下の最小の 2 ベキ」は「最大」の誤りです。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • 1 点加算・区間和から、BIT 2 本による区間加算、BIT 上の二分探索、転倒数、2 次元 BIT までを図と C++ のコードでまとめています。練習問題も付いています。
    • 転倒数の手順は、値が 1 以上であることを前提にしています。値に 0 があるときは、1 を足すか座標圧縮してから使ってください。
  • fenwick_tree のドキュメント
    • 公式の仕様です。0-indexed で、区間和は半開区間 [l,r)[l, r) で求めます。BIT 上の二分探索はありません。

BIT を扱う講座はまだありません。

  • Binary Indexed Tree(Fenwick Tree)(ikatakos)
    • Python の実装集です。区間加算(BIT 2 本)、累積和の二分探索、BIT に載せられる演算の条件、座標圧縮や辞書を使った BIT、2 次元 BIT まで扱っています。
    • 区間加算版の sum に : の抜けがあり、演算を渡せる版の lower_bound はそのままでは動きません。通常版の Bit.lower_bound は正しく動きます。
  • Binary Indexed Tree(Luzhiled’s Library)
    • BIT 上の二分探索 lower_bound・upper_bound を備えた実装です。1 点加算は apply、区間和は prod という名前です。
  • Fenwick Tree(data-structures)
    • BIT でできる操作を、可換モノイドの場合とアーベル群の場合に分けて整理しています。参考資料や実装へのリンクもまとまっています。
  • Fenwick tree(英語版 Wikipedia)
    • 同じ配列を、部分和用・更新用・二分探索用の 3 つの木として見ることで、BIT の構造を説明しています。
  • フェニック木(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、細かい誤りがあります。たとえば多次元の場合の計算量が O(4dlog⁡dn)O(4^d \log_d n) になっていますが、引用元では O(4dlog⁡dn)O(4^d \log^d n) です。
  • Fenwick Tree(cp-algorithms)
    • 0-indexed と 1-indexed の両方の実装、2 次元 BIT、BIT 2 本による区間加算・区間和まで扱っています。練習問題も多く載っています。

セグメント木のリンク集

セグメント木について、参考になる記事や資料をまとめました。

セグメント木は、列に対して「1 点の更新」と「区間の積(和・最小値・最大値など)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。演算が結合法則を満たし、単位元を持つ(モノイドである)ことが条件です。区間に対する更新も行えるように拡張したものを、遅延評価セグメント木(遅延セグ木)と呼びます。区間 chmin のように遅延セグ木にそのままでは載らない作用を扱うための拡張に、Segment Tree Beats があります。

セグメント木そのものを解説する講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 区間の情報をどう持ち、どう結合するかを、区間和・区間最小値から関数合成・行列まで例を挙げて解説しています。セグメント木を使ったことがある人向けです。
  • 代数構造用語集
    • モノイドなどの用語の定義です。
  • 永続セグメント木
    • 過去の状態を残したまま更新できるようにしたセグメント木です。
  • セグメント木(Wikipedia)
    • 前半は Bentley による元々の segment tree(線分の集合を格納し、ある点を含む線分を列挙する木)の説明で、競プロで使うものとは別物です。モノイドへの一般化と配列による実装は後半にありますが、細かい誤りがあるので、ほかの資料と合わせて読むのがおすすめです。
  • Segment Tree(cp-algorithms)
    • 英語の定番の解説です。応用例が多く載っています。

yukicoder contest 517 D - Streaming Schedule

NN 日間、毎日「配信する」か「休む」かを選びます。ii 日目に配信するとファンが AiA_i 人増え、休むと何も起きません(1≤Ai≤1091 \le A_i \le 10^9)。

ただし、BB 日以上続けて休むことはできず、CC 日以上続けて配信することもできません(2≤B,C≤N+12 \le B, C \le N + 1)。増えるファンの人数の最大値を求めてください(N≤3×105N \le 3 \times 10^5)。

配信が続く区間を「配信区間」と呼びます。配信区間の長さは C−1C - 1 以下、休みが続く区間の長さは B−1B - 1 以下でなければなりません。

3 日以上続く休みは考えなくてよい

Section titled “3 日以上続く休みは考えなくてよい”

Ai≥1A_i \ge 1 なので、配信する日は多いほうが得です。3 日以上続く休みがあれば、その真ん中の 1 日を配信に変えられます。この日の両隣は休みのままなので、長さ 1 の配信区間ができるだけです。C≥2C \ge 2 なので長さ 1 の配信区間は必ず許され、休みの区間も短くなるだけなので、条件は崩れません。しかもファンは増えます。

したがって、最適解では休みは 2 日までしか続きません。B=2B = 2 なら連続休みは 1 日まで、B≥3B \ge 3 なら 2 日まで許されます。以下では、B≥3B \ge 3 のときは連続休みの長さに上限を設けずに計算します。上限を超える休み方は、真ん中を配信に変えたものより必ず悪いので、最大値は変わりません。

resti\mathrm{rest}_i を「ii 日目に休むときの、ii 日目までのファンの増加数の最大値」とします。ii 日目に休む直前の状況で場合分けします。

  • 前日も休み:resti−1\mathrm{rest}_{i-1}。B≥3B \ge 3 のときだけ選べます。
  • 前日まで配信区間:配信区間が jj 日目から i−1i - 1 日目までなら、j−1j - 1 日目は休みです。値は restj−1+(Aj+⋯+Ai−1)\mathrm{rest}_{j-1} + (A_j + \dots + A_{i-1}) で、配信区間の長さの制約から i−(C−1)≤j≤i−1i - (C - 1) \le j \le i - 1 です。
  • ii 日目が 1 日目:何もしていないので 00 です。

1 日目より前の日を「0 日目に休んだ」とみなして rest0=0\mathrm{rest}_0 = 0 とおくと、配信区間が 1 日目から始まる場合も 2 つ目の式で扱えます。ただし、1 日目に休むときに「前日も休み」の場合として扱うと、B=2B = 2 では選べなくなってしまいます。そこで 1 日目に休む場合は、BB によらず 00 とします(下の補足も参照)。

最終日に休む場合の答えは restN\mathrm{rest}_N、最終日まで配信する場合の答えは jj 日目から NN 日目までの配信区間を使った同じ式で求まります。

累積和 Si=A1+⋯+AiS_i = A_1 + \dots + A_i を使うと、2 つ目の式は

restj−1+Si−1−Sj−1=(restj−1−Sj−1)+Si−1\mathrm{rest}_{j-1} + S_{i-1} - S_{j-1} = (\mathrm{rest}_{j-1} - S_{j-1}) + S_{i-1}

と書けます。ii が 1 増えると、jj の範囲は 1 つずつ右にずれます。したがって、長さ C−1C - 1 の窓の中での restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} の最大値が分かればよく、これは deque を使ったスライド最大値で求まります。

計算量は O(N)O(N) です。

最初は 1 日目に休む場合も「前日も休み」として扱っていて、WA になりました。たとえば N=2,B=2,C=2,A=(8,9)N = 2, B = 2, C = 2, A = (8, 9) では、1 日目に休んで 2 日目に配信する 99 が正解です。しかし、1 日目の休みを「0 日目からの連続休み」とみなすと、B=2B = 2 で禁止されて 88 になってしまいます。0 日目は実際には休みではないので、1 日目だけは BB によらず休めるようにする必要があります。

Python
from collections import deque
N, B, C = map(int, input().split())
A = list(map(int, input().split()))
t = 0
k = 0
d = deque()
e = deque()
for i, a in enumerate(A):
if d:
u = e[0] + k
else:
u = -(10**18)
if B > 2 or i == 0:
u = max(u, t)
d.append(t - k)
e.append(t - k)
while len(e) >= 2 and e[-2] < e[-1]:
x = e.pop()
e.pop()
e.append(x)
k += a
while len(d) >= C:
x = d.popleft()
if len(e) > 0 and e[0] == x:
e.popleft()
t = u
print(max(t, max(d) + k))

変数の意味は次のとおりです。

  • t:前日に休んだときの最大値(resti−1\mathrm{rest}_{i-1})
  • k:前日までの累積和(Si−1S_{i-1})
  • u:その日に休んだときの最大値(resti\mathrm{rest}_i)
  • d:配信区間の始まりの候補 jj について、restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} を並べた窓。最大 C−1C - 1 個を持ちます。
  • e:d のうち、後ろにより大きい値がないものだけを残した deque。先頭が窓の中の最大値です。

d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 xx が e から消えているなら、xx より後に xx より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は xx より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。

yukicoder contest 517 A - Happy End

英大文字からなる長さ NN の文字列 SS があります(5≤N≤3×1055 \le N \le 3 \times 10^5)。文字列 TT が「良い」とは、TT の末尾 5 文字が HAPPY で、それ以外の場所に HAPPY が部分文字列として現れないことをいいます。

SS の 1 文字を別の文字に書き換える操作を繰り返して SS を良い文字列にするとき、操作回数の最小値を求めてください。

末尾 5 文字は必ず HAPPY にしなければならないので、HAPPY と異なる文字の個数だけ書き換えが必要です。

次に、末尾以外に現れる HAPPY をすべて壊します。ここで大事なのは、HAPPY 同士は重なって現れないことです。HAPPY の中で H は先頭にしかないので、HAPPY の途中から別の HAPPY が始まることはありません。

そのため、末尾以外に現れる HAPPY は、末尾の HAPPY とも互いにも重なりません。重ならない HAPPY を 1 つ壊すには少なくとも 1 文字書き換える必要があり、1 回の書き換えで 2 つ同時に壊すこともできません。よって、末尾以外に現れる HAPPY の個数が、この段階で必要な操作回数の下限になります。

この下限は達成できます。各 HAPPY の 1 文字を、HAPPY に含まれない文字(たとえば Z)に書き換えればよいです。HAPPY に含まれない文字を含む位置からは新しい HAPPY が生まれないので、書き換えによって別の場所に HAPPY ができることはありません。

答えは 2 つの段階の操作回数の和で、計算量は O(N)O(N) です。

Python
N = int(input())
S = list(input())
ans = 0
for i in range(1, 6):
if S[-i] != "HAPPY"[-i]:
S[-i] = "HAPPY"[-i]
ans += 1
for i in range(N - 5):
if S[i : i + 5] == list("HAPPY"):
S[i + 4] = "Z"
ans += 1
print(ans)

前半のループで末尾 5 文字を HAPPY にそろえ、後半のループで末尾以外の HAPPY を見つけるたびに最後の Y を Z に書き換えています。