勉強方法
勉強時間は10-20時間程度
過去問道場で午前2の過去問を全問解いた
http://www.amazon.co.jp/dp/4774169374/を一回通読した
午後1、午後2を2年4回分解いた
結果
感想
多分去年の春頃に趣味で暗号技術入門を読んでいたのが前提知識として役に立ったのかもしれない
自己採点を厳しくしすぎた感がある(合格ギリギリと見積もっていた)
秋季はネットワークスペシャリストを受けようと思う。
勉強方法
勉強時間は10-20時間程度
過去問道場で午前2の過去問を全問解いた
http://www.amazon.co.jp/dp/4774169374/を一回通読した
午後1、午後2を2年4回分解いた
結果
感想
多分去年の春頃に趣味で暗号技術入門を読んでいたのが前提知識として役に立ったのかもしれない
自己採点を厳しくしすぎた感がある(合格ギリギリと見積もっていた)
秋季はネットワークスペシャリストを受けようと思う。
絶対DPの神様が降りてきてる
dp[i][j] i = 木の耐久力 j = 経験値
dp[i][j] = 最小回数
dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)] = Math.min(dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)], dp[i][j] + 1);
みたいな感じでDP
import java.util.*; import java.io.*; import java.math.*; public class Main { static Scanner sc = new Scanner(System.in); static PrintWriter out = new PrintWriter(System.out); static int INF = 2 << 25; public static void main(String[] args) { while(true) { int d = sc.nextInt(); int n = sc.nextInt(); if(d == 0 && n == 0) break; int[] a = new int[n]; int[] e = new int[n]; int[] r = new int[n]; for(int i = 0; i < n; i++) { a[i] = sc.nextInt(); e[i] = sc.nextInt(); r[i] = sc.nextInt(); } int[][] dp = new int[d+1][101]; for(int i = d; i >= 0; i--) { Arrays.fill(dp[i], INF); } dp[d][0] = 0; for(int i = d; i >= 0; i--) { for(int j = 0; j <= 100; j++) { for(int k = 0; k < n; k++) { if(j >= r[k]) { dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)] = Math.min(dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)], dp[i][j] + 1); } } } } int min = INF; for(int i = 0; i < 101; i++) { min = Math.min(min, dp[0][i]); } if(min == INF) { System.out.println("NA"); } else { System.out.println(min); } } } }
Knocker of the Gigas Cedar | Aizu Online Judge
問題出典 PC Koshien 2013 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2013-11-9
http://web-ext.u-aizu.ac.jp/pc-concours/
今日はDPの神が降りてきている
自力で解いた
dp[i][j] iは日数 jは派手さとしてDP
import java.util.*; import java.io.*; import java.math.*; public class Main { static Scanner sc = new Scanner(System.in); static PrintWriter out = new PrintWriter(System.out); public static void main(String[] args) { int d = sc.nextInt(); int n = sc.nextInt(); int[] t = new int[d]; for(int i = 0; i < d; i++) { t[i] = sc.nextInt(); } int[] a = new int[n]; int[] b = new int[n]; int[] c = new int[n]; for(int i = 0; i < n; i++) { a[i] = sc.nextInt(); b[i] = sc.nextInt(); c[i] = sc.nextInt(); } int[][] dp = new int[d][101]; for(int i = 0; i < d; i++) { Arrays.fill(dp[i], -1); } for(int i = 0; i < n; i++) { if(t[0] >= a[i] && t[0] <= b[i]) { dp[0][c[i]] = 0; } } for(int i = 1; i < d; i++) { for(int j = 0; j < n; j++) { if(t[i] >= a[j] && t[i] <= b[j]) { for(int k = 0; k < 101; k++) { if(dp[i-1][k] != -1) { dp[i][c[j]] = Math.max(dp[i-1][k] + Math.abs(k - c[j]), dp[i][c[j]]); } } } } } int max = 0; for(int i = 0; i < 101; i++) { max = Math.max(dp[d-1][i], max); } System.out.println(max); } }
Source: 12th Japanese Olympiad in Informatics, Preliminary Round , 2012-12-16
http://www.ioi-jp.org/
またまたJOIのDP問題 自力で解けた
dp[i][j] iは何日目か jは出席する人間のBIT
i日目に出席できる組み合わせは i-1日目の組み合わせに依存するので
dp[i][j] = (jとANDをとって0にならず、 かつ 責任者がいる 一日前のjの和)
としてDP
一日目は必ず Jが出席しないといけないことが抜けててバグバグした
import java.util.*; import java.io.IOException; import java.math.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); String m = sc.next(); int[][] dp = new int[n][1 << 3]; //000 JOI for(int i = 0; i < 1 << 3; i++) { if(B(Integer.toBinaryString(i)).charAt(JOI(m.charAt(0))) == '1' && B(Integer.toBinaryString(i)).charAt(0) == '1') { dp[0][i] = 1; } } for(int i = 1; i < n; i++) { for(int j = 0; j < 1 << 3; j++) { if(B(Integer.toBinaryString(j)).charAt(JOI(m.charAt(i))) == '1') { for(int k = 0; k < 1 << 3; k++) { if((k & j) != 0) { dp[i][j] += dp[i-1][k] % 10007; } } } } } int sum = 0; for(int i = 0; i < 1 << 3; i++) { sum += dp[n-1][i] % 10007; } System.out.println(sum % 10007); } static int JOI(char a) { if(a == 'J') return 0; if(a == 'O') return 1; return 2; } static String B(String a) { StringBuilder sb = new StringBuilder(); for(int i = 0; i < 3- a.length(); i++) { sb.append("0"); } sb.append(a); return sb.toString(); } }
Source: 13th Japanese Olympiad in Informatics, Preliminary Round , 2013-12-15
http://www.ioi-jp.org/
なんとか自力で解いたDP問題
dp[i][j] i は 何日目 jはパスタの3日分の履歴 3進数として考えた
import java.util.*; import java.io.IOException; import java.math.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int K = sc.nextInt(); int[] listA = new int[K]; int[] listB = new int[K]; for(int i = 0; i < K; i++) { listA[i] = sc.nextInt(); listB[i] = sc.nextInt(); } long[][] dp = new long[n][27]; IN:for(int i = 0; i < n; i++) { if(i == 0) { for(int j = 0; j < K; j++) { if(1 == listA[j]) { int k = listB[j]-1; dp[0][k] = 1; continue IN; } } for(int j = 0; j < 3; j++) { dp[0][j] = 1; } continue IN; } if(i == 1) { for(int j = 0; j < K; j++) { if(2 == listA[j]) { int tmp = listB[j]-1; for(int k = 0; k < 9; k++) { if(k % 3 == tmp) { dp[1][k] = dp[0][k/3]; } } continue IN; } } for(int j = 0; j < 9; j++) { dp[1][j] = dp[0][j/3]; } continue IN; } for(int j = 0; j < K; j++) { if(i+1 == listA[j]) { for(int k = 0; k < 27; k++) { if(k % 3 == listB[j]-1 && !(k%3 == (k%9)/3 && (k%9)/3 == k/9)) { dp[i][k] += dp[i-1][(k/9)*3 + (k%9)/3] + dp[i-1][9 + (k/9)*3 + (k%9)/3] + dp[i-1][18 + (k/9)*3 + (k%9)/3]; dp[i][k] %= 10000; } } continue IN; } } for(int k = 0; k < 27; k++) { if(!((k%3) == (k%9)/3 && (k%9)/3 == k/9)) { dp[i][k] += dp[i-1][(k/9)*3 + (k%9)/3] + dp[i-1][9 + (k/9)*3 + (k%9)/3] + dp[i-1][18 + (k/9)*3 + (k%9)/3]; dp[i][k] %= 10000; } } } int sum = 0; for(int i = 0; i < 27; i++) { sum += dp[n-1][i] % 10000; sum %= 10000; } System.out.println(sum); } }
全埋めしました Blurとか辛かった。枝刈りゲーこわい。
Unknown Switches | Aizu Online Judge
AOJ-ICPCの200問題
めっちゃ悩んだ つらかった
問題要約
電源スイッチの操作状況 S (オンオフではなく、スイッチの状態を変えたか)と電球が点灯しているかどうか B が与えられる
電源スイッチと電球の対応を出力せよ
電源スイッチとの対応関係が分かる電球の場合、対応する電源スイッチの番号を出力し
電源スイッチとの対応関係が不明な電球の場合、「?」と出力せよ
解法
電源スイッチと電球の対応表を作り、
電源スイッチの状態(オンかオフか)と電球の状態(点灯しているかしていないか)が食い違う場合、電源スイッチと電球が対応していないと記録する
電源スイッチと電球の対応が1対1に定まるとき該当の電源スイッチの番号を出力し、
定まらない場合は「?」を出力する
さてこんなわけのわからないたわし語を用いたたわしの説明よりスライドを見た方が早い
というわけでこちらが公式の解説スライドです
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=B.pdf
import java.util.*; public class Main { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); while(true) { int n = stdIn.nextInt(); int m = stdIn.nextInt(); int q = stdIn.nextInt(); if(n == 0 && m == 0 && q == 0) break; String[] S = new String[q]; String[] B = new String[q]; for(int i = 0; i < q; i++) { S[i] = stdIn.next(); B[i] = stdIn.next(); } boolean[][] SX = new boolean[q][n]; boolean[][] BX = new boolean[q][m]; for(int i = 0; i < q; i++) { for(int j = 0; j < n; j++) { SX[i][j] = (S[i].charAt(j) == '1')?true:false; } for(int j = 0; j < m; j++) { BX[i][j] = (B[i].charAt(j) == '1')?true:false; } if(i != 0) { for(int j = 0; j < n; j++) { SX[i][j] = (S[i].charAt(j) == '1')?!SX[i-1][j]:SX[i-1][j]; } for(int j = 0; j < m; j++) { BX[i][j] = (B[i].charAt(j) == '1')?true:false; } } } boolean[][] list = new boolean[n][m]; for(int i = 0; i < q; i++) { for (int j = 0; j < n; j++) { if (SX[i][j]) { for (int k = 0; k < m; k++) { if (!BX[i][k]) { list[j][k] = true; } } } if (!SX[i][j]) { for (int k = 0; k < m; k++) { if (BX[i][k]) { list[j][k] = true; } } } } } if(n == 1) { for(int i = 0; i < m; i++) { System.out.print(0); } System.out.println(); continue; } int[] ans = new int[m]; for(int i = 0; i < m; i++) { ans[i] = -1; int count = 0; int id = 0; for(int j = 0; j < n; j++) { if(!list[j][i]) { id = j; count++; } } if(count == 1) { ans[i] = id+1; } } for(int i = 0; i < ans.length; i++) { if(ans[i] == -1) { System.out.print("?"); } else if(ans[i] <= 10) { char a = '0'; a += ans[i]-1; System.out.print(a); } else { char a = 'A'; a += (ans[i] - 11); System.out.print(a); } } System.out.println(); } } }