c問題、D問題共に全探索の問題だったので、いかに計算量を抑えるかが重要であった。一応自力で解けた
https://atcoder.jp/contests/abc99
C問題
方針
一見、6のx乗か9のy乗のうちNに一番近いものから引いていくような貪欲法で解けそうだが実はN=108の場合を考えると81,9,9,9の4操作ではなく、実は36,36,36,の3回操作が最小となる。つまりNより小さい範囲で全探索することで最小回数を見つけなければならない。よって、Nの範囲だけ、あらかじめ6のx乗と9のy乗を計算し、配列などに入れてソートしていき、dfsなどで全探索すると良い。
D問題
方針
3で割ったあまりでグループ分けできるので、あらかじめあまり0、あまり1、あまり2グループに分け、それぞれの元々の値を記録しておく。その後、各グループごとに、各色に変化した時の合計値を記録しておき、最後に、3グループについて全ての色の組み合わせをdfsなどで試せば答えが求まる。計算量は、色の組み合わせが最大で30*29*28でそれぞれの処理は定数でできるので十分間に合う。