ABC190
5問でした。(上二つはコンテスト終了後)
一見厄介な問題だけどKが最大16なので2^K回探索しても問題ない
pythondef main():
N, M = map(int, input().split())
AB = []
for _i in range(M):
A, B = map(int, input().split())
AB.append((A - 1, B - 1))
K = int(input())
CD = []
for _i in range(K):
C, D = map(int, input().split())
CD.append((C - 1, D - 1))
ret = 0
for i in range(2 ** K):
xs = [0] * N
for j in range(K):
cd = CD[j]
if i & 1:
xs[cd[0]] = 1
else:
xs[cd[1]] = 1
i >>= 1
r = 0
for j in range(M):
if xs[AB[j][0]] == xs[AB[j][1]] == 1:
r += 1
ret = max(ret, r)
print(ret)
面白い問題
数列の先頭の数をaとすると長さiの列の和はa, 2a+1,3a+3, 4a+6, 5a+10, 6a+16, 7a+21, \ldots
つまりN = (i + 1) a + i (i + 1) / 2であるような整数i,aの個数を数えれば良い
2N = 2a(i+1) + i(i+1) = (i + 1)(i + 2a)
i+1をkと書けば 2N = k (k + (2a-1))
2Nの約数kについて2N / k - k + 1が偶数か判定すればよい
pythondef solve(N):
ret = 0
for x in get_divisors(2 * N):
if (2 * N // x - x + 1) % 2 == 0:
ret += 1
return retE
Kが17と小さい
ツリーの探索？ツリーとは限らない
深さ優先でたどっても最適ではない
グラフをたどる最小値手数？
DP？
一旦Fを先に見る
フェニック木で差分更新しようとしたが、更新部分をよく考えたらフェニック木の操作が要らなかった
最初に求めるところでだけ使う
先頭のxを取り除くと、xより小さいものの数だけ転倒数が減る
0〜N-1の並び替えなので、それはx
末尾にxを付け加えると、xより大きなものの数だけ転倒数が増える
N-1-x
pythondef main():
N = int(input())
AS = list(map(int, input().split()))
ft = FenwickTree(size=N)
tento = 0
for i in range(N):
tento += ft.sum(N) - ft.sum(AS[i])
ft.add(AS[i], 1)
for i in range(N):
print(tento)
x = AS[i]
tento -= x
tento += (N - 1 - x)Related Pages
- →past5h×abc184e×past4j×past4k×abc175d×arc106×abc164d×素因数分解を_o(n^(1/4))_でする×abc189×ABC190E×abc194f×atcoderのpythonでmemoryerrorを出すとreになる×agc048×abc179d×深さ優先探索×aoj_grl_5_c×arc107×agc044a×past2n×past3o×頂点を塗るのか辺を塗るのか×past4m×abc178f×abc192×abc191→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]