ABC184

前回に引き続き今回も全問正解でした。

https://gyazo.com/bf1396a675ce6f642c2012548f6cf565

https://gyazo.com/4d081c9f106aabb035f1e975591248df

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

C

最大3回でOK

すでに重なってたら0

1ステップで移動できるなら1

そうでない場合、大きくずれてる側の軸にそって動かして再帰呼び出し

問題条件の「3以下」をなぜか「4以下」と実装してて1WA

追記: コンテスト中はACしたが、コンテスト後のテストケース追加でWAになりました。

たとえば1,1,1,6などの入力の時に2回横に動いたら到達できるけどパリティが違って2回斜め移動では到達できない

code: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

code:python

def solve(A, B, C):

cache = {}

def f(x):

if 100 in x:

return 0

if x in cache:

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)

return ret

return f((A, B, C))

E

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

F

半分の部分集合を全列挙しても2^20は10^6程度なので余裕

部分集合の和はライブラリ実装済み(グレイコードを使ってみた)

前半と後半でそれぞれ部分集合の和を全列挙しておき、二分探索で和がTを超えない最大の数を見つける

code:python

def solve(N, T, AS):

from bisect import bisect_right

S2.sort()

ret = 0

for x in S1:

if x > T:

continue

i = bisect_right(S2, T - x)

return ret