ABC099
ABC100の一歩手前になりました。自分はABC88から参加し始めたのでまだ日は浅いですが、100回になっても今まで通り頑張っていこうと思います。
さて、前回のABCですが、久しぶりにD問題が解けてかなり嬉しかったです。ただ噂のC問題が解けず全完には至ってないので、そこはまだまだだなと感じます。
A - ABD
入力が1000以上であれば"ABD"を、1000以下なら"ABC"をそれぞれ出力してあげます。サンプルケースを見る前は問題文を読み間違えていたので慌ててなおしました。
B - Stone Monument
塔の高さは累積和で表すことができます。i番目の塔は、i-1番目の塔よりもiだけ高くなっています。よって、a,bと入力された塔の高さの差をxとすると、aの塔はx-1番目であることがわかります。したがって、積もっている雪の高さは、x-1番目の塔の高さから入力されたaを引けばよいことになります。
D - Good Grid
C問題は時間内に解けていないので、先にこちらから。
良いグリッドになるには、3で割った余りで分類した３種類それぞれのマス目群に、異なる３色を割り当て、すべてその色で塗りなおす必要があります。よって、一番最初の入力の時点で、3で割った余りがi(0~2です)の時の、色ナンバーk(1~Cです)で塗られていたマス目の数、を記録する、cmemo[i][k]という二次元配列を用意して情報を保存してしまいます。あとは、今回の色は最大30色であるので、30色から3色を選ぶ、という動作をfor文の3重ループで全探索してしまいます。3色を選んだら、その3色に塗り替えたときの違和感の合計を計算して、その最小値を求めて終了です。
自分は、違和感の合計値を、3で割った余りがi(0~2です)の時の、色ナンバーk(1~Cです)に変更した際の違和感を、sum[i][k]という二次元配列におさめました。塗り替える前の色ナンバーの情報をこの時点でまとめ上げて消してしまうことで、最後の計算量を少なくしています。答えはint型だとオーバーフローするのでlong long型を使用しました。これに気づくのに1WA、なおすときに焦ってしまい追加で1WAしたので合計2WAです。
C - Strange Bank
話題の問題です。提出コード1は解説にもある全探索＋貪欲法のコード、2は動的計画法です。コンテスト中は、動的計画法と貪欲法について考えましたが、動的計画法は引き出す際の種類がたかだか12種類であるということを見落としてしまいうまくいかず、貪欲法で条件分岐を利用することを試みることにしました。が、すべての条件を網羅する条件分岐が書けずタイムアップしました。
提出コード1では、6の累乗と9の累乗それぞれであれば貪欲法が使えるということを利用します。入力されたNを任意の2つの数に分解します。そして、片方は6の累乗で貪欲法を、もう片方は9の累乗で貪欲法を適応します。こうしてでた回数の合計値が最も小さくなるようなNの分解の仕方を探します。これは全探索で簡単に求めることができます。
提出コード2では、与えられた条件より、引き出し方が12種類しかないということを利用します。引き出し方のパターンをmemoという配列に格納しました。ここで、i円を最短手数で引き出すことを考えます。仮にmemo[j]円で最後に引き出した時にちょうどi円になったとすると、i-memo[j]円の引き出し方も最短手数になっているはずです。ans[i]を、i円引き出す時の最短手数とすると、
ans[i] = min(ans[ i - memo[j] ]) (ただし、jは0以上12未満)
となります。あとは、この漸化式をもとにiを1から順番にNまで見ていけば答えが求まります。
これ以外にもたくさんの解法があります。動的計画法だけでも、何通りもあります。
こちらのけんちょんさんのブログでは、多くの解法がまとめられているので、是非見ていただければと思います。(リンク:
集める DP と配る DP、メモ化再帰、個数制限なしナップサック問題)
記念すべきABC100もよっぽどのことがない限りはでるつもりです。自分のコードをもうすこし見直ししやすく書けるようにはやくなりたいですね…
