ABC099 C D

所見

ドラマチック。

C Strange Bank

https://abc099.contest.atcoder.jp/submissions/2649978

問題概要

1円、6ⁿ円、9ⁿ円しか引き出せない銀行がある。N円引き出すのに必要な最小手数を求めよ。

取った方針

最初貪欲で行けるような気がしてしまうが、サンプルで貪欲では不可能であることに気づく。
遷移の数が高々12個しかないので(1円引き出すのは最後に引き出す金額が5円以下になった時だけであることを考えると11個)幅優先探索をする。(今回はいくら引き出しても1手という計算なので幅優先探索でOK)

正しい方針(解説の方針)

6^p円を引き出す際、6*q回の引き出しは6^p+1のq回の引き出しに変換できる。
よって、A円引き出すとき、6^p回の引き出しは(A/6^p)%6回行われることがわかる。
9^p円の引き出しも同様。
よって、6^pだけでA円引き出す時、9^pだけでB円引き出す時の最適解がそれぞれ求まるので、6のp乗だけで払える金額について全探索をする。

得られた知見

・手数最適化系の問題では、ある手を他のよりコストが小さい手で置き換えられないか考える。
・制約が状態数の爆発に耐えられそうなら力の全探索💪
・一定スコアを得るための最短手数を求める、という問題は前からDPをしても解けることがある(後述)

解くのに必要な要素

・全探索
・手の置き換え

周辺調査によって得られた知見

・競プロに一定以上慣れている人はこれがDPに見えるらしい
・dp[i] をi円引き出すときの最短手数 とかにする。言われれば確かにそうにしか見えない。

D Good Grid

https://abc099.contest.atcoder.jp/submissions/2652034

問題概要

各マスに色がぬられた盤面とC個の色が与えられる。
(i + j) % 3 == ( x + y ) % 3のとき そのマスには同じ色がぬられており、そうでないときには違う色がぬられている状態にすることを目指し色を塗り替える。
色をiからjに塗り替えた際、D[i][j]のコストがかかる。そのコストの最小値を求めよ。

取った方針

x座標とy座標の和を3で割ったあまりが0,1,2の場所について全て同じ色に塗り替えるコストを前計算する。これはO(CN²)なので間に合う。
同じ色に塗り替えるコストが分かったらすべての色の組み合わせについて全探索する。これはO(C³)で間に合う。

正しい方針(解説の方針)

同上

得られた知見

・重そうな処理をたくさん行う際には前処理ができないか考える。　　 ・複数の処理を分離して考えられないか考える。

解くのに必要な要素

・前処理

周辺調査によって得られた知見

特になし