AtCoder「みんなのプロコン2019」をPythonで解く

「みんなのプロコン2019」に出て、3完でした。

atcoder.jp

C問題のテストケースが一つだけWAになる理由が分からず、1時間以上を浪費しました。レートが下がって悲しいです。

A - Anti-Adjacency（100点）

• 偶数・奇数で場合分け
• "Yes"ではないことに注意する

N, K = list(map(int, input().split()))

if N%2 == 0:
    a = N/2
else:
    a = int(N/2) + 1

if a >= K:
    print("YES")
else:
    print("NO")

B - Path（200点）

• 大学で学んだグラフ理論を思い出した
• 今回の設定では、2つのnodeから2つのedge、残りの2つのnodeから1つのedgeが出ていれば良い
• 全てのinputを一つのlistに格納し、collectionsで条件を満たすか確認

import collections

a = []
for i in range(3):
    a += (list(map(int, input().split())))

c = collections.Counter(a)
ans = c.most_common()

flg = "NO"

if (ans[0][1]) == 2:
    if (ans[0][1]) == 2:
        if (ans[2][1]) == 1:
            if (ans[3][1]) == 1:
                flg = "YES"

print(flg)

C - When I hit my pocket...（400点）

• 「1枚を2回連続で計2枚を増やす」「2回分を使って1円を経由し(B - A)枚を増やす」の比較
• 前者が得な場合は、ずっと1枚を増やし続けるので答えは「K + 1」
• 後者が得な場合は、可能な限り(B - A)枚を増やす
  • まずは1円に交換可能な時点まで進める
  • この時点で残りはrest = (K - A + 1)回
    • restが偶数なら、(B - A)枚増やせるのは(rest / 2)回
    • restが奇数なら、(B - A)枚増やせるのは((rest - 1) / 2)回、余った1回で1枚増やす

K, A, B = list(map(int, input().split()))

if (A + 2 >= B):
    print(K + 1)
elif (A >= K):
    print(K + 1)
else:
    rest = K - (A - 1)
    if (rest%2 == 0):
        print((B - A) * int(rest / 2) + A)
    else:
        print((B - A) * int(rest / 2) + A + 1)

一つだけWAになって時間を溶かした実装

• pythonのfloatの桁落ちが原因だった
• "(int(rest - 1) / 2)" のところが、正しくは "(int( (rest - 1) / 2))"
• もっと楽なのは "/" の代わりに "//" 演算子

そんなあなたに//をどうぞ。スラッシュ2回で切り捨て除算になります

— えじ｜Amane Suzuki (@SakuEji) February 9, 2019

K, A, B = list(map(int, input().split()))
 
cnt = 1
 
if K < A + 1:
    cnt += K
    print(cnt)
    exit()
 
rest = K - (A - 1)
cnt += (A - 1)
 
if (B - A) > 2:
    if (rest%2 == 0):
        cnt += (B - A) * int(rest / 2)
    else:
        cnt += (B - A) * (int(rest - 1) / 2)
        cnt += 1
else:
    cnt += rest
 
print(int(cnt))