ABC184
前回に引き続き今回も全問正解でした。
「後30分でABCだなー」と床暖房でゴロゴロしてたら寝落ちして、起きたら9時を過ぎてたのでメチャクチャ動揺した。
C
最大3回でOK
すでに重なってたら0
1ステップで移動できるなら1
そうでない場合、大きくずれてる側の軸にそって動かして再帰呼び出し
問題条件の「3以下」をなぜか「4以下」と実装してて1WA
追記: コンテスト中はACしたが、コンテスト後のテストケース追加でWAになりました。
たとえば1,1,1,6などの入力の時に2回横に動いたら到達できるけどパリティが違って2回斜め移動では到達できない
pythondef 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) + 1D
pythondef 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を超えない最大の数を見つける
pythondef 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 retRelated Pages
- →past5h×ABC184E×past4j×past4k×abc175d×arc106×abc164d×素因数分解を_o(n^(1/4))_でする×abc189×abc190e×abc194f×atcoderのpythonでmemoryerrorを出すとreになる×agc048×abc179d×深さ優先探索×aoj_grl_5_c×arc107×agc044a×past2n×past3o×頂点を塗るのか辺を塗るのか×past4m×abc178f×abc192×abc191→
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]