https://yukicoder.me/problems/no/540
追記 : 7/2にこっそり修正しました。「1 1 -> 3」を間違えてました。
解説放送 (無意味な放送)
解法
https://yukicoder.me/submissions/185939
場合分けを根性で考えて、それぞれ最適な選び方を考える。
公式解説が分かりやすいし、これが全て
なので、ココからは解法というか、ACに至るまでの流れを書き留めておく。
- まずは実験してみた
- 最初のレベルが★3であることを考えると何かしら最善手があるに違いないという仮定
- まず、見つかったのが、2*3の最善っぽい流れ
- 「偶数と奇数の長さであれば最善っぽい流れが作れる」と気づく
- ここで場合分けをして最善手を答えるパターンで作ってみようと思う
- 偶数と奇数をとりあえず書く
- この時ついでに、コーナーケースになりそうで、自明なW,Hが0となる場合を場合分けで書いておく
- あとは、場合分けとして「偶数と偶数」「奇数と奇数」があって分からなかった
- 他の問題を見ても解けそうになかったので、戻ってきて考えてみる
- ここでエスパー力が冴える
- 例「1234 5678」では1234*(5678 + 1) + 1 = 7007887となってる！！
- ここでHとWの掛け算で全て表現できるだろうという仮定を立てる
- 奇数と奇数の例を考えてみる
1 1 → 3 1 3 → 7 3 3 → 13 3 5 → 21
- これを全て満たすやつを考えると(W * 1) * (H + 1) - min(W, H)
- 偶数と偶数の例も考えてみる
2 2 → 6 2 4 → 11 4 4 → 20 1234 5678 → 7007887
- W < Hのとき、W * (H + 1) + 1で行けそう
- W = Hのときが合わない
- 場合分けしてW * (H + 1)とした
- これを全て組み込んで出したら通った
