ABC190

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

C - Bowls and Dishes

• 
• 一見厄介な問題だけどKが最大16なので2^K回探索しても問題ない 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):
        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)

D - Staircase Sequences

• 
• 面白い問題
• 数列の先頭の数をaとすると長さiの列の和は$a,2a+1,3a+3,4a+6,5a+10,6a+16,7a+21,\dots$
• つまり$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$が偶数か判定すればよい 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を先に見る

F - Shift and Inversions

• 
• フェニック木で差分更新しようとしたが、更新部分をよく考えたらフェニック木の操作が要らなかった
  • 最初に求めるところでだけ使う
• 先頭のxを取り除くと、xより小さいものの数だけ転倒数が減る
  • 0〜N-1の並び替えなので、それはx
• 末尾にxを付け加えると、xより大きなものの数だけ転倒数が増える
  • N-1-x python

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

ABC190E