コンテンツにスキップ

構築

タグ「構築」の記事 9 件

DOJ Beginner Contest 12 D - Yet Another Hamiltonian Path Problem

頂点 1,…,N1, \dots, N の有向グラフがあり、各頂点 ii に Ai∈{0,1}A_i \in \{0, 1\} が与えられます。Ai=0A_i = 0 なら、すべての j<ij < i に対して辺 i→ji \to j があります。Ai=1A_i = 1 なら、すべての j>ij > i に対して辺 i→ji \to j があります。すべての頂点をちょうど 1 回ずつ通る経路(ハミルトン路)を 1 つ出力する問題です。存在しなければ −1-1 を出力します(2≤N≤5×1052 \le N \le 5 \times 10^5、全テストケースの NN の総和は 5×1055 \times 10^5 以下)。

Ai=0A_i = 0 の頂点を「左向き」、Ai=1A_i = 1 の頂点を「右向き」と呼びます。左向きの頂点どうしは番号の大きい順にたどれて、右向きの頂点どうしは番号の小さい順にたどれます。あとは、2 つの列をつなげられるかどうかです。

  • AN=0A_N = 0 のとき:右向きの頂点を小さい順にたどり、続けて左向きの頂点を大きい順にたどります。つなぎ目では、最後の右向きの頂点から左向きの頂点 NN に進みます。NN はどの頂点より番号が大きいので、この辺はあります。
  • A1=1A_1 = 1 のとき:左向きの頂点を大きい順にたどり、続けて右向きの頂点を小さい順にたどります。つなぎ目では、最後の左向きの頂点から右向きの頂点 11 に進みます。11 はどの頂点より番号が小さいので、この辺はあります。
  • A1=0A_1 = 0 かつ AN=1A_N = 1 のとき:頂点 11 は左向きなのに自分より小さい頂点がなく、頂点 NN は右向きなのに自分より大きい頂点がありません。どちらも出る辺がないので、経路の終点にしか置けません。終点は 1 つなので、ハミルトン路は存在しません。

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

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
if A[0] == 0 and A[-1] == 1:
print(-1)
continue
ans = []
if A[-1] == 0:
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
else:
assert A[0] == 1
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
print(*ans)

A は 0 始まりなので、頂点の番号は i + 1 です。最初の if で −1-1 の場合を除いているので、else に来たときは A1=1A_1 = 1 です。

ShareOJ Programming Contest vol.1 C - Add to Multiples

はじめすべて 00 の長さ NN の数列 AA があります。「kk と整数 xx を選び、kk の倍数番目の要素すべてに xx を足す」という操作を NN 回以下行って、A=(X1,…,XN)A = (X_1, \dots, X_N) にする操作列を 1 つ答える問題です。ただし ∣x∣≤1018|x| \le 10^{18} でなければなりません。

テストケースは TT 個あり、NN の総和は 3×1053 \times 10^5 以下、∣Xi∣≤109|X_i| \le 10^9 です。

kk を選ぶ操作で変わるのは Ak,A2k,…A_k, A_{2k}, \dots なので、kk より小さい番号の要素は変わりません。そこで、i=1,2,…,Ni = 1, 2, \dots, N の順に AiA_i を合わせていきます。

ii を見る時点で、AiA_i を変える操作は ii の約数 k<ik < i を選んだものだけで、それらはすでに済んでいます。したがって、今の AiA_i と XiX_i の差 x=Xi−Aix = X_i - A_i を求めて、k=ik = i で xx を足せば Ai=XiA_i = X_i になります。このあとの操作では AiA_i は変わりません。

各 ii について操作は高々 1 回なので、操作は NN 回以下です。

ii のときに足す値を xix_i とすると、Xi=∑d∣ixdX_i = \sum_{d \mid i} x_d が成り立ちます。これをメビウスの反転公式で解くと、xi=∑d∣iμ(i/d)Xdx_i = \sum_{d \mid i} \mu(i / d) X_d となります。μ\mu の値は −1,0,1-1, 0, 1 のどれかなので、∣xi∣|x_i| は (ii の約数の個数)×109\times 10^9 以下です。3×1053 \times 10^5 以下の整数の約数は多くても 180180 個なので、∣xi∣≤1018|x_i| \le 10^{18} を十分に満たします。

k=ik = i で足すときに書き換える要素は ⌊N/i⌋\lfloor N / i \rfloor 個です。合計は ∑i=1NN/i=O(Nlog⁡N)\sum_{i=1}^{N} N / i = O(N \log N) になります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(1, N + 1):
k = A[i - 1]
if k == 0:
continue
ans.append((i, k))
for j in range(1, N // i + 1):
A[i * j - 1] -= k
print(len(ans))
for i, j in ans:
print(i, j)

A を「あと足す必要がある量」として持ち、操作のたびにそこから引いています。k は足す値 xx で、00 のときは操作を省いています。

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 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 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 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])

Codeforces Round 1125 (Div. 3) A - In Search of Convenience

整数 x0,y0,Rx_0, y_0, R が与えられます(−10≤x0,y0≤10-10 \le x_0, y_0 \le 10、1≤R≤251 \le R \le 25)。点 (x0,y0)(x_0, y_0) からの距離がちょうど RR である格子点(座標が整数の点)を 1 つ出力してください。答えが複数あるときは、どれを出力してもかまいません。テストケースは t≤104t \le 10^4 個です。

(x0,y0)(x_0, y_0) から xx 軸の方向にちょうど RR だけずらした点 (x0−R,y0)(x_0 - R, y_0) を出力すればよいです。

RR は整数なので、この点も格子点です。距離は

(x0−(x0−R))2+(y0−y0)2=R2=R\sqrt{(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2} = \sqrt{R^2} = R

となり、ちょうど RR です。

問題文の例のように (5−2)2+(5−1)2=52(5 - 2)^2 + (5 - 1)^2 = 5^2 となる点を探す必要はありません。軸に沿ってずらすだけで条件を満たせます。(x0+R,y0)(x_0 + R, y_0) や (x0,y0±R)(x_0, y_0 \pm R) でもかまいません。

Python
for _ in range(int(input())):
x, y, r = map(int, input().split())
print(x - r, y)

SamCoding Round 7 (Div. 2) G - Chocolate Factory

D と M からなる長さ 2n−12n - 1 の文字列 ss が与えられます。長さ nn 以上の区間で、M をちょうど xx 個含むものが nn 個以上あるような xx を 1 つ求める問題です(n≤106n \le 10^6)。そのような xx は必ず存在します。

問題文では「nn 人の検査員がそれぞれ異なる区間を担当し、全員が同じ個数の M を検査する」という設定になっています。

たとえば n=3n = 3、s=s = MDMDM のとき、M を 22 個含む長さ 33 以上の区間は [1,3],[3,5],[1,4],[2,5][1, 3], [3, 5], [1, 4], [2, 5] の 44 個あるので、x=2x = 2 が答えです。

長さ nn 以上の区間はおよそ n22\frac{n^2}{2} 個あるので、すべて数えることはできません。そこで、条件を満たすと保証できる xx を 1 つ見つけます。

長さ nn の区間に含まれる M の個数の最大値を xx とすると、これが答えになります。

最大を達成する区間を [p,p+n−1][p, p + n - 1] とします。区間を 1 文字伸ばしたり縮めたりしても、M の個数は 00 か 11 しか変わりません。そのため、xx 以下の区間から xx 以上の区間まで 1 文字ずつ動かせば、途中に必ずちょうど xx の区間があります。

これを使って、ちょうど xx 個の区間を nn 個見つけます。

  • 左端 l<pl < p のそれぞれ(p−1p - 1 個): 右端を l+n−1l + n - 1 から p+n−1p + n - 1 まで伸ばしていきます。最初の [l,l+n−1][l, l + n - 1] は長さ nn なので M は xx 個以下、最後の [l,p+n−1][l, p + n - 1] は最大の区間を含むので xx 個以上です。途中に M がちょうど xx 個の区間があります。
  • 右端 r≥p+n−1r \ge p + n - 1 のそれぞれ(n−p+1n - p + 1 個): 左端を pp から r−n+1r - n + 1 まで縮めていきます。最初の [p,r][p, r] は最大の区間を含むので xx 個以上、最後の [r−n+1,r][r - n + 1, r] は長さ nn なので xx 個以下です。こちらも途中にちょうど xx 個の区間があります。

前者の区間は左端が pp より前、後者は左端が pp 以降なので、すべて異なります。どれも長さは nn 以上で、個数は (p−1)+(n−p+1)=n(p - 1) + (n - p + 1) = n です。

長さ nn の区間は nn 個あり、スライディングウィンドウで M の個数を更新しながら最大値を求めれば O(n)O(n) です。

Python
N = int(input())
S = input()
ans = t = S[:N].count("M")
for i in range(N - 1):
t -= S[i] == "M"
t += S[i + N] == "M"
ans = max(ans, t)
print(ans)

t が今の区間に含まれる M の個数です。区間を 1 つ右にずらすとき、左端から外れる S[i] と右端に入る S[i + N] の分だけ t を更新しています。

Blitz Round #25 A - Sum vs MEX

11 から nn の順列 pp のうち、すべての ii (1≤i≤n1 \le i \le n) について

∑j=1ipj が MEX(p1,…,pi) で割り切れる\sum_{j=1}^{i} p_j \text{ が } \mathrm{MEX}(p_1, \ldots, p_i) \text{ で割り切れる}

を満たすものを 1 つ構築するか、存在しないことを判定する問題です。ここでの MEX は「含まれない最小の正の整数」です。

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5、テストケースの nn の総和は 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

i=ni = n のとき、p1,…,pnp_1, \ldots, p_n には 11 から nn がすべて含まれるので MEX=n+1\mathrm{MEX} = n + 1、総和は n(n+1)2\frac{n(n+1)}{2} です。

n(n+1)2÷(n+1)=n2\frac{n(n+1)}{2} \div (n + 1) = \frac{n}{2}

なので、割り切れるのは nn が偶数のときだけです。よって nn が奇数なら答えは NO です。

nn が偶数のとき:11 を最後に置く

Section titled “nnn が偶数のとき:111 を最後に置く”

11 を最後に置くと、i<ni < n では p1,…,pip_1, \ldots, p_i に 11 が含まれないので MEX=1\mathrm{MEX} = 1 となり、条件は常に満たされます。

i=ni = n のときは上で見たとおり、nn が偶数なら割り切れます。

したがって、たとえば p=(2,3,…,n,1)p = (2, 3, \ldots, n, 1) が条件を満たします。

Python
for _ in range(int(input())):
N = int(input())
if N & 1:
print("NO")
else:
ans = list(range(2, N + 1)) + [1]
print("YES")
print(*ans)