第10回情報オリンピック(JOI)予選
404 · GitHub
今回はJavaで挑んでみた
1
4つの時間(秒)の和を求めて分秒にしなさい。
やるだけ
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int sec = sc.nextInt() + sc.nextInt() + sc.nextInt() + sc.nextInt(); System.out.println(sec/60); System.out.println(sec%60); } }
2
環状文字列のうち与えられた部分文字列を含むものの個数を数えよ。
ここではrotateさせて判定させているが、2回連接にしてindexOfしたほうが速い。反省。
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String s = sc.next(); int n = sc.nextInt(); int cnt = 0; for(int i = 0; i < n; i++) { String r = sc.next(); boolean f = false; for(int j = 0; j < 10; j++) { if(rotate(r,j).startsWith(s)) f=true; } if(f) cnt++; } System.out.println(cnt); } static String rotate(String str, int at) { return str.substring(at) + str.substring(0,at); } }
3
ピラミッドのある位置の高さを3で割った剰余。
上下左右端からの距離のうち最小値が高さとなる。
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int k = sc.nextInt(); for(int i = 0; i < k; i++) { int x = sc.nextInt()-1; int y = sc.nextInt()-1; int z = n-x-1; int w = n-y-1; int m = min(min(x,y),min(z,w)); System.out.println(m%3+1); } } }
4
一桁の整数列を+または-でfoldlして目的の値を作る。途中経過が[0,20]に収まるパターンを数えろ。
典型的なDP。
以下は初項が0のときに爆死する典型コード。(-0+2+4=6のような計算式を数えあげてしまう)
まー4は金メダリスト2人が同じミスしてるししょうがないよねー
http://twitter.com/pon_64/status/16397962607333376
4点失点
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); long[] dp = new long[21]; dp[0] = 1; for(int i = 0; i < n-1; i++) { long[] dp2 = new long[21]; int x = sc.nextInt(); for(int f = 0; f <= 20; f++) { int t = f+x; if(t<=20) dp2[t]+=dp[f]; } for(int f = 0; f <= 20; f++) { int t = f-x; if(0<=t) dp2[t]+=dp[f]; } dp = dp2; } System.out.println(dp[sc.nextInt()]); } }
5
'S'からNまで順番に辿る最短距離を求めよ。
普通のBFS。
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { static Scanner sc = new Scanner(System.in); static final char[] pts = {'S','1','2','3','4','5','6','7','8','9'}; public static void main(String[] args) { int h = sc.nextInt(); int w = sc.nextInt(); int n = sc.nextInt(); StringBuffer mapBuf = new StringBuffer(); for(int y=0; y<h; y++) mapBuf.append(sc.next()); String map = mapBuf.toString(); @SuppressWarnings({"unchecked"}) ArrayList<Integer>[] graph = (ArrayList<Integer>[])new ArrayList[w*h]; for(int i = 0; i < w*h; i++) graph[i]=new ArrayList<Integer>(); for(int x = 0; x < w; x++) { for(int y = 0; y < h; y++) { if(x+1<w) { int a = at(w,x,y); int b = at(w,x+1,y); if(map.charAt(a)!='X' && map.charAt(b)!='X') { graph[a].add(b); graph[b].add(a); } } if(y+1<h) { int a = at(w,x,y); int b = at(w,x,y+1); if(map.charAt(a)!='X' && map.charAt(b)!='X') { graph[a].add(b); graph[b].add(a); } } } } int stepsum = 0; for(int i = 0; i < n; i++) { int start = map.indexOf(pts[i]); int goal = map.indexOf(pts[i+1]); int[] tim = new int[w*h]; for(int j = 0; j < w*h; j++) tim[j]=-1; ArrayDeque<Integer> q = new ArrayDeque<Integer>(); q.add(start); tim[start]=0; while(!q.isEmpty()) { int cur = q.poll(); int curTime = tim[cur]; if(cur == goal) { stepsum += curTime; break; } for(int to : graph[cur]) { if(tim[to]==-1) { q.add(to); tim[to] = curTime+1; } } } } System.out.println(stepsum); } static int at(int w, int x, int y) { return y*w+x; } }
6
J,O,Iの3文字で構成されたN*Mの表を作る。既に文字が決まっているものもある。JOIのロゴを一部分として含むようなものの個数を数えよ。
ビットDP。表を走査順に直列化して、直前のN個の中のどこに「JO」を含むかで2^N通り。
N*M*3*3*2^Nくらい。
import java.util.*; import java.io.*; import static java.lang.Math.*; import static java.util.Arrays.*; public class Main { // I : 0 // O : 1 // J : 2 static final char[] numchar = {'I','O','J'}; static Scanner sc = new Scanner(System.in); static final int MOD = 100000; public static void main(String[] args) { int m = sc.nextInt(); int n = sc.nextInt(); String[] snip = new String[m]; for(int i = 0; i < m; i++) snip[i] = sc.next(); int wholecount = 1; int[][] dp = new int[3][1<<n]; dp[0][0] = 1; for(int y = 0; y < m; y++) { for(int x = 0; x < n; x++) { /* for(int r = 0; r < 3; r++) { for(int p = 0; p < (1<<n); p++) { if(dp[r][p]!=0)System.out.println("("+y+","+x+") ("+numchar[r]+","+p+") : "+dp[r][p]); } } */ int[][] dp2 = new int[3][1<<n]; char cur = snip[y].charAt(x); if(cur=='?') { wholecount=wholecount*3%MOD; } for(int c = 0; c < 3; c++) { if(cur!='?' && cur!=numchar[c]) continue; for(int r = 0; r < 3; r++) { for(int p = 0; p < (1<<n); p++) { int np = p>>1; if(r==2 && c==1 && 0<x) np |= 1<<(n-2); if((p&1)==1 && c==0) continue; dp2[c][np] = (dp2[c][np]+dp[r][p])%MOD; } } } dp = dp2; } } int sum = wholecount; for(int r = 0; r < 3; r++) { for(int p = 0; p < (1<<n); p++) { sum = (sum+MOD-dp[r][p])%MOD; // if(dp[r][p]!=0)System.out.println("("+numchar[r]+","+p+") : "+dp[r][p]); } } System.out.println(sum); } }
