M-SOLUTIONS プロコンオープン 2020
4連休でのんびりしてたらすっぽかしたので事後的に解いた
全探索できるサイズだなとは思ったが、最短手数を求めて足りてるかどうかを判断した。公式解説と同じ。
pythondef solve(A, B, C, K):
while A >= B:
K -= 1
B *= 2
while B >= C:
K -= 1
C *= 2
if K >= 0:
return "Yes"
return "No"複数の数の移動ウィンドウでの積を比較する問題
最大10^9の値を20万個掛け算することになるので早々に「掛け算はしない」という方針
ウィンドウの前後で比較すれば良いだけ
pythondef solve(N, K, AS):
for i in range(K, N):
if AS[i - K] < AS[i]:
print("Yes")
else:
print("No")なんらかの探索が必要なのかどうなのか、を考えるためにまずは末尾から2日、3日の範囲で行動を考えた
結論、要するに単調増加の始まるところで全力で買い、単調非減少の終わるところで全力で売れば良い、と考えた
大きな上昇トレンドの中に窪みがある場合でも、窪みの直前で売って窪みの底で買えばより良い結果になるから。
それを実装したら「明日値上がりするなら買う、明日値下がりするなら売る」というシンプルな行動ルールに帰着した
pythondef solve(N, XS):
cash = 1000
stock = 0
for i in range(N - 1):
price = XS[i]
if cash >= price:
if XS[i + 1] > price:
# buy
s = cash // price
stock += s
cash -= s * price
continue
if stock > 0:
if XS[i + 1] < price:
# sell
cash += stock * price
stock = 0
# last day
cash += stock * XS[-1]
return cash時間内に解けなかった。
正しい解法にたどり着いたと自信満々で実装して上手くいかなかった
サンプルケースでは全部うまくいったのにサブミットするとダメなパターン
解説みたら解法が正しくなかったので、今度改めて解く
ここでは時間内に考えたことを書く
まず考えたのはこれは1本ずつ足していけば良い問題なのかどうか
よく見たらサンプルでそうではないケースが紹介されてた
次に考えたこと、線の選択肢はいくつあるか
都市の上を通ってない線に関しては、それをより人数の多い側にずらすことでスコアが改善する
人数がイコールである場合にも悪化はしない
なので都市の上を通る線だけを考えて良い
線の追加順は関係ない
なのでスコアは線選択肢の部分集合を定義域とする関数
距離は、新しく追加された線への距離とのminを取ることで更新できる
集合を定義域とし、距離を値とする動的計画法
都市が15個なので線は最大30、部分集合を整数にパックできるサイズだ→ bitDP
この方針のダメだった点
計算量の見積もりが甘い、2^30はおよそ10^10なので、数秒で計算するのは無理、さらに削減する必要があった
本数オーバーで打ち切ってるから十分小さいかなぁと思ったのだが…
comb(30, 15)は1.6 * 10^8
3^15だと 1.4 * 10^7ぐらいになる(この計算は暗算ではできなかった)
ある都市を線が通った場合(wlog南北に)、その都市は以降の線の置き方によらず距離0なので東西に並ぶ都市がない限り東西の線は通らない
解説ではこれに加えてN^2をNに削減する議論をしている
「距離は、新しく追加された線への距離とのminを取ることで更新できる」を使えばNなのではと思う
追記: そもそも
[None] * (1 << 30) はAtCoder環境ではMemoryErrorでREになる(MLEではない)空間計算量の見積もりが甘々だった
サイズ30の集合の部分集合を考えてはいけない
南北線と東西線を別々に考えて2^15+2^15にするべきだった
半分全列挙っぽい発想だ
Related Pages
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
"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]