コンテンツにスキップ

ソート

タグ「ソート」の記事 12 件

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)

ABC482 C - Band Count

H×WH \times W のグリッドに NN 個の駒が置かれていて、ii 番目の駒はマス (Ri,Ci)(R_i, C_i) にあります。次の 22 種類のクエリ QQ 個に答える問題です(H,W≤109H, W \le 10^9、N,Q≤3×105N, Q \le 3 \times 10^5)。

  • 1 u d:uu 行目から dd 行目までにある駒の個数を出力する。
  • 2 l r:ll 列目から rr 列目までにある駒の個数を出力する。

行のクエリでは駒の列は関係なく、「u≤Ri≤du \le R_i \le d を満たす ii の個数」を答えればよいです。列のクエリも同様に「l≤Ci≤rl \le C_i \le r を満たす ii の個数」です。

H,WH, W が大きいので行ごとの個数の配列は作れませんが、RR と CC をそれぞれソートしておけば、二分探索で数えられます。ソートした RR で、dd 以下の個数から uu 未満の個数を引いたものが答えです。

計算量は O((N+Q)log⁡N)O((N + Q) \log N) です。

Python
import bisect
H, W, N, Q = map(int, input().split())
R = []
C = []
for _ in range(N):
r, c = map(int, input().split())
R.append(r)
C.append(c)
R.sort()
C.sort()
for _ in range(Q):
t, x, y = map(int, input().split())
l = R if t == 1 else C
print(bisect.bisect_right(l, y) - bisect.bisect_left(l, x))

bisect_right(l, y) は l の中の yy 以下の要素の個数、bisect_left(l, x) は xx 未満の要素の個数です。

SamCoding Round 9 (Div. 4) D - Printer Queue

nn 人の生徒が 1 台のプリンターで書類を印刷します。生徒 ii の書類の印刷には tit_i 秒かかります。プリンターは一度に 1 つの書類しか印刷できず、時刻 00 から休みなく順に印刷します。各生徒の待ち時間を「時刻 00 から自分の書類が印刷し終わるまでの時間」とするとき、印刷する順番をうまく決めて、待ち時間の合計の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤ti≤1061 \le t_i \le 10^6)。

印刷時間の短い順に印刷するのが最適です。

jj 番目に印刷する書類の印刷時間を sjs_j とすると、jj 番目の生徒の待ち時間は s1+s2+⋯+sjs_1 + s_2 + \dots + s_j です。待ち時間の合計では、sjs_j は jj 番目以降の n−j+1n - j + 1 人の待ち時間に含まれるので、

∑j=1n(n−j+1) sj\sum_{j=1}^{n} (n - j + 1) \, s_j

になります。前に印刷するものほど大きな係数が掛かるので、短いものを前に置けばよいです。

実際、隣り合う sj>sj+1s_j > s_{j+1} があれば、2 つを入れ替えると合計は sj−sj+1>0s_j - s_{j+1} > 0 だけ減ります。そのため、最適な順番では印刷時間が短い順に並んでいます。

あとは tt をソートして累積和をとり、その合計を出力すれば答えです。O(nlog⁡n)O(n \log n) です。

Python
from itertools import accumulate
input()
print(sum(accumulate(sorted(list(map(int, input().split()))))))

accumulate でソート後の累積和、つまり各生徒の待ち時間を求め、その合計を出力しています。

repovive starter round 10 C - Museum Records

nn 人が博物館に 1 回ずつ入って出ました。2n2n 回の入退場の時刻はすべて異なります。各人 ii について、

  • aia_i:ii が入る前に出ていた人数
  • bib_i:ii が出たあとに入ってきた人数

が記録されています。すべての記録が正しくなる入退場の順番があるか判定する問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤ai,bi<n0 \le a_i, b_i < n)。

aia_i は、入るのが遅い人ほど大きいか等しいです。よって、入る順番は aia_i の昇順です。aia_i が等しい人どうしの間では誰も出ていないので、その人たちの入る順番を入れ替えても、ほかの人の a,ba, b は変わりません。

kk 人目が入ってから k+1k + 1 人目が入るまでの間を「すき間 kk」と呼びます(すき間 nn は最後の人が入ったあと)。bib_i 人があとから入ってくるので、人 ii はすき間 n−bin - b_i で出ます。同じすき間で出る人どうしの順番は、記録に影響しません。

こうして入退場の順番は(記録に影響しない入れ替えを除いて)決まるので、次の 2 つを満たすか調べれば十分です。人 ii が kik_i 番目に入るとします。

  1. 入ってから出る:ki≤n−bik_i \le n - b_i。
  2. aia_i が正しい:aia_i は、n−bj≤ki−1n - b_j \le k_i - 1 である人 jj の人数に等しい。

aia_i が等しい人どうしの順番は 2. に影響しないので、1. を満たしやすい順にします。それは bib_i の大きい人(早く出る人)を先にする順です。

aia_i の昇順、同じなら bib_i の降順に並べます。0-indexed で ii 番目の人は k=i+1k = i + 1 番目に入るので、1. は i+1≤n−bi + 1 \le n - b です。

また、2. の人数は、すき間ごとに出る人数を数えて累積和をとれば求まります。ckc_k を「すき間 kk 以下で出る人数」とすると、2. は a=cia = c_i です。

全員がこの 2 つを満たせば Yes、そうでなければ No です。計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n = int(input())
ab = [tuple(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda x: (x[0], -x[1]))
c = [0] * (n + 1)
for a, b in ab:
c[n - b] += 1
for i in range(n):
c[i + 1] += c[i]
for i, (a, b) in enumerate(ab):
if i + 1 > n - b or a != c[i]:
print("No")
exit(0)
print("Yes")

repovive starter round 10 B - Rise to the Occasion

長さ nn の整数列 aa と正の整数 x,yx, y が与えられます。カウンタ tt は最初 00 です。aa を好きな順に並べ替えてから順に見ていき、値 vv について t≤vt \le v なら tt を xx 増やし、そうでなければ tt を yy 減らします。最後の tt の最大値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤x,y≤1091 \le x, y \le 10^9、−109≤ai≤109-10^9 \le a_i \le 10^9)。

aa を昇順に並べてシミュレーションした結果が答えです。

kk 個の値を見た時点の tt は、増やした回数を pp として px−(k−p)y=p(x+y)−kypx - (k - p)y = p(x + y) - ky です。よって、同じ個数を見た時点の 2 つのカウンタの値 t≤t′t \le t' の差は x+yx + y の倍数です。

t≤t′t \le t' のとき、同じ値 vv を見たあとも大小は逆転しません。両方が増える場合と両方が減る場合は明らかです。t≤v<t′t \le v < t' で tt だけが増える場合は、t′≥t+(x+y)t' \ge t + (x + y) なので t′−y≥t+xt' - y \ge t + x です(t>v≥t′t > v \ge t' となることはありません)。

したがって、途中のある時点でカウンタが大きいほうが、残りの並びが同じなら最後のカウンタも大きいか等しいです。

並びの中で u>vu > v が u,vu, v の順に隣り合っているとき、v,uv, u の順に入れ替えても、2 つを見たあとのカウンタは小さくならないことを示します。2 つを見る前のカウンタを tt とします。

  • t≤vt \le v のとき:どちらの順でも 1 つ目で増えて t+xt + x になります。2 つ目で増えるのは、元の順では t+x≤vt + x \le v のとき、入れ替えると t+x≤ut + x \le u のときで、後者のほうが条件が弱いです。
  • v<t≤uv < t \le u のとき:元の順では uu で増えて vv で減り、入れ替えると vv で減って uu で増えます(t−y<t≤ut - y < t \le u なので)。どちらも t+x−yt + x - y です。
  • u<tu < t のとき:どちらの順でも 1 つ目で減って t−yt - y になります。2 つ目で増えるのは、元の順では t−y≤vt - y \le v のとき、入れ替えると t−y≤ut - y \le u のときで、後者のほうが条件が弱いです。

どの場合も、入れ替えたほうが増える回数が多いか等しいので、カウンタも大きいか等しいです。上で示したことから、最後のカウンタも小さくなりません。この入れ替えを繰り返すと昇順になるので、昇順が最適です。

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

Python
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
t = 0
for v in a:
if t > v:
t -= y
else:
t += x
print(t)

DOJ Beginner Contest 11 F - Laboratory

NN 種類の微生物があり、ii 番の微生物の xx 日目の個体数は Ai+BixA_i + B_i x です。BiB_i を成長係数とよびます。

xx 日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。

  • 成長係数の小さい順
  • xx 日目の個体数の少ない順

どちらも、値が同じなら番号の小さい順に並べます。KK 種類以上選べる最も早い日 x≥0x \ge 0 を求める問題です。存在しなければ -1 を出力します。

1≤K≤N≤1051 \le K \le N \le 10^5、1≤Ai,Bi≤1091 \le A_i, B_i \le 10^9 です。

固定した日に選べる最大の種類数

Section titled “固定した日に選べる最大の種類数”

微生物を (Bi,i)(B_i, i) の昇順に並べておきます。選んだ微生物の並びがこの順で、(Ai+Bix,i)(A_i + B_i x, i) も昇順になっていれば条件を満たします。

つまり、(Bi,i)(B_i, i) の順に並べた列で、(Ai+Bix,i)(A_i + B_i x, i) の最長狭義増加部分列(LIS)の長さが、xx 日目に選べる最大の種類数です。LIS の長さは O(Nlog⁡N)O(N \log N) で求まります。

xx 日目に選べる組は、x+1x + 1 日目にも選べます。

(Bp,p)<(Bq,q)(B_p, p) < (B_q, q) の 2 つが xx 日目に条件を満たしているとします。1 日たつと、個体数の差 (Aq+Bqx)−(Ap+Bpx)(A_q + B_q x) - (A_p + B_p x) は Bq−Bp≥0B_q - B_p \ge 0 だけ増えます。Bp<BqB_p < B_q なら差が増えるので順序は保たれ、Bp=BqB_p = B_q なら差が変わらないので順序も変わりません。

よって、選べる最大の種類数は xx について広義単調増加です。KK 種類以上選べる最小の xx を二分探索で求めます。

問題文にあるとおり、答えが存在すれば 10910^9 以下です。x=109+1x = 10^9 + 1 で KK 種類選べなければ -1 を出力し、選べれば [0,109+1][0, 10^9 + 1] で二分探索します。

全体で O(Nlog⁡Nlog⁡max⁡)O(N \log N \log \max) です。

Python
from operator import itemgetter
from bisect import bisect_left
for _ in range(int(input())):
N, K = map(int, input().split())
ABi = [tuple(map(int, input().split())) + (i,) for i in range(N)]
ABi.sort(key=itemgetter(1))
def q(x):
dp = [(2 * 10**18, 10**18)] * (N + 1)
for a, b, i in ABi:
dp[bisect_left(dp, (a + b * x, i))] = (a + b * x, i)
for i in range(N + 1):
if dp[i][0] >= 2 * 10**18:
return i
assert False
ok = 10**9 + 1
ng = -1
if q(ok) < K:
print(-1)
continue
while ok > ng + 1:
mid = (ok + ng) // 2
if q(mid) >= K:
ok = mid
else:
ng = mid
print(ok)

sort は安定なので、BiB_i だけをキーにしても、BiB_i が等しいものは番号順に並びます。q(x) は (Ai+Bix,i)(A_i + B_i x, i) の LIS の長さを返します。dp[k] は長さ k+1k + 1 の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。

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 は、どうやっても作れない組数です。

牛客小白月赛138 C - AND and OR

長さ nn の非負整数列 a1,…,ana_1, \dots, a_n と非負整数 kk が与えられます(2≤n≤2×1052 \le n \le 2 \times 10^5、0≤ai,k≤1090 \le a_i, k \le 10^9)。

(aiandaj)+(aioraj)=k(a_i \mathbin{\mathrm{and}} a_j) + (a_i \mathbin{\mathrm{or}} a_j) = k

を満たす 1≤i<j≤n1 \le i < j \le n があれば 1 つ出力し、なければ −1-1 を出力してください(nn の総和 ≤2×105\le 2 \times 10^5)。

実は、どんな非負整数 a,ba, b についても

(aandb)+(aorb)=a+b(a \mathbin{\mathrm{and}} b) + (a \mathbin{\mathrm{or}} b) = a + b

が成り立ちます。ビットごとに確かめると分かります。各ビットについて、aa と bb のそのビットの組み合わせは次の 3 通りです。

a,ba, b のビットANDORAND + ORa+ba + b
両方 0000000000
片方だけ 1100111111
両方 1111112222

どのビットでも AND と OR の寄与の和が aa と bb の寄与の和に一致するので、全体でも等しくなります。

したがって、問題は「ai+aj=ka_i + a_j = k となる i<ji < j を 1 つ見つけよ」という、よくある問題に言い換えられます。

(ai,i)(a_i, i) の組を値でソートしておきます。各要素 aia_i について、相手の値 k−aik - a_i が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。

k−ai=aik - a_i = a_i のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。

計算量はソートと二分探索で O(nlog⁡n)O(n \log n) です。

Python
import bisect
for _ in range(int(input())):
N, K = map(int,input().split())
A = list(map(int,input().split()))
Ai = [(A[i],i) for i in range(N)]
Ai.sort()
for i in range(N):
j = bisect.bisect_left(Ai,(K-Ai[i][0],-1))
if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]:
print(*sorted((Ai[i][1]+1,Ai[j][1]+1)))
break
else:
print(-1)

Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が k−aik - a_i 以上である最初の位置が求まります。添字は 00 以上なので、第 2 要素に −1-1 を入れておけば、値が k−aik - a_i の組より必ず前に来ます。出力は i<ji < j の順にする必要があるので、元の添字をソートしてから出力しています。

Codeforces Round 1125 (Div. 3) C - Unrequited Love

長さ nn の整数列 a1,…,ana_1, \dots, a_n があります(6≤n≤2⋅1056 \le n \le 2 \cdot 10^5、∣ai∣≤104|a_i| \le 10^4)。1≤x≤n−41 \le x \le n - 4 に対して、鍵 x,x+2,x+4x, x + 2, x + 4 の組を「トライアド xx」と呼び、その値を ax+ax+2−ax+4a_x + a_{x+2} - a_{x+4} とします。

鍵を共有せず、値が等しい 2 つのトライアドの組(順序は区別しない)の個数を求めてください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

vx=ax+ax+2−ax+4v_x = a_x + a_{x+2} - a_{x+4} とおきます。

鍵を共有するのはどんなときか

Section titled “鍵を共有するのはどんなときか”

トライアド x<yx < y の鍵は {x,x+2,x+4}\{x, x+2, x+4\} と {y,y+2,y+4}\{y, y+2, y+4\} です。y−xy - x が奇数なら偶奇が違うので共有しません。y−x≥6y - x \ge 6 なら離れすぎていて共有しません。したがって、鍵を共有するのは y−x=2y - x = 2 または y−x=4y - x = 4 のときだけです。

鍵の共有を気にせずに、値が等しいペアをすべて数えてから、鍵を共有するペアを引きます。

  • 値が等しいペアの総数:vv をソートすると、同じ値が連続して並びます。同じ値が kk 個あれば、そこから (k2)=k(k−1)2\binom{k}{2} = \frac{k(k-1)}{2} 個のペアが作れます。
  • 鍵を共有するペア:vx=vx+2v_x = v_{x+2} となる xx の個数と、vx=vx+4v_x = v_{x+4} となる xx の個数を足したものです。

答えは前者から後者を引いたものです。計算量はソートがあるので O(nlog⁡n)O(n \log n) です。

補足:辞書で数えるとハックされる

Section titled “補足:辞書で数えるとハックされる”

vyv_y と等しい vxv_x(x<yx < y)の個数を、Counter などの辞書で数えながら左から見ていく方法も考えられます。ただ、Python でこの方法を提出したところ、PyPy でも TLE になりました(テスト 7)。

テスト 7 は、奇数番目の要素がすべて 00 の入力です。そのため奇数位置の vxv_x はすべて 00 になり、辞書のキー 00 が約 10510^5 回検索されます。一方、偶数位置の vxv_x は、キー 00 を検索するときにたどる位置をほかのキーで埋め尽くすように作られていると考えられます。Python の整数のハッシュ値は値そのものなので、キーが予測できればこのような入力を作れてしまいます。その結果、検索のたびに長い列をたどることになって TLE します。

対策としては、次のどちらかがあります。

  • 起動時に決めた乱数とキーの XOR をとってから辞書に入れる(ハックする側が衝突を狙えなくなる)
  • 上の解法のように、ハッシュを使わずにソートで数える

ここでは後者を採用しています。C++ の std::map は平衡二分木でハッシュを使わないので、辞書で数える方法でも問題ありません。

Python
from itertools import groupby
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = N - 4
v = [A[i] + A[i + 2] - A[i + 4] for i in range(M)]
ans = 0
for _, g in groupby(sorted(v)):
k = len(list(g))
ans += k * (k - 1) // 2
for i in range(M):
if i + 2 < M and v[i] == v[i + 2]:
ans -= 1
if i + 4 < M and v[i] == v[i + 4]:
ans -= 1
print(ans)

groupby(sorted(v)) で同じ値の並びごとに個数 k を数え、(k2)\binom{k}{2} を足しています。そのあと、位置の差が 22 と 44 で値が等しいものを引いています。

C++(std::map で数える)
#include "sh-library/base/all"
void solve() {
LL(N);
VL(A, N);
mll c;
ll ans = 0;
deque<ll> d;
rep(i, N - 4) {
ll t = A[i] + A[i + 2] - A[i + 4];
ans += c[t];
if (d.size() >= 1 && d[d.size() - 1] == t) {
ans++;
}
if (d.size() >= 3 && d[d.size() - 3] == t) {
ans++;
}
while (d.size() >= 4) {
c[d.front()]++;
d.pop_front();
}
d.push_back(t);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

左から順に見て、トライアド yy と組になる x<yx < y を数えています。

  • y−x≥5y - x \ge 5 の分は、c(値ごとの個数を持つ std::map)で数えます。
  • y−xy - x が 11 と 33 の分は、直近 4 個の値を持つ d で個別に確かめます。

y−xy - x が 22 と 44 のペアは鍵を共有するので数えません。

使用ライブラリ:cpp_include@6e9980e

ABC477 B - Standing Outliers

数直線上に NN 人がいて、人 ii は座標 XiX_i にいます。自分以外のどの人との距離も DD 以上である人の番号を、昇順にすべて出力する問題です(N≤100N \le 100)。

N≤100N \le 100 なので、各人 ii について他の全員との距離 ∣Xi−Xj∣|X_i - X_j| を調べれば O(N2)O(N^2) で間に合います。

ソートを使うと O(Nlog⁡N)O(N \log N) にもなります。座標を昇順に並べると、ある人に最も近い人は並びで両隣のどちらかです。なので、両隣との差がどちらも DD 以上かどうかだけ調べれば十分です。同じ座標の人がいる場合は差が 0<D0 < D になるので、そのまま正しく判定できます。

Python
N, D = map(int, input().split())
X = list(map(int, input().split()))
ans = [i + 1 for i in range(N) if all(abs(X[i] - X[j]) >= D for j in range(N) if i != j)]
print(len(ans))
print(*ans)

全員の組を調べる O(N2)O(N^2) の解法です。

Uiua
≡&p+1⊚&p/+.⍜⍆(⬚1×⊂1.≥⊣:⧈-)∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を読み、それぞれ空白区切りの数値の配列にします。

⍜⍆(…) は、XX をソートしてから中の処理をし、結果を元の順番に戻します。中の処理は次のとおりです。

  1. ⧈- で隣り合う座標の差を求めます。
  2. ⊣: で 1 行目の [N,D][N, D] から DD を取り出し、≥ で各差が DD 以上かどうかの 0/1 の列にします。この列の kk 番目は、ソート後の kk 番目と k+1k+1 番目の人の間が離れているかを表します。
  3. ⊂1. で、この列を複製して片方の先頭に 11 を付けます。⬚1× で、もう片方の末尾を 11 で埋めて掛け合わせます。これで各人について「左隣とも右隣とも DD 以上離れているか」が求まります。両端の人は、いない側の隣を 11(離れている)として扱っています。

あとは /+. で人数を数えて &p で出力し、⊚ で 1 になっている位置を取り出して +1 で 1 始まりの番号にし、≡&p で出力しています。番号は 1 行に 1 つずつ出力しますが、AtCoder のジャッジは空白と改行の違いを区別しないので、これで通ります。

ABC478 D - Range Set Insertion Query

はじめ空の集合 S1,…,SNS_1, \ldots, S_N に対して、「SL,…,SRS_L, \ldots, S_R に値 XX を追加する」という操作を QQ 回行います。最後に各 SiS_i の要素数を求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

SiS_i の要素数は「ii を含む区間が 1 つ以上ある値 XX の個数」です。同じ XX の区間が重なっていると、単純にいもす法で数えたときに XX を 2 回以上数えてしまうのが問題です。

そこで、値 XX ごとに区間をまとめ、重なっている区間を併合して互いに重ならない区間の集まりにしてから、いもす法で +1+1 します。こうすれば、各位置で同じ XX が数えられるのは高々 1 回です。

区間の併合は、区間を左端でソートして前から見ていき、今の区間の左端が直前にまとめた区間の右端以下なら右端を伸ばし、そうでなければ新しい区間として追加すればできます。

XX でソートしてから同じ XX ごとに処理し、計算量はソートの O(Qlog⁡Q)O(Q \log Q) といもす法の O(N)O(N) を合わせて O(N+Qlog⁡Q)O(N + Q \log Q) です。

コードでは区間を半開区間 [L−1,R)[L - 1, R) で持っているので、隣り合っているだけの区間(右端 == 次の左端)も併合されますが、和集合は変わらないので問題ありません。

Python
from operator import itemgetter
N, Q = map(int, input().split())
LRX = [tuple(map(int, input().split())) for i in range(Q)]
LRX.sort(key=itemgetter(2))
imos = [0] * (N + 1)
i = 0
while i < Q:
x = LRX[i][2]
tmp = [(LRX[i][0] - 1, LRX[i][1])]
i += 1
while i < Q and LRX[i][2] == x:
tmp.append((LRX[i][0] - 1, LRX[i][1]))
i += 1
tmp.sort()
l = []
for a, b in tmp:
if l and l[-1][1] >= a:
l[-1] = (l[-1][0], max(l[-1][1], b))
else:
l.append((a, b))
for a, b in l:
imos[a] += 1
imos[b] -= 1
for i in range(N):
imos[i + 1] += imos[i]
print(*imos[:N])

ABC478 C - Sort Subarray

長さ NN の整数列 AA の、長さ KK の連続部分列をちょうど 1 回だけ選んで昇順にソートします。その結果 AA 全体を昇順にできるかを判定する問題です(1≤K<N≤2×1051 \le K < N \le 2 \times 10^5)。

AA を昇順にソートした列を SS とします。区間 [i,i+K)[i, i + K) をソートして AA 全体が SS になるのは

  • 区間より前が SS と一致している(Aj=SjA_j = S_j, j<ij < i)
  • 区間より後ろが SS と一致している(Aj=SjA_j = S_j, j≥i+Kj \ge i + K)

のときです。このとき、区間の中の値の集まりも SS の対応する部分と一致するので、区間をソートすれば SS になります。逆に、区間の外は操作で変わらないので、この 2 つは必要です。

そこで

  • LiL_i = 先頭から ii 個がすべて SS と一致しているか
  • RiR_i = 位置 ii 以降がすべて SS と一致しているか

を前と後ろから求めておき、LiL_i かつ Ri+KR_{i+K} となる ii があるかを調べます。計算量はソートの O(Nlog⁡N)O(N \log N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = sorted(A)
l = [True]
for i in range(N):
l.append(l[-1] and A[i] == s[i])
r = [True]
for i in reversed(range(N)):
r.append(r[-1] and A[i] == s[i])
r.reverse()
if any(l[i] and r[i + K] for i in range(N - K + 1)):
print("Yes")
else:
print("No")
Uiua
&p⨬"Yes""No">⊣:/+>0×⍜⇌\+⟜\+≠⍆.∩(⊜⋕⊸≠@ &sc)

≠⍆. で AA とソートした列を比べ、ずれている位置を 11 にした列を作ります。⟜\+ で前からの累積和、⍜⇌\+ で後ろからの累積和を取って × で掛けると、「前にも後ろにもずれがある位置」、つまりずれている最初の位置から最後の位置までが正になります。/+>0 でその長さを数え、⊣ で取り出した KK と > で比べて、KK を超えていれば "No"、そうでなければ "Yes" を ⨬ で選んで出力しています。