ABC347備忘録【C~D】

C - Ideal Holidays

問題

考えたこと

周期性があるので何日目にいることを仮定するかは自由です。周期性を考慮した後の日にちに対して最小値を基点として、他の点との距離を求めて休日としていくことが可能か判定していきました。文字だけではわかりずらいので、図で考えていきましょう。以降では入力例２に対して$D$を変えて考えていきます。

図１は距離を求めれば周期性によりスライドすることができ、それにより休日内に収まるか判定できることを表しています。

図２は距離には２種類あることを表していて、こちらも周期性によりスライドをすることができます。距離11のままではすべて平日と判定しまいますが、距離4のほうではすべて休日にすることが可能です。

図３はどちらの距離に対しても最大距離間は全点を網羅するということを表しています。なので、基点から２種類の最大距離、max_dist1, max_dist2をもとめ、これらの小さいほうをスライドさせて休日の範囲内に収まっているか判定すればよいことがわかります。

ACコード

c.py

n, a, b = map(int, input().split())
D = list(map(int, input().split()))
# 周期性を考慮し、日にちを変換。重複を削除
D_set = {d % (a + b) if d % (a + b) != 0 else a + b for d in D}

# 最小の日にちを基点とした
min_d = min(D_set)
D_set.remove(min_d)

max_dist1, max_dist2 = 0, 0
for d in D_set:
    dist = d - min_d
    max_dist1 = max(max_dist1, dist)
    max_dist2 = max(max_dist2, a + b - 1 - dist)

print("Yes" if min(max_dist1, max_dist2) < a else "No")

D - Popcount and XOR

問題

考えたこと

$popcount(X)$と$popcount(Y)$間に差をつけるのは、２進数に変換した$C$が$1$の時のみです。なので、２進数に変換した$C$が$1$の場所をすべて通過した後、$popcount(X)$と$popcount(Y)$は等しくなっており、それぞれ$a$と$b$以下でなければなりません。

条件を確認後、$popcount(X)$と$popcount(Y)$が$a$、$b$に達していない分、$(1, 1)$をつけ足していきます。

ACコード

d.py

a, b, c = map(int, input().split())

bin_c = bin(c)[2:]
n = len(bin_c)
X, Y = ["0" for _ in range(n)], ["0" for _ in range(n)]

for i in range(n):
    if bin_c[i] == "1":
        if a >= b:
            X[i] = "1"
            a -= 1
        else:
            Y[i] = "1"
            b -= 1

if a < 0 or b < 0 or a != b:
    exit(print(-1))

for i in range(n):
    if a == b == 0:
        break
    if bin_c[i] == "0":
        X[i] = "1"
        Y[i] = "1"
        a -= 1
        b -= 1

if 60 - len(X) >= a:
    X = ["1"] * a + X
    Y = ["1"] * a + Y
    print(int("".join(X), 2), int("".join(Y), 2))
else:
    print(-1)