[Python]ARC106個人的メモ[AtCoder]

ARC106

所感

AB2完
2完だったけど結構速く解けたと思ってたので良いパフォーマンスが出て良かった
でも今回で入緑したかったのでそこは残念
コードはコンテスト中に提出したものを少し手直ししてあります

A - 106

最初に3があんまり大きくない乗数でNの制約を超えるだろうと感じたので，AかBを固定して考える問題だなって割とすぐ分かった
実際Aは40乗ぐらいでNの制約である10の18乗よりも大きくなる，Bは30ぐらい
よって全探索すればいい
今気づいたが2重のfor文でおｋ

#!/usr/bin/env python3
N = int(input())

res = 5
lst = set([res])
while res < 10 ** 18:
    res *= 5
    lst.add(res)

res = 3
a = 1
while N - res not in lst:
    if N - res < 0:
        print(-1)
        exit()
    res *= 3
    a += 1

b = sorted(list(lst)).index(N - res)

print(a, b + 1)

二重for文で書いたコード

#!/usr/bin/env python3
N = int(input())

limit = 50

for a in range(1, limit):
    for b in range(1, limit):
        if 3 ** a + 5 ** b == N:
            print(a, b)
            exit()

print(-1)

B - Values

同じ木?に属しているノードのAの合計がBの合計と一致すればYesかなって考えてコード書いたらacした
Unionfindで同じ木に属しているノードを探索し，木ごとにAとBの合計を計算した

#!/usr/bin/env python3
class UnionFind:
    def __init__(self, n: int):
        self.root = [-1] * n

    def find(self, x: int):
        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)

    def size(self, x: int) -> bool:
        return self.root[self.find(x)] * -1


N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

union = UnionFind(N)
for _ in range(M):
    c, d = map(int, input().split())
    union.unite(c - 1, d - 1)

lst = [[] for _ in range(N)]
for n in range(N):
    lst[union.find(n)].append(n)

flag = True
for can in lst:
    res1 = 0
    res2 = 0
    for n in can:
        res1 += A[n]
        res2 += B[n]
    if res1 != res2:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")

C - Solutions

wa
残り5分ぐらいの時点で1waの状態まで行けた
残り1分切ったあたりでN=1の場合の考慮が欠けてたことに気づいた
で，修正しきれず終了
非常に悔しかったです

問題Pが蟻本に乗ってる区間スケジューリング問題ってのと完全に一致してる
なので，高橋君のプログラムが正解を返すことは割と早く分かった
一方，青木君のプログラムは間違っている
反例は以下の図
最適解は4つの区間を選択することだが，青木君は3つしか選べない

従って，必ず$(高橋君の解)\geq(青木君の解)$になる
なので，$M<0$の場合はありえない

まず$M=0$の場合を考える
図に示した共通の区間をN個出力すれば良い

$M>0$の場合を考える
青木君と高橋君で選ぶ区間に差をつけるには下図のように区間を配置すれば良さそうである
この図の場合は$M=1$となる
図を参考に考えると，1つの長い区間の範囲内に$M+1$個の区間が含まれていれば良さそうである
また，最初にMを満たす様に青と黒の区間を配置し，その後Nを満たす様に緑の区間を配置していけばよさそうである
矢印の制約は各座標について始点又は終点のいずれか1つしか配置できないということだけだから，(高橋君の選ぶ区間)と(共通の区間)は長さ1で良い
座標の制約もあるが入力の制約に対して十分大きいので，この考え方なら気にする必要は無い

で，ここから細かい制約を見ていく

まず，$N=1 or 2$の時は必ず$M=0$である
$N=1$の時は区間が1個しかないのだから，高橋君も青木君も選び方が同じしかありえないからで，$N=2$の時は2人の選び方に差が生じないからである
何故なら，区間が重なっていたら，2人とも1つの区間しか選べない，一方で区間が重なっていなかったら2人とも2つの区間を選べる

次に$N>2$の場合
この時，$N-M<2$が成り立つ必要がある
まず，$N>2$の範囲で青木君が区間を1つも選ばない場合は存在しない
よって，$N=M$はありえない
また，$M=N-1$となる時の2人の選び方は高橋君がN個，青木君が1個の場合か，高橋君がN-1個，青木君が0個の場合の2つしかない
0個はあり得ないので後者は無し
前者も，下図で共通部分を除去してN=3の場合を考えてみれば分かる
青木君の選択を1つにするためには，その1つ以外の区間が青木君の区間の範囲内に互いに重複する部分が無い状態で収まっている必要がある
しかし，その状態では青木君の区間とそれ以外の区間を同時に選択できないので，高橋君の選択がN個になることは無い
従って，$M=N-1$となることもあり得ず，$N>2$の場合$N-M<2$が成り立つ必要がある

#!/usr/bin/env python3
N, M = map(int, input().split())

if M < 0 or (N > 2 and N - M < 2):
    print(-1)
    exit()

a = 0
b = 1
if M > 0:
    print(1, 2 + (M + 1) * 2)

    for i in range(N - 1):
        if i == M + 1:
            # 青矢印の終了点
            a += 3
            b += 3
        else:
            a += 2
            b += 2
        print(a, b)

elif M == 0:
    for _ in range(N):
        a += 2
        b += 2
        print(a, b)