結果
問題 | No.334 門松ゲーム |
ユーザー |
![]() |
提出日時 | 2016-01-15 22:52:27 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 229 ms / 2,000 ms |
コード長 | 1,232 bytes |
コンパイル時間 | 2,896 ms |
コンパイル使用メモリ | 79,096 KB |
実行使用メモリ | 43,144 KB |
最終ジャッジ日時 | 2024-09-19 19:21:39 |
合計ジャッジ時間 | 6,038 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
package no334;import java.util.Scanner;public class Main {static int n;static int[] k;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();k = new int[n];for(int i=0;i<n;i++) {k[i] = sc.nextInt();}int ans = dfs((1<<n)-1);if (ans == Integer.MAX_VALUE) {System.out.println(-1);}else{System.out.println(ans / 10000 + " " + (ans / 100 % 100) + " " + ans % 100);}}static int[] memo = new int[1<<12];//先手が勝てるかpublic static int dfs(int m) {if (memo[m] != 0) {return memo[m];}int[] use = new int[3];int ret = Integer.MAX_VALUE;for(int i=0;i<1<<n;i++) {if ((~m & i) != 0 || Integer.bitCount(i) != 3) {continue;}int ind = 0;for(int j=0;j<n;j++) {if ((i >> j & 1) == 1) {use[ind++] = j;}}if (isKadomatsuSequence(k[use[0]], k[use[1]], k[use[2]])) {if (dfs(m & ~i) == Integer.MAX_VALUE) {ret = Math.min(ret, use[0] * 10000 + use[1] * 100 + use[2]);}}}return memo[m] = ret;}public static boolean isKadomatsuSequence(long a,long b,long c) {if (a == b || b == c) {return false;}return b < a && b < c || b > a && b > c;}}