コンテンツにスキップ

ブログ

ABC484 F - Make them monochrome

−1-1 または正整数からなる数列 AA に対し、次のクエリを処理する問題です(N,Q≤3×105N,Q\le3\times10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:区間 [l,r][l,r] の各 −1-1 を好きな正整数に置き換えたとき、区間内をすべて同じ値にできるか判定する。

−1-1 は自由に置き換えられるので、区間内にもともとある正整数がすべて同じなら Yes です。正整数がなければ、すべての −1-1 を例えば 11 にできます。異なる正整数が 22 種類以上あれば、どちらも変更できないので No です。

この条件を、区間内の異なる値を大きい順に 22 種類まで取得して判定します。各値の出現回数も一緒に保持します。

  • 11 種類しかなければ、そのまま同じ値か、すべて −1-1 なので Yes。
  • 上位 22 種類の出現回数の和が区間長より小さければ、ほかにも値があり、少なくとも 33 種類あるので No。
  • ちょうど 22 種類なら、小さい方が −1-1 の場合だけ Yes。

−1-1 はすべての正整数より小さいので、最後の条件で「−1-1 と正整数 11 種類だけ」を判定できます。

上位2種類をセグメント木で管理する

Section titled “上位2種類をセグメント木で管理する”

各区間に、値が大きい順の 22 種類と、それぞれの出現回数を持たせます。左右の区間を結合するときは、同じ値の個数を足し合わせ、上位 22 種類だけを残します。

片方の区間で上位 22 種類に入らない値は、その区間だけでそれより大きい値が 22 種類あります。よって、結合後の上位 22 種類にも入りません。このため、各区間で上位 22 種類だけを残しても、結合後の値と個数を正確に求められます。

この情報をセグメント木に持たせると、値の変更は 11 点更新、判定は区間取得で処理できます。結合する情報の大きさは定数なので、各クエリは O(log⁡N)O(\log N)、全体では O(N+Qlog⁡N)O(N+Q\log N) です。空間計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/priority_counter.hpp"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
using S = MaxCounter<ll, 2>;
RSumQ<S> seg(A);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
i--;
seg.set(i, S{x});
} else {
LL(l, r);
l--;
auto tmp = seg.prod(l, r);
if (tmp.size() == 1) {
print("Yes");
continue;
}
if (tmp[0].second + tmp[1].second < r - l) {
print("No");
continue;
}
if (tmp[1].first == -1) {
print("Yes");
} else {
print("No");
}
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

自作ライブラリの MaxCounter<ll, 2> は値の大きい順に 22 種類までを、その個数とともに保持します。+ でこの情報を結合できるため、RSumQ に載せています。tmp.size() は保持している種類数なので、元の区間に 33 種類以上ある場合も 22 になります。

ABC484 E - Subsegment Sum Finder

長さ NN の数列 AA について、総和が LL 以上 RR 以下になる空でない連続部分列の個数を求める問題です。取り出す位置が異なる部分列は区別します(N≤3×105N\le3\times10^5)。AA には負の値も含まれます。

P0=0P_0=0、Pj=A1+⋯+AjP_j=A_1+\cdots+A_j とします。位置 i+1i+1 から jj までの和は Pj−PiP_j-P_i なので、条件は

L≤Pj−Pi≤R⟺Pj−R≤Pi≤Pj−LL\le P_j-P_i\le R \quad\Longleftrightarrow\quad P_j-R\le P_i\le P_j-L

です。

右端 jj を左から順に処理すると、それまでの累積和 P0,…,Pj−1P_0,\dots,P_{j-1} のうち、区間 [Pj−R,Pj−L][P_j-R,P_j-L] に入るものの個数を求めればよいです。負の要素があるため累積和は単調とは限りませんが、値ごとの出現回数を管理すれば数えられます。

すべての累積和を座標圧縮し、各値がこれまでに何回現れたかをセグメント木に持ちます。最初に P0=0P_0=0 の個数を 11 にします。

現在の累積和を tt とすると、圧縮した値の列で bisect_left(t - R) から bisect_right(t - L) までの半開区間の個数の和を求めます。上端に bisect_right を使うことで、t−Lt-L と等しい値も含められます。区間の端の値そのものが圧縮対象に含まれていなくても、二分探索で境界を求められます。

個数を答えに加えてから、現在の累積和 tt の個数を 11 増やします。問い合わせを先に行うことで、空の部分列を数えず、必ず i<ji<j の組だけを数えられます。同じ累積和が複数回現れる場合も、その出現回数を足すので正しく扱えます。

座標圧縮と各右端の処理を合わせ、計算量は O(Nlog⁡N)O(N\log N)、空間計算量は O(N)O(N) です。累積和と答えには 64 bit 整数を使います。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/utility/compress.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N, L, R);
VL(A, N);
Compress<ll> C(cumulative_sum(A));
RSumQ<ll> seg(C.size());
seg.apply(C.id(0), 1);
ll ans = 0, t = 0;
for (ll a : A) {
t += a;
ans += seg.prod(C.bisect_left(t - R), C.bisect_right(t - L));
seg.apply(C.id(t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

自作ライブラリの Compress と SegTree を使っています。cumulative_sum(A) は先頭の 00 を含む累積和を返し、seg.apply(i, 1) は位置 ii の個数を 11 増やします。

ABC484 D - Move One Card Left

長さ NN の数列 AA から要素を 11 つ取り出し、元の位置かそれより左へ挿入します。この操作をちょうど 11 回行って作れる異なる数列の個数を求める問題です(N≤2×105N\le2\times10^5)。操作で選んだ位置が違っても、結果の数列が同じなら 11 通りと数えます。

同じ結果になる操作をまとめる

Section titled “同じ結果になる操作をまとめる”

元の位置に戻す操作では数列が変わらないので、まず元の数列を 11 通りとして数えます。

位置 ii の値 a=Aia=A_i を左へ移すことを考えます(以下、位置は 0 始まり)。直前も同じ値、つまり Ai−1=aA_{i-1}=a なら、位置 ii から移す代わりに位置 i−1i-1 の aa を移しても同じ結果になります。よって、同じ値が連続する区間では先頭の位置だけを移動元として数えれば十分です。

また、挿入先の値も aa なら、その aa の直後へ挿入しても同じ結果です。これを繰り返し、挿入先が aa と異なる位置になるまで右へずらします。最後まで同じ値しかなければ、元の数列と同じなので追加で数えません。

したがって、新しく数える操作は次の条件に絞れます。

  • 移動元 ii は同じ値が連続する区間の先頭。
  • 挿入先 jj は j<ij<i かつ Aj≠AiA_j\ne A_i を満たす位置。

この条件では、操作後に元の数列と初めて異なる位置が jj、最後に異なる位置が ii です。よって、異なる (i,j)(i,j) が同じ数列を作ることはなく、重複せずに数えられます。

左から走査し、それまでに現れた値 aa の個数を c[a] に持ちます。位置 ii より前には ii 個の要素があり、そのうち aa と異なるものは

i−c[a]i-c[a]

個です。直前の値と異なるときだけ、この個数を答えに加えます。

コードでは前の値を p に保持し、p != a で連続区間の先頭かを判定しています。走査自体は O(N)O(N) 回で、使っている Counter は平衡二分探索木で個数を管理するため、計算量は O(Nlog⁡N)O(N\log N)、空間計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
LL(N);
VL(A, N);
Counter<ll> c;
ll ans = 1;
ll p = -1;
rep(i, N) {
ll a = A[i];
if (p != a) {
ans += i - c[a];
}
c.inc(a);
p = a;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

自作ライブラリの Counter で値ごとの出現回数を管理しています。

ABC484 C - Move One Card

長さ NN の数列 A,BA,B が与えられます。AA から要素を 11 つ取り出し、好きな位置に挿入する操作をちょうど 11 回行って、BB にできるか判定する問題です(N≤2×105N\le2\times10^5)。元の位置に戻しても構いません。

右の要素を左へ移す場合を調べる

Section titled “右の要素を左へ移す場合を調べる”

まず、AA のある要素を左へ移して BB にできるかを判定します。左から比較し、最初に一致しない位置を ll とします。この位置では、右のどこかから持ってきた値 BlB_l を挿入する必要があります。

挿入した値を f=Blf=B_l とし、その後は BiB_i と Ai−1A_{i-1} を比較します。挿入によって、間にあった要素が 11 つずつ右へずれるためです。

ずらした比較が初めて一致しなくなる位置を ii とすると、ここで元の位置から ff を取り出したと考えます。そのためには

Ai−1=f,Ai=BiA_{i-1}=f,\qquad A_i=B_i

が必要です。この条件を満たせば、以降は再び AiA_i と BiB_i を比較します。その後に不一致があれば、11 回の移動では作れません。

途中で元の比較に戻せないまま末尾まで一致した場合は、末尾の要素を取り出したと考えます。この場合は AN=fA_N=f なら成功です。

同じ値が続くと、実際に取り出す位置より後までずらした比較が一致することがあります。しかし、その間は移す値 ff と同じ値が続いているので、取り出す位置を後ろへずらしても結果は変わりません。よって、最初の不一致まで比較を続けて構いません。

左の要素を右へ移す操作の逆操作は、右の要素を左へ移す操作です。したがって、AA と BB を交換して同じ判定を行えば、右へ移す場合も調べられます。

もともと A=BA=B の場合も、取り出した要素を同じ位置に戻せるので Yes です。22 回の走査のどちらかが成功すれば Yes、両方失敗したら No を出力します。計算量は O(N)O(N) です。

コードの t は比較位置のずれ(00 または −1-1)、f は移す値、c は「挿入前」「挿入後・取り出し前」「取り出し後」の段階を表しています。

C++
#include "shogo-library/base/all"
void solve() {
LL(N);
VL(A, N);
VL(B, N);
rep(2) {
ll t = 0, c = 0, f = -1, ok = 1;
rep(i, N) {
if (A[i + t] == B[i])
continue;
if (c == 0) {
t = -1;
f = B[i];
c++;
} else if (c == 1) {
if (f != A[i + t]) {
ok = 0;
break;
} else if (A[i] != B[i]) {
ok = 0;
break;
} else {
f = -1;
t = 0;
c++;
}
} else {
ok = 0;
break;
}
}
if (c == 1) {
if (f != A.back()) {
ok = 0;
}
}
if (ok) {
print("Yes");
return;
}
std::swap(A, B);
}
print("No");
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

ABC484 B - Nineball

ナインボールの卓上に KK 個のボールが残っており、その番号が A1,A2,…,AKA_1,A_2,\dots,A_K です。99 番のボールが残っていれば最小の番号を、残っていなければゲームが終了しているので −1-1 を出力する問題です。

まず、9 in A で 99 番のボールが残っているかを調べます。残っていれば min(A)、そうでなければ −1-1 を出力します。

99 の有無を先に判定することで、ゲームが終了している場合も正しく扱えます。計算量は O(K)O(K) です。

Python
K = map(int, input().split())
A = list(map(int, input().split()))
if 9 in A:
print(min(A))
else:
print(-1)

ABC484 A - Chocolate Bar Count

縦 3030 行、横 3030 列の板チョコから、一番下の行を取り除く操作を BB 回、一番右の列を取り除く操作を RR 回行います。残るチョコレートの片数を求める問題です。

操作後の行数は 30−B30-B、列数は 30−R30-R です。残った長方形のマス数を求めればよいので、答えは (30−B)(30−R)(30-B)(30-R) になります。

Python
B, R = map(int, input().split())
print((30 - B) * (30 - R))

DOJ Starter Contest 1 I - 수열 정렬하기 5

数列 AA の「整列度」を、i<ji<j かつ Ai<AjA_i<A_j を満たす組 (i,j)(i,j) の個数とします。隣り合う要素の交換をちょうど KK 回行った後の整列度を最大化し、その値と交換手順を出力する問題です(2≤N≤10002\le N\le1000、0≤K≤5×1050\le K\le5\times10^5)。

逆転している隣接要素を交換する

Section titled “逆転している隣接要素を交換する”

隣り合う 22 要素を交換しても、それ以外の要素との前後関係は変わりません。よって、整列度の変化は交換する 22 要素の関係だけで決まります。

  • 左の要素が大きい場合は、整列度が 11 増える。
  • 左の要素が小さい場合は、整列度が 11 減る。
  • 同じ値の場合は、整列度は変わらない。

したがって、まずは左の要素が大きい隣接対を交換します。数列が整列済みでなければそのような場所は必ず存在するので、整列するまでは毎回 11 ずつ増やせます。11 回で 11 より大きく増やすことはできないため、これが最適です。

コードではバブルソートの走査を NN 回行い、交換回数が残っている間だけ逆転した隣接対を交換しています。KK 回を使い切った場合は、その状態が答えになります。

整列後に残った交換を消化する

Section titled “整列後に残った交換を消化する”

整列しても交換回数が残っている場合、同じ値の隣接対があれば、そこで交換を繰り返します。数列も整列度も変わらないので、最大の整列度を保てます。

同じ値がない場合は、先頭の 22 要素を繰り返し交換します。22 回交換すれば元に戻るため、残り回数が偶数なら整列済みの状態、奇数なら先頭の 11 組だけが逆転した状態になります。

全要素が異なる場合、隣接交換のたびに転倒数の偶奇が反転します。整列に必要な交換回数を使った後で、さらに奇数回交換して整列済みの状態に戻ることはできません。したがって、この場合の整列度が最大値より 11 小さくなるのは避けられず、先頭の 11 組だけを逆転させる方法が最適です。

最後の数列について、条件 Ai<AjA_i<A_j を満たす組を全探索して整列度を求めます。交換位置は ans に 0 始まりで保存しているので、出力時に 11 を加えます。

バブルソートの走査と整列度の計算が O(N2)O(N^2)、残りの交換と手順の出力が O(K)O(K) なので、計算量は O(N2+K)O(N^2+K)、空間計算量は O(N+K)O(N+K) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for _ in range(N):
for i in range(N - 1):
if K > 0 and A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
K -= 1
ans.append(i)
i = 0
for j in range(N - 1):
if A[j] == A[j + 1]:
i = j
break
while K > 0:
A[i], A[i + 1] = A[i + 1], A[i]
K -= 1
ans.append(i)
print(sum(A[i] < A[j] for i in range(N - 1) for j in range(i + 1, N)))
for a in ans:
print(a + 1)

DOJ Starter Contest 1 H - 수열 안 정렬하기 2

長さ NN の整数列 AA を並べ替えて作れる異なる数列のうち、広義単調増加ではないものの個数を求める問題です。同じ値の要素は区別しません(N≤105N\le10^5)。答えは 101210^{12} 以下であることが保証されています。

値 vv の出現回数を cvc_v とすると、異なる並べ方の総数は

P=N!∏vcv!P=\frac{N!}{\prod_v c_v!}

です。要素を区別した並べ方 N!N! から、同じ値同士の入れ替えによる重複を除いています。

このうち広義単調増加な並べ方は、昇順にソートした 11 通りだけです。よって、答えは P−1P-1 です。

コードでは、大きな階乗をそのまま計算する代わりに、p=109+7p=10^9+7 と q=109+9q=10^9+9 のそれぞれを法として PP の余りを求めています。

どちらの素数も NN より大きいため、cv!c_v! は法の倍数になりません。したがって逆元が存在し、分母の逆元を掛けることで割り算できます。pow(t, -1, m) が、法 mm での tt の逆元を求めています。

関数 q(m) では階乗を法 mm で前計算し、P mod mP\bmod m を返します。

小さい答えの保証を使って復元する

Section titled “小さい答えの保証を使って復元する”

P mod p=xP\bmod p=x、P mod q=yP\bmod q=y とすると、PP はある非負整数 ii を使って

P=pi+xP=pi+x

と書けます。そこで ii を順に試し、(pi+x) mod q=y(pi+x)\bmod q=y になるものを探します。

答えが 101210^{12} 以下なので、P≤1012+1P\le10^{12}+1 です。よって i=⌊P/p⌋<1000i=\lfloor P/p\rfloor<1000 であり、コードの range(10**4) で必ず見つかります。また、この探索範囲の候補はすべて pqpq 未満です。異なる2つの素数を法とする余りが両方一致する数は pqpq 未満の範囲で一意なので、見つかった候補が PP そのものです。

最後に 11 を引いて答えを出力します。計算量は、ハッシュ表の平均的な操作時間を仮定すると、階乗と出現回数の計算が O(N)O(N)、逆元計算が各法について O(log⁡m)O(\log m)、復元の探索が高々 10410^4 回です。

Python
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
def q(m):
l = [1]
for i in range(N):
l.append(l[-1] * (i + 1) % m)
res = l[N]
t = 1
for i in C.values():
t = t * l[i] % m
res = res * pow(t, -1, m) % m
return res
x = q(10**9 + 7)
y = q(10**9 + 9)
for i in range(10**4):
if ((10**9 + 7) * i + x) % (10**9 + 9) == y:
print((10**9 + 7) * i + x - 1)
break

DOJ Starter Contest 1 G - 수열 정렬하기 4

長さ NN の整数列 AA に対し、ある要素に 11 を加え、それ以外のすべての要素から 11 を引く操作を行えます。数列を広義単調増加にするための最小操作回数を求める問題です(N≤105N\le10^5、0≤Ai≤1090\le A_i\le10^9)。

この操作は「全要素から 11 を引いて、選んだ要素に 22 を加える」と言い換えられます。全要素に同じ値を足し引きしても大小関係は変わらないので、整列の可否だけを考えるなら、選んだ要素に 22 を加える操作として扱えます。

そこで、左から順に、直前の要素以上になるまで必要な回数だけ 22 を加えます。先頭には加える必要がありません。各要素を必要以上に大きくすると後続の要素の条件が厳しくなるので、必要最小限だけ加えるのが最適です。

より具体的には、要素 ii の操作回数を tit_i とすると、条件は

Ai+2ti≤Ai+1+2ti+1A_i+2t_i\le A_{i+1}+2t_{i+1}

です。t1=0t_1=0 とし、直前の tit_i が決まったらこの不等式を満たす最小の非負整数 ti+1t_{i+1} を選びます。他の実現可能な操作回数列と比べても、帰納的に各 tit_i が最小になるので、その総和も最小です。

コードでは、隣接差分 d[i] = A[i + 1] - A[i] を管理しています(0 始まり)。すべての差分が 00 以上になれば整列済みです。

d[i] が負なら、右側の要素 A[i + 1] に 22 を加える操作を

t=⌈−d[i]2⌉t=\left\lceil\frac{-d[i]}{2}\right\rceil

回行います。負の d[i] に対して、これは (1 - d[i]) // 2 で求められます。

この操作で d[i] は 2t2t 増えます。また、次の差分 d[i + 1] は 2t2t 減ります。それ以外の差分は変わりません。左からこの更新を繰り返すと、すでに直した差分を壊さずに処理できます。

差分を 11 回走査するだけなので、計算量・空間計算量はともに O(N)O(N) です。

Python
N = int(input())
A = list(map(int, input().split()))
d = [A[i] - A[i - 1] for i in range(1, N)]
ans = 0
for i in range(len(d)):
if d[i] < 0:
t = (1 - d[i]) // 2
ans += t
d[i] += 2 * t
if i < len(d) - 1:
d[i + 1] -= 2 * t
print(ans)

DOJ Starter Contest 1 F - 문자열 정렬하기

英小文字からなる NN 個の文字列が与えられます。文字列のスコアを、各文字の出現回数の二乗の和とします。例えば abaca のスコアは 32+12+12=113^2+1^2+1^2=11 です。

次の優先順位で文字列を並べ、11 行に 11 つずつ出力する問題です(N≤5×104N\le5\times10^4、各文字列の長さは 2020 以下)。

  1. スコアが小さい順
  2. 長さが短い順
  3. 辞書順

同じ文字列も、与えられた個数だけ出力します。

各文字列について、Counter で文字ごとの出現回数を数え、その二乗を足せばスコアを求められます。

あとは、ソートのキーとして (スコア, 長さ, 文字列) というタプルを返します。Python はタプルを先頭の要素から順に比較するので、問題で指定された優先順位をそのまま表せます。

S.sort(key=q) では各文字列に対して q が 11 回ずつ呼ばれ、その結果を使ってソートします。最大文字列長を LL とすると、キーの計算に O(NL)O(NL)、文字列の比較も含めたソートに O(NLlog⁡N)O(NL\log N) かかります。

Python
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
def q(s):
c = Counter(s)
return (sum(i**2 for i in c.values()), len(s), s)
S.sort(key=q)
for s in S:
print(s)

DOJ Starter Contest 1 E - 수열 안 정렬하기 1

長さ NN の整数列 AA の要素を並べ替え、広義単調増加ではない数列を 11 つ出力する問題です。そのような並べ方がなければ −1-1 を出力します(N≤105N\le10^5)。

すべての要素が等しい場合は、どう並べ替えても同じ数列になります。その数列は広義単調増加なので、答えは −1-1 です。N=1N=1 の場合もここに含まれます。

異なる値が含まれる場合は、降順に並べればよいです。降順では左の要素が右の要素以上になり、異なる値の境目では左の要素が右より大きくなります。よって、広義単調増加ではありません。

コードでは sort() で昇順にしてから reverse() で逆順にしています。計算量は O(Nlog⁡N)O(N\log N) です。

Python
N = int(input())
A = list(map(int, input().split()))
if all(A[0] == a for a in A):
print(-1)
else:
A.sort()
A.reverse()
print(*A)

DOJ Starter Contest 1 D - 수열 정렬하기 3

長さ NN の整数列 AA に対し、「末尾の要素を先頭へ移す」「先頭の要素を末尾へ移す」という操作を何回でも行えます。数列を広義単調増加にできるか判定する問題です(N≤100N\le100)。

どちらの操作も数列を循環シフトする操作です。何回操作しても、要素の円環上での並び順は変わりません。逆に、先頭にする位置は自由に選べます。

よって、調べるべき数列は、各 i=0,1,…,N−1i=0,1,\dots,N-1 について先頭を ii 番目にした

A[i:] + A[:i]

の NN 通りだけです(0 始まり)。

あらかじめ s = sorted(A) を求め、いずれかの循環シフトが s と一致すれば YES、どれも一致しなければ NO を出力します。ソート済みの並べ方は同じ値を区別しなければ一意なので、この比較で判定できます。

各循環シフトの作成と比較に O(N)O(N) かかるので、計算量は O(N2)O(N^2) です。for に付いた else は、break せずにすべての候補を調べ終えた場合に実行されます。

Python
N = int(input())
A = list(map(int, input().split()))
s = sorted(A)
for i in range(N):
if s == A[i:] + A[:i]:
print("YES")
break
else:
print("NO")

DOJ Starter Contest 1 C - 수열 정렬하기 2

長さ NN の整数列 AA に対し、隣り合う 22 要素を交換する操作を何回でも行えます。数列を広義単調増加にできるか判定する問題です(N≤100N\le100)。

隣り合う要素の交換を繰り返せば、どのような数列でもソートできます。例えば、左の要素が右より大きい場所を交換するバブルソートを使えばよいです。

よって、入力によらず答えは YES です。実際の交換手順は求められていないので、入力を読み込まずに YES を出力するだけで構いません。

Python
print("YES")

DOJ Starter Contest 1 B - 수열 정렬하기 1

長さ NN の整数列 AA が与えられます。要素を並べ替え、すべての 1≤i<N1 \le i < N について Ai≤Ai+1A_i \le A_{i+1} を満たす数列を出力する問題です(1≤N≤31 \le N \le 3、−109≤Ai≤109-10^9 \le A_i \le 10^9)。

数列を昇順にソートすれば、隣り合う要素が Ai≤Ai+1A_i \le A_{i+1} を満たします。Python のリストの sort() は昇順に並べ替えるので、そのまま使えます。

print(*A) とすると、リストの要素を空白区切りで 11 行に出力できます。同じ値が複数あっても、削除せずにすべて出力します。

ソートの計算量は O(Nlog⁡N)O(N\log N) です。

Python
N = int(input())
A = list(map(int, input().split()))
A.sort()
print(*A)

DOJ Starter Contest 1 A - 정렬 문제 이름 붙이기

整数 NN が与えられます。ii 番目の問題の名前を sorting i とするとき、11 番目から NN 番目までの名前を順に出力する問題です(1≤N≤1001 \le N \le 100)。sorting と番号の間には空白を 11 つ入れます。

11 から NN まで順に、sorting と番号を出力します。

コードでは range(N) を使うので、i は 00 から N−1N-1 まで変化します。出力する番号は i + 1 です。print に引数を 22 つ渡すと、その間に空白が入り、最後に改行されるので、指定された形式で出力できます。

Python
for i in range(int(input())):
print("sorting", i + 1)

SamCoding Round 11 (Div. 1) C - Ice Maze

N×MN\times M の氷の盤面で、S から出発して穴 E に到達するまでの最小の滑走回数を求める問題です(N,M≤1000N,M\le 1000)。# は岩、それ以外のマスは氷です。

11 回の滑走では上下左右のいずれかに進み、次のマスが岩または盤面の外になるまで止まれません。ただし、途中で E を通過したらその場で穴に落ち、到達したものとします。到達できない場合は −1-1 を出力します。

滑走を始めるたびに止まる位置まで走査すると、同じ通路を何度も調べてしまいます。そこで、滑走を 11 マスずつの移動に分け、位置に加えて進行方向も状態に持たせます。

dp[k][i][j] を、「マス (i,j)(i,j) に方向 kk に滑っている状態で到達するまでの最小の滑走回数」とします。遷移は次の 22 種類です。

  • 進行方向の隣のマスに進める場合は、そのマスへ同じ方向で移動する。滑走中なので追加コストは 00。
  • 進行方向が岩または盤面の外で塞がれている場合は、その場で次の滑走の方向を選ぶ。新しい滑走を始めるので追加コストは 11。

進める間は方向を変える遷移を作らないことで、途中で止まれないという条件を表せます。塞がれた方向を選ぶ遷移もコードには含まれますが、移動せずに回数が増えるだけなので、最小値を改善することはありません。

辺のコストが 00 または 11 なので、0-1 BFS を使います。コスト 00 の遷移で更新した状態は deque の先頭へ、コスト 11 の遷移で更新した状態は末尾へ追加します。

最初の滑走の方向は自由に選べるので、S の 44 方向の状態をすべて距離 11 で初期化します。

答えは、E にある 44 方向の状態の距離の最小値です。滑走中の各マスを状態にしているので、停止位置になるかどうかによらず、E を通過した時点の回数を求められます。コードでは E から先にも探索を続けますが、そこから先のコストも非負なので、E に初めて到達するまでの最小値は変わりません。

状態数は 4NM4NM で、各状態からの遷移は高々 44 本です。よって、計算量・空間計算量ともに O(NM)O(NM) です。

Python
from itertools import product
from collections import deque
N, M = map(int, input().split())
G = [input() for i in range(N)]
INF = 10**10
dp = [[[INF for j in range(M)] for i in range(N)] for k in range(4)]
q = deque()
for i, j in product(range(N), range(M)):
if G[i][j] != "S":
continue
for k in range(4):
q.append((k, i, j))
dp[k][i][j] = 1
while q:
k, i, j = q.popleft()
di, dj = [(-1, 0), (1, 0), (0, -1), (0, 1)][k]
ni, nj = i + di, j + dj
if ni in range(N) and nj in range(M) and G[ni][nj] != "#":
if dp[k][ni][nj] > dp[k][i][j]:
dp[k][ni][nj] = dp[k][i][j]
q.appendleft((k, ni, nj))
else:
for nk in range(4):
if dp[nk][i][j] > dp[k][i][j] + 1:
dp[nk][i][j] = dp[k][i][j] + 1
q.append((nk, i, j))
ans = INF
for i, j in product(range(N), range(M)):
if G[i][j] != "E":
continue
for k in range(4):
ans = min(ans, dp[k][i][j])
if ans == INF:
print(-1)
else:
print(ans)

SamCoding Round 11 (Div. 1) B - GPU Queue

MM 台の GPU と、実行時間が順に T1,T2,…,TNT_1,T_2,\dots,T_N であるタスクがあります。各 GPU は同時に 11 個のタスクを処理でき、空いた GPU が待ち行列の先頭のタスクをすぐに実行します。

時刻 00 から処理を始めたとき、すべてのタスクが完了する時刻を求める問題です(N,M≤2×105N,M \le 2\times10^5)。

各 GPU が次に空く時刻を管理し、タスクを先頭から順に割り当てます。

あるタスクを実行できるのは、最も早く空く GPU です。その時刻を xx、タスクの実行時間を tt とすると、その GPU が次に空く時刻は x+tx+t になります。同時に空く GPU が複数あっても、どれに割り当てるかで空く時刻の集合は変わりません。

最も早く空く時刻を効率よく取り出すため、最小ヒープを使います。最初はすべての GPU が空いているので、00 を MM 個入れます。各タスクについて、最小値 xx を取り出し、x+tx+t をヒープに戻します。

すべてのタスクを割り当てた後、各 GPU に割り当てた最後のタスクの完了時刻がヒープに残ります。その最大値が、すべてのタスクの完了時刻です。GPU がタスクより多い場合に残る 00 も、そのままで構いません。

計算量は O(M+Nlog⁡(M+1))O(M+N\log(M+1))、ヒープに必要な空間は O(M)O(M) です。

Python
import heapq
N, M = map(int, input().split())
T = list(map(int, input().split()))
hq = [0] * M
for t in T:
x = heapq.heappop(hq)
heapq.heappush(hq, x + t)
print(max(hq))

SamCoding Round 11 (Div. 1) A - Lamps and Switches

11 から 101810^{18} までの番号が付いたランプがあり、最初はすべて消えています。各 ii について、番号が ii の倍数であるランプの点灯状態を一度ずつ反転します。

すべての操作の後、番号が ll 以上 rr 以下のランプのうち、点灯しているものの個数を求める問題です。質問は最大 10510^5 個あり、1≤l≤r≤10181 \le l \le r \le 10^{18} です。

番号 xx のランプは、xx の約数に対応するスイッチを押したときに反転します。最初は消えているので、約数の個数が奇数なら点灯し、偶数なら消えています。

約数は通常、dd と x/dx/d の組になります。ただし、xx が平方数のときだけ、d=x/d=xd=x/d=\sqrt{x} となる約数が 11 つあります。よって、約数の個数が奇数になるのは平方数のときだけです。

つまり、求めるものは区間 [l,r][l,r] に含まれる平方数の個数です。tt 以下の正の平方数は 12,22,…,⌊t⌋21^2,2^2,\dots,\lfloor\sqrt{t}\rfloor^2 の ⌊t⌋\lfloor\sqrt{t}\rfloor 個なので、答えは

⌊r⌋−⌊l−1⌋\lfloor\sqrt{r}\rfloor-\lfloor\sqrt{l-1}\rfloor

となります。

Python の math.isqrt(t) は、⌊t⌋\lfloor\sqrt{t}\rfloor を整数のまま正確に求めます。浮動小数点数を経由しないので、101810^{18} 付近の値も丸め誤差を気にせず扱えます。コードの q(t) が、tt 以下の点灯しているランプの個数に対応します。

Python
import math
def q(t):
return math.isqrt(t)
for _ in range(int(input())):
l, r = map(int, input().split())
print(q(r) - q(l - 1))

ABC483 F - Sum of Mod of Linear

NN 組の整数 (Ai,Bi)(A_i,B_i) が与えられます。各クエリの整数 xx に対し、

f(x)=∑i=1N((x+Ai) mod Bi)f(x) = \sum_{i=1}^{N} ((x+A_i) \bmod B_i)

を求める問題です(N≤5×105N \le 5 \times 10^5、Q≤2×105Q \le 2 \times 10^5、0≤Ai<Bi≤5×1050 \le A_i < B_i \le 5 \times 10^5、0≤x≤5×1050 \le x \le 5 \times 10^5)。

クエリごとに和を計算すると間に合わないので、X=5×105X=5\times 10^5 として、x=0,1,…,Xx=0,1,\dots,X の答えを先にすべて求めます。

11 組 (a,b)(a,b) に注目します。(x+a) mod b(x+a)\bmod b は、xx を 11 増やすたびに基本的には 11 増えます。ただし、x+ax+a が bb の倍数になるところでは b−1b-1 から 00 に戻るので、基本の増分 11 に加えて bb を引く必要があります。

この折り返しが起こる xx は

b−a, 2b−a, 3b−a,…b-a,\ 2b-a,\ 3b-a,\dots

です。全 NN 項を合わせると、毎回の基本の増分は NN になります。

そこで、ans[0] に f(0)=∑iAif(0)=\sum_i A_i を入れ、ans[1] 以降を NN で初期化します。各 (a,b)(a,b) について、b−ab-a から bb 刻みの位置で ans[x] から bb を引きます。最後に累積和を取ると、ans[x] が f(x)f(x) になります。

bb が小さい組は折り返しの回数が多いため、同じ (a,b)(a,b) を何度も処理すると時間がかかります。そこで、最初に同じ組の個数を数えます。(a,b)(a,b) が cc 個あるなら、初期値には acac を加え、折り返しの位置では bcbc を引けばよいです。

この工夫による計算量を考えます。bb を固定したとき、0≤a<b0 \le a < b なので、異なる組は高々 bb 種類です。また、11 組あたりの折り返しの回数は O(X/b+1)O(X/b+1) です。

境界を TT として分けると、b≤Tb \le T の組の処理は合計 O(XT+T2)O(XT+T^2)、b>Tb>T の組の処理は、組が高々 NN 個なので O(N(X/T+1))O(N(X/T+1)) です。TT を N\sqrt{N} 程度にすると、全体で O(XN+N)O(X\sqrt{N}+N) 回の処理に抑えられます。

コードで使う Counter の構築には O(Nlog⁡N)O(N\log N) かかるので、累積和とクエリへの回答も含めた計算量は O(Nlog⁡N+XN+Q)O(N\log N+X\sqrt{N}+Q)、空間計算量は O(N+X)O(N+X) です。答えは 32 bit 整数に収まらない場合があるので、64 bit 整数を使います。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
constexpr ll XMAX = 5e5;
LL(N);
VAL(AB, N, 2);
Counter<al<2>> cnt(AB);
vl ans(XMAX + 1, N);
ans[0] = 0;
for (auto [ab, c] : cnt) {
auto [a, b] = ab;
ans[0] += a * c;
rep(x, b - a, XMAX + 1, b) {
ans[x] -= b * c;
}
}
rep(x, 1, XMAX + 1) {
ans[x] += ans[x - 1];
}
LL(Q);
rep(Q) {
LL(x);
print(ans[x]);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの Counter で同じ組の個数を数えています。累積和を取る前の ans[x] (x≥1x \ge 1) は答えの差分、累積和を取った後は各 xx に対する答えです。

ABC483 E - Typo Pairs

英小文字からなる長さ MM の文字列が NN 個与えられます。異なる位置の個数(ハミング距離)が 22 以下である文字列の組 (i,j)(i,j) (i<ji<j) を数える問題です(N≤2×105N \le 2 \times 10^5、2≤M≤62 \le M \le 6)。

文字を隠して一致する組を数える

Section titled “文字を隠して一致する組を数える”

22 つの文字列で異なる位置が高々 22 つなら、その位置を隠すと同じ文字列になります。英小文字には登場しない @ を使い、各文字列から次の文字列を作って個数を数えます。

  • 元の文字列
  • 11 か所を @ に置き換えた文字列すべて
  • 22 か所を @ に置き換えた文字列すべて

同じ文字列が cc 個できたら、それを作る元の文字列の組は (c2)\binom{c}{2} 個です。ただし、隠す位置の選び方によって同じ組を何回も数えるので、補正が必要です。

ハミング距離ごとに重複を補正する

Section titled “ハミング距離ごとに重複を補正する”

@ が kk 個ある文字列について (c2)\binom{c}{2} を合計した値を TkT_k とします。ある文字列の組が各 TkT_k に何回数えられるかは、ハミング距離によって次のようになります。

ハミング距離T2T_2T1T_1T0T_0
22110000
11M−1M-11100
00(M2)\binom{M}{2}MM11

距離 22 なら、異なる 22 か所を隠す方法だけで一致します。距離 11 なら、異なる位置と、それ以外の M−1M-1 か所のいずれかを隠すことで T2T_2 に数えられます。距離 00 なら、どの位置を隠しても一致します。距離 33 以上の組は、どこを 22 か所隠しても一致しません。

まず T2T_2 では、距離 22 の組をちょうど 11 回数えています。距離 11 の組も 11 回にするため、(M−2)T1(M-2)T_1 を引きます。

この時点で距離 00 の組が数えられる回数は

(M2)−M(M−2)\binom{M}{2} - M(M-2)

なので、さらに (M−12)T0\binom{M-1}{2}T_0 を足すと、その回数も 11 になります。よって答えは

T2−(M−2)T1+(M−1)(M−2)2T0T_2 - (M-2)T_1 + \frac{(M-1)(M-2)}{2}T_0

です。コードでは、作った文字列に含まれる @ の個数に応じて、この係数を掛けています。

各文字列から O(M2)O(M^2) 個の文字列を作り、コピーやハッシュの計算に O(M)O(M) かかるので、ハッシュ表の操作が平均的に定数時間で行えるとすると、計算量は O(NM3)O(NM^3) です。M≤6M \le 6 なので十分間に合います。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VS(S, N);
std::unordered_map<str, ll> cnt;
for (str s : S) {
cnt[s]++;
rep(i, M) {
str t = s;
t[i] = '@';
cnt[t]++;
}
rep(i, M) rep(j, i + 1, M) {
str t = s;
t[i] = '@';
t[j] = '@';
cnt[t]++;
}
}
ll ans = 0;
for (const auto &[s, c] : cnt) {
ll k = count(s, '@');
ll pairs = c * (c - 1) / 2;
if (k == 2) {
ans += pairs;
} else if (k == 1) {
ans -= (M - 2) * pairs;
} else {
ans += (M - 1) * (M - 2) / 2 * pairs;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

ABC483 D - Glitchy Robot

数直線上の座標 00 にいるロボットが、順に A1,A2,…,ANA_1, A_2, \dots, A_N だけ移動します。移動を始める前に、AA の要素を高々 11 つ選んで符号を反転できます。

ロボットが一度以上通る整数座標の個数の最大値を求める問題です(N≤2×105N \le 2 \times 10^5)。

通る座標は累積和の最小値から最大値まで

Section titled “通る座標は累積和の最小値から最大値まで”

移動後の座標は累積和です。初期位置も含めて

P0=0,Pi=∑j=1iAjP_0 = 0, \qquad P_i = \sum_{j=1}^{i} A_j

とします。ロボットは連続的に移動するので、通る整数座標は min⁡Pi\min P_i から max⁡Pi\max P_i までのすべてです。よって、個数は

max⁡Pi−min⁡Pi+1\max P_i - \min P_i + 1

となります。

符号を反転する位置を全探索します。ただし、毎回累積和を作り直すと O(N2)O(N^2) かかるので、累積和の最小値・最大値を求められるセグメント木を使います。

各区間に、区間の総和 ss、空の接頭辞も含めた累積和の最小値 ll、最大値 rr を持たせます。空の接頭辞の和は 00 なので、初期位置も考慮できます。

左の区間の情報を (sL,lL,rL)(s_L, l_L, r_L)、右の区間の情報を (sR,lR,rR)(s_R, l_R, r_R) とすると、つなげた区間の情報は

s=sL+sR,l=min⁡(lL,sL+lR),r=max⁡(rL,sL+rR)\begin{aligned} s &= s_L + s_R, \\ l &= \min(l_L, s_L + l_R), \\ r &= \max(r_L, s_L + r_R) \end{aligned}

です。右の区間の累積和には、左の区間の総和 sLs_L が加わることを使っています。

11 要素 aa の情報は (a,min⁡(0,a),max⁡(0,a))(a, \min(0,a), \max(0,a)) です。この情報をセグメント木で管理すると、AiA_i を −Ai-A_i に変える操作を 11 点更新で行えます。

最初に反転しない場合の答えを求めます。その後、各位置について「符号を反転する」「全体の最大値と最小値から答えを更新する」「元に戻す」を行います。

各位置の更新は O(log⁡N)O(\log N)、全体の情報の取得は O(1)O(1) なので、計算量は O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/algebra/monoid.hpp"
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N);
VL(A, N);
SegTree<monoid::PrefixSumMinMax<ll>> seg(A);
ll ans = seg.all_prod().max - seg.all_prod().min + 1;
rep(i, N) {
seg.set(i, -A[i]);
chmax(ans, seg.all_prod().max - seg.all_prod().min + 1);
seg.set(i, A[i]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの PrefixSumMinMax と SegTree を使っています。all_prod() の min と max が、初期位置 00 を含む累積和の最小値・最大値です。

ABC483 C - Second Choice Election

候補者が NN 人、投票者が MM 人いて、投票者 ii の第一希望は AiA_i、第二希望は BiB_i です。候補者が 11 人辞退すると、その候補者を第一希望としていた人だけが第二希望に投票します。

各候補者が辞退した場合について、得票数が最大の候補者を求める問題です。同票なら番号が最小の候補者を選びます(N,M≤2×105N, M \le 2 \times 10^5)。

まず、全員が第一希望に投票したときの得票数を数えます。また、候補者 ii を第一希望としている人の第二希望を tmp[i] にまとめます。

候補者 ii が辞退するとき、移動するのは tmp[i] に対応する票だけです。それぞれについて ii の得票数を 11 減らし、第二希望の候補者の得票数を 11 増やします。この状態で当選者を求めたら、移動した票を元に戻します。

得票数の更新と当選者の取得には、候補者ごとの得票数に加え、「得票数の降順、同票なら番号の昇順」に並べた集合を管理すればよいです。更新時に古い組を削除して新しい組を追加すると、集合の先頭が当選者になります。

辞退した候補者の得票数は 00 になります。M≥1M \ge 1 なので必ず誰かが 11 票以上を得ており、辞退した候補者が選ばれることはありません。得票数が 00 の候補者を集合に入れなくても答えは変わりません。

各票は、その第一希望の候補者が辞退するときにだけ移動し、その後復元されます。全体で O(M)O(M) 回の更新を行うので、計算量は O(N+Mlog⁡N)O(N + M \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
LL(N, M);
VAL(AB, M, 2);
vvl tmp(N);
Counter<ll> cnt;
for (auto &[a, b] : AB) {
a--, b--;
tmp[a].push_back(b);
cnt.inc(a);
}
rep(i, N) {
for (ll j : tmp[i]) {
cnt.dec(i);
cnt.inc(j);
}
print(cnt.mode()->value + 1);
for (ll j : tmp[i]) {
cnt.dec(j);
cnt.inc(i);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの Counter を使っています。inc・dec で票を増減でき、mode() は個数が最大の値を、同数なら最小の値を返すので、当選者をそのまま求められます。候補者番号は内部では 0 始まりにしています。

ABC483 B - Flip Card Stack

11 から NN までの番号が書かれたカードが、上から番号順にすべて表向きで積まれています。「上から KiK_i 枚をひとまとめにして裏返す」という操作を QQ 回行い、最後のカードの順序と表裏を求める問題です(N,Q≤100N, Q \le 100)。

各カードについて、表向きなら番号をそのまま、裏向きなら番号にマイナスを付けて、上から順に出力します。

制約が小さいので、操作をそのままシミュレーションします。

リスト ans にカードを上から順に並べ、表裏を符号で表します。最初はすべて表向きなので、[1, 2, ..., N] で初期化します。

上から kk 枚をひとまとめにして裏返すと、その kk 枚の順序が逆になり、それぞれの表裏も反転します。なので、先頭の kk 要素を逆順に取り出し、符号を反転させればよいです。残りのカードを後ろにつなげると、操作後のリストになります。

例えば、[1, 2, 3, 4, 5] の上から 33 枚を裏返すと、[-3, -2, -1, 4, 5] になります。

各操作で長さ NN のリストを作り直すので、計算量は O(NQ)O(NQ) です。

Python
N, Q = map(int, input().split())
K = list(map(int, input().split()))
ans = list(range(1, N + 1))
for k in K:
ans = [-ans[k - i - 1] for i in range(k)] + ans[k:]
for a in ans:
print(a)

k - i - 1 は k−1,k−2,…,0k - 1, k - 2, \dots, 0 と変化するので、先頭の kk 要素を逆順に取り出せます。取り出した値に - を付けて表裏を反転し、操作の対象外である ans[k:] をつなげています。

ABC483 A - Double-Sided Printing

NN ページの資料を両面印刷します。コピー用紙 11 枚に 22 ページまで印刷できるとき、必要な用紙の枚数の最小値を求める問題です。

NN が偶数なら N/2N / 2 枚、奇数なら最後の 11 ページを印刷するためにもう 11 枚必要なので (N+1)/2(N + 1) / 2 枚です。

どちらの場合も、N+1N + 1 を 22 で割った商を求めれば答えになります。Python では整数除算の // を使います。

Python
print((int(input()) + 1) // 2)

SamCoding Round 10 (Div. 4) F - Ant Colony

nn 頂点の重み付きの木が与えられ、ii 本目の辺は頂点 uiu_i と viv_i を長さ wiw_i で結んでいます。22 頂点間の距離の最大値、つまり木の直径を求める問題です(n≤2×105n \le 2 \times 10^5、1≤wi≤1091 \le w_i \le 10^9)。

木の直径は、次の手順で求められます。

  1. 適当な頂点から最も遠い頂点 uu を求める。
  2. uu から最も遠い頂点 vv を求める。uu と vv の距離が直径。

辺の重みが非負なので、重み付きでもこの方法が使えます。各頂点からの距離は DFS や BFS で求められるので、計算量は O(n)O(n) です。答えは最大で 2×105×1092 \times 10^5 \times 10^9 程度になるので、64 ビット整数で計算します。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/graph/tree_util.hpp"
void solve() {
LL(N);
Tree<ll> tree(N);
tree.read(-1, true);
print(tree_diameter(tree));
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tree.read(-1, true) で、頂点番号を 0 始まりにずらし、重み付きの辺として読み込んでいます。tree_diameter は上の方法で直径の長さを求める関数です。

使用ライブラリ:cpp_include@cb82602

SamCoding Round 10 (Div. 4) E - Penguins on an Iceberg

n×mn \times m のグリッドがあり、各マスは氷(#)、水(.)、ペンギンが乗った氷(P)のどれかです。グリッドの外はすべて水です。毎晩、水と上下左右に隣り合う氷のマスがすべて同時に溶けて水になります。ペンギンが乗ったマスも普通の氷と同じように溶け、その晩にペンギンは水に落ちます。最後のペンギンが何晩目に水に落ちるかを求める問題です(n,m≤1000n, m \le 1000)。

11 晩目に溶けるのは、水またはグリッドの外と隣り合う氷のマスです。22 晩目に溶けるのは、まだ溶けていない氷のうち、11 晩目に溶けたマスと隣り合うマスです。以下同様に、tt 晩目に溶けるマスは t−1t - 1 晩目に溶けたマスから 11 歩で行けるマスになります。

なので、11 晩目に溶けるマスをすべて始点にした多始点 BFS をすれば、各マスが何晩目に溶けるかが求まります。答えは P のマスの値の最大値です。計算量は O(nm)O(nm) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/range.hpp"
void solve() {
LL(N, M);
VS(S, N);
Rect rect(N, M);
vvl dist(N, vl(M, -1));
deque<pl> que;
for (auto [i, j] : rect) {
if (S[i][j] == '.') {
dist[i][j] = 0;
continue;
}
bool f = false;
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (S[ni][nj] == '.')
f = true;
}
if (len(rect.neighbors4(i, j)) < 4) {
f = true;
}
if (f) {
que.push_back({i, j});
dist[i][j] = 1;
}
}
while (len(que)) {
auto [i, j] = que.front();
que.pop_front();
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (dist[ni][nj] == -1) {
dist[ni][nj] = dist[i][j] + 1;
que.push_back({ni, nj});
}
}
}
ll ans = 0;
for (auto [i, j] : rect) {
if (S[i][j] == 'P')
chmax(ans, dist[i][j]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dist[i][j] はマス (i,j)(i, j) が溶ける晩で、水のマスは 00 にしています。Rect は N×MN \times M のマスをまとめて扱う型で、for (auto [i, j] : rect) で全マスを回り、neighbors4(i, j) でグリッド内の上下左右のマスを返します。返ってきたマスが 44 つ未満なら、そのマスはグリッドの端にあり、外の水と隣り合っています。

使用ライブラリ:cpp_include@cb82602

SamCoding Round 10 (Div. 4) D - Bead Necklace

英小文字からなる文字列 ss が与えられます。ss が ppp…pppp\ldots p(pp を何度も繰り返した文字列)の先頭部分になるような、最も短い文字列 pp を求める問題です(∣s∣≤106|s| \le 10^6)。

∣s∣=n|s| = n とします。長さ ii の pp は ss の先頭 ii 文字に決まり、条件は「すべての j≥ij \ge i で sj=sj−is_j = s_{j-i}」、つまり ss の ii 文字目以降(0 始まり)が ss の先頭部分になっていることです。

これは Z algorithm で調べられます。Z algorithm は、各 ii について ss と ss の ii 文字目以降の最長共通接頭辞の長さ ziz_i を O(n)O(n) で求めます。条件は zi=n−iz_i = n - i と同じなので、これを満たす最小の i≥1i \ge 1 を探し、先頭 ii 文字を出力します。そのような ii がなければ、ss 全体が答えです。

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

C++
#include "shogo-library/base/all"
#include "shogo-library/string/string.hpp"
void solve() {
STR(S);
auto z = z_algorithm(S);
rep(i, 1, len(S)) {
if (z[i] == len(S) - i) {
print(S.substr(0, i));
return;
}
}
print(S);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

z_algorithm は上の ziz_i を求める関数です。

使用ライブラリ:cpp_include@cb82602

SamCoding Round 10 (Div. 4) C - Chakra Run

忍者が数直線上を地点 00 から地点 LL まで走ります。11 メートル走るごとにチャクラを 11 消費し、最初はチャクラを cc 持っています。道の途中に nn 軒のラーメン屋があり、ii 軒目は地点 pip_i にあって、立ち寄るとチャクラが aia_i 増えます(チャクラに上限はありません)。到着した時点でチャクラがちょうど 00 でも立ち寄れます。地点 LL に着くまでに立ち寄る回数の最小値を求め、たどり着けないなら −1-1 を出力する問題です(n≤2×105n \le 2 \times 10^5、L,c,ai≤109L, c, a_i \le 10^9)。

立ち寄った店の集合を決めると、走れる距離は cc にその店の aia_i の和を足したものです。どの店に立ち寄るかの順番は関係なく、「地点 xx にたどり着けるか」は、xx より手前で立ち寄った店だけで決まります。

そこで、前から順に店を見ていき、通り過ぎた店をいったん「候補」としてためておきます。次の店(または地点 LL)までたどり着けないときは、それまでの候補の中から aia_i が最大の店に「さかのぼって立ち寄ったことにする」のを、たどり着けるようになるまで繰り返します。候補が尽きたらたどり着けないので −1-1 です。

各時点で、立ち寄る回数を増やすなら、手前の店の中で aia_i が最大のものを選ぶのが最も遠くまで走れます。なので、この貪欲法で立ち寄る回数が最小になります。候補から最大値を取り出すのは優先度付きキュー(ヒープ)でできるので、計算量は O(nlog⁡n)O(n \log n) です。

Python
import heapq
N, L, C = map(int, input().split())
PA = [tuple(map(int, input().split())) for i in range(N)]
PA.append((L, 0))
hq = []
ans = 0
for p, a in PA:
while p > C:
if not hq:
break
C -= heapq.heappop(hq)
ans += 1
if p > C:
print(-1)
break
heapq.heappush(hq, -a)
else:
print(ans)

C は「今たどり着ける最も遠い地点」として使っています。末尾に地点 LL を a=0a = 0 の店として足し、ゴールも店と同じように判定しています。heapq は最小値を取り出すヒープなので、−ai-a_i を入れて最大値を取り出しています。

SamCoding Round 10 (Div. 4) B - Bookworm

Jasur は nn ページの本を読みます。11 日目は aa ページ読み、その後は毎日、前の日より kk ページ多く読みます(22 日目は a+ka + k ページ、33 日目は a+2ka + 2k ページ、…)。残りのページが予定より少ない日は、残りを読んで読み終えます。何日目に読み終えるかを求める問題です(1≤n,a≤10121 \le n, a \le 10^{12}、0≤k≤10120 \le k \le 10^{12})。

mm 日目までに読む予定のページ数の合計は

f(m)=ma+m(m−1)2kf(m) = ma + \frac{m(m - 1)}{2} k

です。f(m)≥nf(m) \ge n となる最小の mm が答えです。

ff は mm について単調増加なので、二分探索で求められます。a≥1a \ge 1 より f(n)≥nf(n) \ge n なので、答えは n≤1012n \le 10^{12} 以下です。探索の上限は 101510^{15} にしています。

Python
n, a, k = map(int, input().split())
ok = 10**15
ng = 0
while ok > ng + 1:
mid = (ok + ng) // 2
if n <= mid * a + mid * (mid - 1) // 2 * k:
ok = mid
else:
ng = mid
print(ok)

ok は f(m)≥nf(m) \ge n を満たす mm、ng は満たさない mm を保ちながら、区間を半分ずつ狭めています。

SamCoding Round 10 (Div. 4) A - Santa's Helpers

雪だるまを 1 つ作るには、大・中・小の雪玉を 1 つずつと、ボタンにする石炭が 33 個必要です。大きい雪玉が aa 個、中くらいの雪玉が bb 個、小さい雪玉が cc 個、石炭が dd 個あるとき、完成した雪だるまを最大で何個作れるかを求める問題です(0≤a,b,c,d≤1090 \le a, b, c, d \le 10^9)。雪玉の大きさを入れ替えて使うことはできません。

大きい雪玉だけを考えると最大 aa 個、中くらいなら bb 個、小さいなら cc 個、石炭なら ⌊d/3⌋\lfloor d / 3 \rfloor 個まで作れます。どの材料も足りている間は作れるので、答えはこれらの最小値 min⁡(a,b,c,⌊d/3⌋)\min(a, b, c, \lfloor d / 3 \rfloor) です。

Python
a, b, c, d = map(int, input().split())
print(min(a, b, c, d // 3))