結果
| 問題 | No.90 品物の並び替え |
| ユーザー |
 atn112323
|
| 提出日時 | 2016-03-09 19:15:18 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 58 ms / 5,000 ms |
| コード長 | 13,449 bytes |
| コンパイル時間 | 3,196 ms |
| コンパイル使用メモリ | 82,284 KB |
| 実行使用メモリ | 50,592 KB |
| 最終ジャッジ日時 | 2024-09-24 16:59:53 |
| 合計ジャッジ時間 | 3,753 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 |
ソースコード
import java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.IOException;import java.io.InputStreamReader;public class Main {/*** This class represents a problem setting.*/class Problem implements IProblem {int[] NM;int[][] score;@Overridepublic void set(ProblemReader reader) throws IOException {NM = reader.nextIntArray();score = reader.nextIntArray2(NM[1]);}@Overridepublic String toString() {// TODOreturn null;}}/*** Solver for the problem.* It's the most important part of codes in this file.*/class Solver implements IProblemSolver<Problem> {@Overridepublic String solve(Problem problem) {int N = problem.NM[0], M = problem.NM[1];int[] items1 = new int[M];int[] items2 = new int[M];int[] scores = new int[M];for (int i = 0; i < M; i++) {items1[i] = problem.score[i][0];items2[i] = problem.score[i][1];scores[i] = problem.score[i][2];}return StringUtils.toString(solve(N, M, items1, items2, scores));}private int solve(int N, int M, int[] items1, int[] items2, int[] scores) {int[][] score = new int[N][N];for (int i = 0; i < M; i++) {score[items1[i]][items2[i]] = scores[i];}int[] max = new int[1 << N];for (int i = 2; i <= N; i++) {int comb = (1 << i) - 1;while (comb < 1 << N) {for (int j = 0; j < N; j++) {if (((comb >> j) & 1) == 1) {int sum = max[comb ^ (1 << j)];for (int k = 0; k < N; k++) {if (((comb >> k) & 1) == 1) {sum += score[k][j];}}max[comb] = Math.max(max[comb], sum);}}int x = comb & -comb;int y = comb + x;comb = ((y ^ comb) / (x << 2)) | y;}}return max[(1 << N) - 1];}}/*** This class is a solver to confirm the main solver.* This solver often works only for a problem with a small number setting.*/class Solver2 implements IProblemSolver<Problem> {@Overridepublic String solve(Problem problem) {// TODOreturn null;}}class Factory implements IProblemFactory<Problem> {@Overridepublic Problem newProblem() {// TODOreturn null;}@Overridepublic Problem newProblem(ProblemReader reader) throws IOException {Problem problem = new Problem();problem.set(reader);return problem;}}class ResultComparator implements IResultComparator {@Overridepublic boolean same(String res1, String res2) {// TODOreturn res1.equals(res2);}}ProblemProcessor<Problem> processor;Main() {Init();}void Init() {ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();config.factory = new Factory();config.solver = new Solver();config.solver2 = new Solver2();config.comparator = new ResultComparator();processor = new ProblemProcessor<Problem>(config);}void process(String mode) throws IOException {processor.process(mode);}public static void main(String args[]) throws IOException {String mode = "solve";new Main().process(mode);}/*Common library*/interface IProblem {abstract void set(ProblemReader reader) throws IOException;}interface IProblemFactory<P extends IProblem> {abstract P newProblem();abstract P newProblem(ProblemReader reader) throws IOException;}interface IProblemSolver<P extends IProblem> {abstract String solve(P problem);}interface IResultComparator {abstract boolean same(String res1, String res2);}class ProblemReader {BufferedReader br = null;ProblemReader() {br = new BufferedReader(new InputStreamReader(System.in));}int nextInt() throws IOException {return StringUtils.toInt(br.readLine());}long nextLong() throws IOException {return StringUtils.toLong(br.readLine());}double nextDouble() throws IOException {return StringUtils.toDouble(br.readLine());}String nextString() throws IOException {return br.readLine();}int[] nextIntArray() throws IOException {return StringUtils.toIntArray(br.readLine());}long[] nextLongArray() throws IOException {return StringUtils.toLongArray(br.readLine());}double[] nextDoubleArray() throws IOException {return StringUtils.toDoubleArray(br.readLine());}String[] nextStringArray() throws IOException {return StringUtils.toStringArray(br.readLine());}int[] nextIntArray(int n) throws IOException {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = nextInt();}return a;}long[] nextLongArray(int n) throws IOException {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nextLong();}return a;}double[] nextDoubleArray(int n) throws IOException {double[] a = new double[n];for (int i = 0; i < n; i++) {a[i] = nextDouble();}return a;}String[] nextStringArray(int n) throws IOException {String[] strs = new String[n];for (int i = 0; i < n; i++) {strs[i] = nextString();}return strs;}int[][] nextIntArray2(int n) throws IOException {int[][] a = new int[n][];for (int i = 0; i < n; i++) {a[i] = nextIntArray();}return a;}long[][] nextLongArray2(int n) throws IOException {long[][] a = new long[n][];for (int i = 0; i < n; i++) {a[i] = nextLongArray();}return a;}double[][] nextDoubleArray2(int n) throws IOException {double[][] a = new double[n][];for (int i = 0; i < n; i++) {a[i] = nextDoubleArray();}return a;}String[][] nextStringArray2(int n) throws IOException {String[][] strs = new String[n][];for (int i = 0; i < n; i++) {strs[i] = nextStringArray();}return strs;}void close() throws IOException {if (br != null) {br.close();}}}class ProblemCreator<P extends IProblem> {IProblemFactory<P> factory;ProblemCreator(IProblemFactory<P> factory) {this.factory = factory;}void create() throws FileNotFoundException {P problem = factory.newProblem();System.out.println(problem.toString());}}class ProblemSolverComparator<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver1, solver2;IResultComparator comparator;ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2, IResultComparator comparator) {this.factory = factory;this.solver1 = solver1;this.solver2 = solver2;this.comparator = comparator;}void compare() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res1 = solver1.solve(problem);String res2 = solver2.solve(problem);if (comparator.same(res1, res2)) {System.out.println(res1);} else {System.err.println(res1 + " " + res2);}} finally {if (reader != null) {reader.close();}}}}class ProblemAnswerer<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver;ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {this.factory = factory;this.solver = solver;}void answer() throws IOException {ProblemReader reader = null;try {reader = new ProblemReader();P problem = factory.newProblem(reader);String res = solver.solve(problem);System.out.println(res);} finally {if (reader != null) {reader.close();}}}}class ProblemProcessorConfig<P extends IProblem> {IProblemFactory<P> factory;IProblemSolver<P> solver, solver2;IResultComparator comparator;}class ProblemProcessor<P extends IProblem> {ProblemProcessorConfig<P> config;ProblemCreator<P> creator;ProblemSolverComparator<P> comparator;ProblemAnswerer<P> answerer;ProblemProcessor(ProblemProcessorConfig<P> config) {this.config = config;creator = new ProblemCreator<P>(config.factory);comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2, config.comparator);answerer = new ProblemAnswerer<P>(config.factory, config.solver);}void process(String mode) throws IOException {switch (mode) {case "create":creator.create();break;case "debug":comparator.compare();break;case "solve":answerer.answer();break;}}}static class StringUtils {static String toString(int a) {return String.valueOf(a);}static String toString(long a) {return String.valueOf(a);}static String toString(double a) {return String.valueOf(a);}static String toString(String str) {return str;}static String toString(int[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(long[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(double[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + " ");} else {sb.append(a[i]);}}return sb.toString();}static String toString(String[] strs) {StringBuilder sb = new StringBuilder();for (int i = 0; i < strs.length; i++) {if (i < strs.length - 1) {sb.append(strs[i] + " ");} else {sb.append(strs[i]);}}return sb.toString();}static String toString2(int[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + "\n");} else {sb.append(a[i]);}}return sb.toString();}static String toString2(long[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + "\n");} else {sb.append(a[i]);}}return sb.toString();}static String toString2(double[] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {if (i < a.length - 1) {sb.append(a[i] + "\n");} else {sb.append(a[i]);}}return sb.toString();}static String toString2(String[] strs) {StringBuilder sb = new StringBuilder();for (int i = 0; i < strs.length; i++) {if (i < strs.length - 1) {sb.append(strs[i] + "\n");} else {sb.append(strs[i]);}}return sb.toString();}static String toString(int[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(long[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(double[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static String toString(String[][] a) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {for (int j = 0; j < a[i].length; j++) {if (j < a[i].length - 1) {sb.append(a[i][j] + " ");} else {sb.append(a[i][j]);}}sb.append("\n");}sb.setLength(sb.length() - 1);return sb.toString();}static int toInt(String s) {return Integer.parseInt(s);}static long toLong(String s) {return Long.parseLong(s);}static double toDouble(String s) {return Double.parseDouble(s);}static int[] toIntArray(String s) {String[] tokens = s.split(" ");int[] a = new int[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Integer.parseInt(tokens[i]);}return a;}static long[] toLongArray(String s) {String[] tokens = s.split(" ");long[] a = new long[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Long.parseLong(tokens[i]);}return a;}static double[] toDoubleArray(String s) {String[] tokens = s.split(" ");double[] a = new double[tokens.length];for (int i = 0; i < tokens.length; i++) {a[i] = Double.parseDouble(tokens[i]);}return a;}static String[] toStringArray(String s) {return s.split(" ");}}}