AtCoder Regular Contest 139 B - Make N
https://atcoder.jp/contests/arc139/tasks/arc139_b
問題概要が与えられる。
の状態から、
操作1:コストXでPを1増やす
操作2:コストYでPをA増やす
操作3:コストZでPをB増やす
の3種類のどの操作も任意の回数行える。P=Nにするためのコストの最小値を求めよ。
自分の失敗考察
操作2の単位増加あたりのコスト(つまりY/A)がXより大きいなら、操作2は不要。
その時はO(1)で解ける。操作3についても同様。
難しいのはそれ以外の時、操作2と3をできるだけ使って、余った分だけ操作1を使う時。
Y/AとB/Zの小さい方の操作…★ が多い方が良さそうだが、
余りが大きくなって操作1が増えると逆転がある。
★を貪欲に使えるだけ使った時を考え、
そこから操作数を1ずつ減らしていって試していくと、そのうち最適解に辿り着く？
考えてみると、AとBの最小公倍数分だけAが減ると、
余りの量が元に戻るので、周期的になる。
ということは、A,Bが大きいと間に合わないからだめ。
他、余りの量を0から順に増やしていって、
各試行で拡張ユークリッドの互除法をすることを考えて、
うまい性質があったりしないか考えたがだめ。
正解方針
自分の考察でも半分はOK。
A,Bが大きい時は、単に操作2の回数を全探索すればよい。
Aが以上なら全探索、
未満なら自分の考察の方法、と切り替えれば、O(
)で解ける。
考察典型化
「最小の時も最大の時もO(1)ならO()を疑う」
を境に解法を切り替えればよいパターンを疑う。
自分の思考の癖の補正
「○○が小さい時は解けるけど…」等と思った時に、
その解法を諦めて別の解法を探して迷走することが多い。
「小さい時はこれで解決、後は大きい時を解けばよい」と考えるようにすれば、
2つ以上の解法を切り替えるタイプの問題で迷走はしなくなる。
