Codeforces Round #697 (Div.3)

はい。
Codeforces Round #697 (Div.3)
unratedになったので途中で撤退してました。

A. Odd Divisor

▶クリックで開閉

t=int(input())
for i in range(t):
    n=int(input())
    while n%2==0:
        n//=2
    print("YES" if n!=1 else "NO")

約数の中に奇数が存在するか？かな。2で割り続けて現れる奇数が1より大きいかで調べました。

B. New Year's Number

▶クリックで開閉

t=int(input())
for i in range(t):
    n=int(input())
    print("YES" if (n//2020>=n%2020) else "NO")

2020と2021の和で数が作れるか？？2020で割ります。2020で割った余りを確認します。
例えば2020で割った商が5で余りも5以下なら2020,2021の和で作れます。余りが5より大きいと全て2021を使っても足りないのでそれで判定できると思います。

C. Ball in Berland

▶クリックで開閉

t=int(input())
for i in range(t):
    a,b,k=map(int,input().split())
    x=[int(i)-1 for i in input().split()]
    y=[int(i)-1 for i in input().split()]
    xd={int(i):0 for i in range(a)}
    yd={int(i):0 for i in range(b)}
    ans=0
    for i in x:
        xd[i]+=1
    for i in y:
        yd[i]+=1
    for i in range(k):
        ans+= k-xd[x[i]]-yd[y[i]]+1
    print(ans//2)

2ペア同時作成します。同じ番号の人は同時作成できません。二部グラフとして考えます。各頂点の辺の数を数えておきます。各ペア候補を先頭から調べます。全体の辺の数はk本です。調べる対象の頂点の辺は全て使えなくなります。ですけども調べる対象のペア1つだけは残ります。ペアと無関係な辺は全て同時作成可能なペアです。全部調べ終わると重複で2回数えていることになるので2で割ったものが解になります。