ABC190

5問でした。(上二つはコンテスト終了後)

https://gyazo.com/9030631995d9ff9f43f12c962337334d

https://gyazo.com/058a608463f896cfd24f8e7fcce52025

一見厄介な問題だけどKが最大16なので2^K回探索しても問題ない

code:python

def 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):

for j in range(K):

if i & 1:

else:

i >>= 1

r = 0

for j in range(M):

r += 1

ret = max(ret, r)

print(ret)

https://gyazo.com/ee1aa2792d7488de3ae51627cb8e6a45

面白い問題

$ 2N = 2a(i+1) + i(i+1) = (i + 1)(i + 2a)

code:python

def solve(N):

ret = 0

for x in get_divisors(2 * N):

if (2 * N // x - x + 1) % 2 == 0:

ret += 1

return ret

E

Kが17と小さい

ツリーの探索？ツリーとは限らない

深さ優先でたどっても最適ではない

グラフをたどる最小値手数？

DP？

一旦Fを先に見る

https://gyazo.com/62384af9136737b3adf36fccca4e1237

フェニック木で差分更新しようとしたが、更新部分をよく考えたらフェニック木の操作が要らなかった

最初に求めるところでだけ使う

先頭のxを取り除くと、xより小さいものの数だけ転倒数が減る

0〜N-1の並び替えなので、それはx

末尾にxを付け加えると、xより大きなものの数だけ転倒数が増える

N-1-x

code:python

def main():

N = int(input())

AS = list(map(int, input().split()))

ft = FenwickTree(size=N)

tento = 0

for i in range(N):

for i in range(N):

print(tento)

tento -= x

tento += (N - 1 - x)