BottomCoder SRM 382 div2
| points | result | time |
|---|---|---|
| 250 | AC | 5.5m |
| 500 | AC | 13.5m |
| 1000 | AC | 17.5m |
250
N(<=50)項の数列a(0<=*<=1000000)がある。このうち、a[i]ではじまり[j]で終わる連続したj-i+1項について、j-i+1>=K(<=|A|)であるもののうち、j-i+1項の平均が最大となるような(i,j)を求めよ。平均が等しくなる場合は、j-i+1がより大きいものを選べ。
平均を求めるときにdoubleになるので誤差処理が必要？あとは普通に全探索でOK.ちなみに1000000*50*50は2^31より大きいので、Javaで無理してintでやろうとすると死ぬ。
public class ContiguousSubsequences { public int[] findMaxAverage(int[] a, int K) { int n = a.length; int maxn = 0; double maxa = 0; int maxi = 0; double EPS = 1E-7; for(int i = 0;i < n;i++){ for(int j = i + K - 1;j < n;j++){ int sum = 0; for(int k = i;k <= j;k++){ sum += a[k]; } double ave = (double)sum / (j-i+1); if(ave > maxa + EPS || (Math.abs(ave - maxa) < EPS && maxn < j-i+1)){ maxa = ave; maxn = j-i+1; maxi = i; } } } return new int[]{maxi, maxi+maxn-1}; } }
500
N*M(<=10*10)のチェス盤の上にK-riderが何個か置いてある。K-riderは、1手でknightの動きをK回以下できる駒である。駒が同一マスにあっても問題ないとするとき、盤上のすべてのK-riderが一点に集まるために必要な手数を答えよ。そのようなことができない場合は-1を返せ。
N*Mが小さいので解き方に自由がきく。
1個のK-riderについて、全てのマスに最短何手でいけるかを計算する。knightの動きでM手でいけたとき、K-riderとしては[(M+K-1)/K]手でいける。MはBFSで列挙すればO((NM)^2)でできる。行けないところは-1をつけておく。
そして、全てのK-riderについて、全てのマスへの最短手数をマスごとに合計する。-1が一つでも混じっていたらそこは-1とし、無効扱いにする。最短手数の合計の全てのマスでの最小値が答え。全て-1だったら-1を返す。
import java.util.concurrent.ArrayBlockingQueue; public class CollectingRiders { public int minimalMoves(String[] board) { int n = board.length; int m = board[0].length(); char[][] b = new char[n][m]; for(int i = 0;i < n;i++){ b[i] = board[i].toCharArray(); } int[] dr = {2, 1, -1, -2, -2, -1, 1, 2}; int[] dc = {1, 2, 2, 1, -1, -2, -2, -1}; int[][] maxb = new int[n][m]; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(b[i][j] >= '0' && b[i][j] <= '9'){ int k = b[i][j] - '0'; int[][] bb = new int[n][m]; ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(150); q.add(i*m+j); bb[i][j] = 1; while(!q.isEmpty()){ int cur = q.poll(); int r = cur/m; int c = cur%m; for(int l = 0;l < 8;l++){ int nr = r + dr[l]; int nc = c + dc[l]; if(nr >= 0 && nr < n && nc >= 0 && nc < m && bb[nr][nc] == 0){ bb[nr][nc] = bb[r][c] + 1; q.add(nr*m+nc); } } } for(int u = 0;u < n;u++){ for(int v = 0;v < m;v++){ if(maxb[u][v] != -1){ if(bb[u][v] == 0){ maxb[u][v] = -1; }else{ maxb[u][v] += (bb[u][v]-1+k-1)/k; } } } } } } } int min = 9999999; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(maxb[i][j] != -1)min = Math.min(min, maxb[i][j]); } } return min == 9999999 ? -1 : min; } }
1000
2K(K<=50)個の、goodにかかれた数字からなる数字列がある。このうち次の性質のいずれかを満たすものは何通りあるか。999983で割った余りを答えよ。
- 前半のK個と後半のK個の数の合計が等しい。
- 奇数番目の項の和と偶数番目の項の和が等しい。
条件1をC1, 条件2をC2、条件Cを満たす数列の個数を#Cと表すと、
#C1+#C2-#(C1∧C2)
を求めれば良い。
goodにある数字からなるK個の数字の和がSであるようなK個の数字の組み合わせをm(K,S)とする。これ自体はDPで求められる。dp[i][j]=m(i,j)として、dp[i][j]=\sum_{k in good} dp[i-1][j-k]
とすればよい。
C1は、ある合計Sについて、前半のK個の和がS, 後半のK個の和がSになればいいので、
#C1=\sum_S m(K,S)^2
となる。Sの範囲はは0以上9*50=450以下。#C2も全く同じ値になる。
#(C1∧C2)を計算する。まずKが偶数のとき、前半で奇数番目にある項の数はK/2個、他、前半偶数番目、後半奇数番目、後半偶数番目もK/2個である。前半K個の和をS, 前半奇数番目の項の合計をAとするとき、条件1,2のどちらもみたすので、奇数・偶数番目の項の和もS. そして、条件1より、前半偶数番目の項の和はS-A, 条件2より後半奇数番目の項の和はS-A, 後半偶数番目の項の和はA. よって、
#(C1∧C2)=\sum_S \sum_A (m(K/2,A)m(K/2,S-A))^2
となる。Kが奇数の場合は、前半奇数番目、後半偶数番目の項の数が[K/2]+1になるだけなので、結局、
#(C1∧C2)=\sum_S \sum_A (m(K/2+K%2,A)m(K/2,S-A))^2
となる。あとは計算すれば求まる。
public class CharmingTicketsEasy { int MOD = 999983; public int count(int K, String good) { int fl = 0; for(int i = 0;i < good.length();i++){ fl |= 1<<(good.charAt(i) - '0'); } // K:odd K/2+1, K/2 // K:even K/2 int[][] dp = new int[K+1][451]; dp[0][0] = 1; for(int i = 1;i < K+1;i++){ for(int j = 0;j <= 450;j++){ int sum = 0; for(int k = 0;k <= 9;k++){ if((fl&1<<k)!=0 && j-k >= 0){ sum += dp[i-1][j-k]; } } dp[i][j] = sum % MOD; } } long one = 0; for(int ks = 0;ks <= 450;ks++){ one += ((long)dp[K][ks] * (long)dp[K][ks]) % MOD; } long inter = 0; for(int ks = 0;ks <= 450;ks++){ for(int a = 0;a <= ks;a++){ long uho = ((long)dp[K/2+(K%2)][a] * dp[K/2][ks-a]) % MOD; inter += (uho * uho) % MOD; } } return (int)((((one*2-inter) % MOD)+MOD)%MOD); } }
