ABC184

AtCoder Beginner Contest 184 - AtCoder 前回に引き続き今回も全問正解でした。

「後30分でABCだなー」と床暖房でゴロゴロしてたら寝落ちして、起きたら9時を過ぎてたのでメチャクチャ動揺した。

C

• 最大3回でOK
  • すでに重なってたら0
  • 1ステップで移動できるなら1
  • そうでない場合、大きくずれてる側の軸にそって動かして再帰呼び出し
• 問題条件の「3以下」をなぜか「4以下」と実装してて1WA
• 追記: コンテスト中はACしたが、コンテスト後のテストケース追加でWAになりました。
  • たとえば1,1,1,6などの入力の時に2回横に動いたら到達できるけどパリティが違って2回斜め移動では到達できない python

def solve(R1, C1, R2, C2, phase=0):
    if R1 == R2 and C1 == C2:
        return 0
    if R1 + C1 == R2 + C2:
        return 1
    if R1 - C1 == R2 - C2:
        return 1
    if abs(R1 - R2) + abs(C1 - C2) <= 3:
        return 1

    d1 = abs(R1 + C1 - R2 - C2)
    d2 = abs(R1 - C1 - R2 + C2)
    if d1 > d2:
        d = R1 + C1 - R2 - C2
        d //= 2
        R1 -= d
        C1 -= d
        return solve(R1, C1, R2, C2) + 1
    else:
        d = R1 - C1 - R2 + C2
        d //= 2
        R1 -= d
        C1 += d
        return solve(R1, C1, R2, C2) + 1

D

• メモ化再帰で期待値DP python

def solve(A, B, C):
    cache = {}

    def f(x):
        if 100 in x:
            return 0
        if x in cache:
            return cache[x]
        a, b, c = x
        ret = 1
        if a:
            y = tuple(sorted((a + 1, b, c)))
            ret += f(y) * a / (a + b + c)
        if b:
            y = tuple(sorted((a, b + 1, c)))
            ret += f(y) * b / (a + b + c)
        if c:
            y = tuple(sorted((a, b, c + 1)))
            ret += f(y) * c / (a + b + c)
        cache[x] = ret
        return ret
    return f((A, B, C))

E

• 実装が複雑そうだったので飛ばしてFを先に。

F

• 半分全列挙
  • 半分の部分集合を全列挙しても2^20は10^6程度なので余裕
• 部分集合の和はライブラリ実装済み(グレイコードを使ってみた)
• 前半と後半でそれぞれ部分集合の和を全列挙しておき、二分探索で和がTを超えない最大の数を見つける python

def solve(N, T, AS):
    from bisect import bisect_right
    S1 = sum_for_all_subset_grey(AS[:N//2])
    S2 = sum_for_all_subset_grey(AS[N // 2:])
    S2.sort()
    ret = 0
    for x in S1:
        if x > T:
            continue
        i = bisect_right(S2, T - x)
        ret = max(ret, x + S2[i - 1])
    return ret

ABC184E