https://atcoder.jp/contests/abc119/tasks/abc119_c
- 考えたこと
- 操作の順序は関係ない
- 結合してから伸縮しても伸縮してから結合してもコストは同じ
- なので先に結合のことだけ考えればよい
- 棒は8本なので、どれを選んで結合するか2^8通り、これはDPするまでもない
- おっと問題条件勘違い、目的は特定長さの1本を得るのではなく3本を得るのか
- 3つのグループのどれに入れるか、入れないか、で4^8通り、10^5より小さい、全探索してOK
- グループごとの目的長さは降順と仮定しても一般性を失わない
- 結合した竹の長さを求めて、目的値との差の絶対値をスコアに加算、最も小さいものを返す
- 操作の順序は関係ない
- 公式解説
- 方針は同じ
- 「無を延長することはできない」確かに。これを見落としてたので僕はWAになる