ABC437C - Reindeer and Sleigh 2
https://atcoder.jp/contests/abc437/tasks/abc437_c
Dはすぐ解けましたがCに手こずってしまい遅くなりました。どうやったら思いつけるのか解説を読みながら自分なりに考えました。
コンテスト中の動き
ABを4分で解き、Cをちょっと考えてみてすぐに無理そうだと判断し、Dを解きました。この時点で21分。ここまではよかったのですが……。Cが明らかに無理そうなので果敢にもEに挑戦し、こっちはこっちでBFSやDFSを駆使しても目的を達成できそうな探索は作れませんでした。で、しばらくしてまたCに戻ってきました。やけくそで貪欲解法を投げたらそのまま通りました。なんやそれ……。
考察
大まかにこんな風に考えました。重くて力のあるやつには引く方をやってほしい。反対に軽くて力のないやつには乗ってほしい。しかしそうでないその他が問題です。
愚直に全パターンを試すと $ 2^N $ になってしまう問題です。こういうときは DP を疑ってみるようにしています。乗る／乗らないの 2 択なので $ 2 \times N $ の計算回数でなんとかできないかなと想像します。
ところが、何を持たせればいいのかわかりませんでした。W, P を使った値を持たせるにしても、結局 W や P から作られる値を最大化したいわけではなくて乗れるトナカイの数を最大化したいんですね。どうやって DP テーブルを組めばいいのか思いつかず途方に暮れました。
しばらくしてから自分なりの解法ヒントである「隣の要素が次の要素に影響するときはDPが多い。」を思い出しました。この問題だと隣接とか全く関係ありませんね。で、DPか貪欲かで悩むことってよくあるので、思い切って貪欲で考えてみることにします。証明が難しかったりするので貪欲は最終手段と思っているのですが……。
結局こう考えて、とにかく重くてパワーのあるやつに引かせればいいのなら WとRの合計が大きい順に引かせてやれ！！ってなりました。半ばやけくそでした。まさかこれでACできるとは思いもしませんでした。
実装
簡単ですね。全員を乗せた状態から出発し、W+P の大きなやつから下ろしていって合計の力が合計の重さを上回った時点で終わりです。
T = int(input())
ans = []
for _ in range(T):
N = int(input())
WP = []
total_W = 0
for i in range(1, N+1):
w, p = map(int, input().split())
WP.append([w, p])
total_W += w
WP.sort(key= lambda x: x[0]+x[1], reverse=True)
total_P = 0
for i in range(N):
total_P += WP[i][1] # 最初から順に、「引く」に加えていく
total_W -= WP[i][0] # 同時に残る重さからそいつを引く
if total_W <= total_P:
break
ans.append(N - i - 1)
for an in ans:
print(an)
まとめ（結局どう考えればよかったのか）
公式解説とユーザー解説を読んだ結果、こう考えたらしっくり来ました。余力の考え方ですね。
まず全員に引かせてみる。P の合計値 sum(P) が余力になる。トナカイ i を乗せてみる。引く力は sum(P) - P[i]、重量は W[i] となる。余力は $ sum(P) - P[i] - W[i] $ になる。これを繰り返してなるべくたくさん乗せたい。毎回 $ P[i] + W[i] $ が引かれていくから、この値の小さい順に乗せていけばいい。
こんな簡単なことがなぜわからないのか……終わってからならなんとでも言えますがこれをコンテスト中に思いつけなかったというのが現実です。考察のポイントの一つに「数式にしてみる」というのがありますが、今回はさらに
- 絵を描きながら数式を書いてみる
- シミュレーションしてみる
この辺がポイントだったかなと思います。またもや偶然による正解でしたね。正解できただけマシな気はします。
まとめ2（追記）
もう少しつきつめて考えていくと、僕はコンテスト中にシミュレーションしていなかったから法則を思いつけなかったのではなく、シミュレーションのやり方が間違っていたから法則を思いつけなかったのだと気づきました。
僕はコンテスト中、「乗る」「引く」どちらにも所属しない状態から始めて1匹ずつどちらかに振り分けていく方針を採りました。DPの考え方に引っ張られるとどうしてもそうなるのだと思います。
一方、この問題ではまず全員を「乗る」または「引く」状態に所属させ、そこから1匹ずつ移動させていく方針でシミュレーションを行う必要がありました。おそらくですが、この方針から出発すれば容易に W+P の法則に気づけたのではないかと思います。
何人かの方が「つるかめ算」と言っていましたが、このことなんですね。僕もつるかめ算は頭に入っているつもりですが今回の問題では発想として出てこなかったようです。僕にとっては出てきそうで出てこない考え方でした。
というわけで今回の教訓としては、シミュレーションをしてみてもピンとこないようなら別角度からのシミュレーションを検討してみることでしょう。