Synthetic Kadomatsu [AtCoder Beginner Contest 119 C]
N個の数値が与えられる。これらの数値に以下の操作をほどこして、3つの値 A,B,C を作る。必要となるコストのうち、最小のものを求めよ、という問題です。
・数値を1増やす（コスト1）
・数値を1減らす（コスト1）
・2つの数値を足して新しい数値とする（コスト10）
まず前提として、いずれも加減の計算なので、操作の順番は無視することができます。
解答の方針を説明する前に、とりあえずコードを載せてしまいます。
import java.util.*; import java.util.stream.*; class Main { static Scanner sc = new Scanner(System.in); static int nextInt () {return Integer.parseInt(sc.next());} static int[] nextIntArray (int n) {return IntStream.range(0,n).map(i->nextInt()).toArray();} static int maxInt = Integer.MAX_VALUE; static int minInt = Integer.MIN_VALUE; public static void main(String[] args) { //入力を受け取る int n = nextInt(); int[] take = nextIntArray(3); ArrayList<Integer> sozai = new ArrayList<>(); for (int i=0; i<n; i++) sozai.add(nextInt()); //A,B,Cの順列のパターンをListに入れておく ArrayList<ArrayList<Integer>> pattern = new ArrayList<>(); for (int i=0; i<6; i++) { pattern.add(new ArrayList<>()); } pattern.get(0).add(take[0]); pattern.get(0).add(take[1]); pattern.get(0).add(take[2]); pattern.get(1).add(take[0]); pattern.get(1).add(take[2]); pattern.get(1).add(take[1]); pattern.get(2).add(take[1]); pattern.get(2).add(take[0]); pattern.get(2).add(take[2]); pattern.get(3).add(take[1]); pattern.get(3).add(take[2]); pattern.get(3).add(take[0]); pattern.get(4).add(take[2]); pattern.get(4).add(take[0]); pattern.get(4).add(take[1]); pattern.get(5).add(take[2]); pattern.get(5).add(take[1]); pattern.get(5).add(take[0]); //各パターン毎にA,B,Cを実際に作って、各パターンでかかるコストのうち最小のものを答えとする int ans = maxInt; //メイン処理ここから---------------------------------------------------------- for (int i=0; i<6; i++) { //合成する際、List内の素材を消しながら合成していくので、あらかじめコピーしておく ArrayList<Integer> tempSozai = (ArrayList<Integer>) sozai.clone(); int minminCost = 0;//パターンiの最小コスト //パターンiのj番目の竹を作っていくループ for (int j=0; j<3; j++) { //パターンiのj番目の竹を作るために使用した素材を入れておくList ArrayList<Integer> sozaiNum = new ArrayList<>(); int minCost = maxInt; //パターンiのj番目の竹を作るときの最小コスト //ビット全探索 ********************************************************* for (int k=1; k<(Math.pow(2,tempSozai.size())); k++) { int gouseiNum = 0; //合成した回数（この回数ぶんだけコスト10がかかる） int length = 0; //合成したときの長さ ArrayList<Integer> temp = new ArrayList<>(); //どの素材を合成したかのメモ for (int m=0; m<tempSozai.size(); m++) { if ((1&k>>m) == 1) { length += tempSozai.get(m); gouseiNum++; temp.add(tempSozai.get(m)); } } //合成した結果、竹が2本以下になってはA,B,Cの3本を作れないのでcontinue if (gouseiNum > n-2) continue; //パターン i の j 番目の竹を k 番目の作成パターンで作成したときにかかるコスト int cost = (gouseiNum-1)*10 + Math.abs(pattern.get(i).get(j)-length); //パターン i の j 番目の竹の最小作成コストを更新 if (cost < minCost) { minCost = cost; sozaiNum = (ArrayList<Integer>)temp.clone(); //最小コストのときに使用した竹をメモ } } //ビット全探索ここまで **************************************************** //パターンiのj番目の竹を作るために使用した素材をListから消去する for (int k=0; k<sozaiNum.size(); k++) { tempSozai.remove(sozaiNum.get(k)); } //パターンiのj番目の竹を作るためにかかったコストを、パターンiのコストに足す minminCost += minCost; } //パターンiのコストと、その時点での最小コストを比較して更新する ans = Math.min(ans, minminCost); } //メイン処理ここまで---------------------------------------------------------------- //出力 System.out.println(ans); } }
コードが相当スパゲッティになっているので、やっていることを以下に箇条書きで示します。
①A,B,Cをどの順番で作るか、6つのパターンを全て列挙する
・ABC,ACB,BCA......
②パターン毎に、実際にA,B,Cを作ってみる
・パターン i の0番目の竹を作る
・ビット全探索で、素材の合成の組み合わせを全て列挙する
・組み合わせのうち、作成したときのコストが最小になるものを0番目の竹の作成コストとする
・素材から、0番目の竹を作ったときに使ったものを取り除く
・パターン i の1番目の竹を作る
・同様の処理。ただし、0番目の竹を作ったときに使った素材は無くなっている
・パターン i の2番目の竹を作る
・同様の処理。ただし、0,1番目の竹を作ったときに使った素材は無くなっている
・パターン i の A,B,C を全て作り終わった。A,B,C の作成コストの総和をパターン i のコストとして記録する
③6つのパターンのコストのうち、もっとも少ないものが答え
