BottomCoder SRM 377 div2

points	result	time
250	AC(resubmit)	5m
500	AC	5m
1000	WA	30m

Problem Archiveには載っていない幻の回。
そして数学回。

SRM378はまだhardが解けてないので載せてないです。

250

素数でなく、1以外の素因数はすべて11以上であるような数のうち、m(<=10^6)より大きい最小の数を求めよ。

div2easyでオーダー考えるような問題は出ないので、おそらく愚直に素因数を探せばいいと考えてコーディング。
m+1以上の各数iについて、まずiに2,3,5,7の素因数がないかどうか調べる。これらがなければ、次は素数かどうか調べる。√i以下の数で割り切れたら非素数。こうして非素数になっていればそのiが答え。

resubmitは、iの上限を10^6にしてしまって(ry. ちなみにm=10^6だと答えは1000001になる。

import java.util.Arrays;

public class AlmostPrimeNumbers {
	public int getNext(int m) {
		outer:
		for(int i = m+1;i < 1000009;i++){
			for(int p = 2;p <= 7;p++){
				if(i % p == 0){
					continue outer;
				}
			}
			for(int p = 11;p * p <= i;p+=2){
				if(i % p == 0){
					return i;
				}
			}
		}
		return 0;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

500

(0〜width)*(0〜height) (<=10^5*10^5)の格子がある。この格子点を頂点とする正方形は何個あるか。

テラ算数。制約から考えて、O(N)あたりでないといけない。
斜めの正方形を考える。これをすっぽり覆う格子に平行な辺でできた正方形が必ず存在する。この覆う正方形と斜めの正方形は、一方が格子内に存在すれば他方も必ず存在する。よって、斜めの正方形の個数はそれを覆う正方形の個数と等しい。結局、格子に平行な辺でできた正方形のみの個数を数えれば良いことになる。
正方形の辺の長さをdとすると、その個数は(width-d+1)*(height-d+1)となる。斜めの正方形は、その最も高いところにある頂点が、dの正方形の一番上の辺の格子点のどこかに対応するので、正方形1個に対しd-1個存在する。よって答えは
\sum_{1<=d<=min(width,height)} (width-d+1)(height-d+1)d.

これはdの3次式なので、n乗和の公式を使ってO(1)にもできる。

import java.util.Arrays;

public class SquaresInsideLattice {
	public long howMany(int width, int height) {
		long sum = 0;
		for(int i = 1;i <= Math.min(width, height);i++){
			sum += (long)(width-i+1)*(height-i+1)*i;
		}
		return sum;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

1000

無向グラフの体をした無向2部グラフ(||+||<=50)が与えられる。一方は黒い頂点からなり、もう一方は白い頂点からなる。また各頂点には値(mark)が乗っている。ここからN(<=10^9)ターン(1-base)、次の操作を行う。N回行った後の各頂点のmark%(10^9+7)を求めよ。(意訳)

奇数ターンでは、すべての黒い頂点について、隣り合った白い頂点のmarkの合計を、その頂点のmarkとする。
偶数ターンでは、すべての白い頂点について、隣り合った黒い頂点のmarkの合計を、その頂点のmarkとする。

行列の問題。wtobを奇数ターンでの遷移行列、btowを偶数ターンでの遷移行列とする。
wtob[i]は、頂点iが白ならwtob[i][i]のみ1で他は0, 黒なら隣り合った白い頂点jについてwtob[i][j]=1, 他は0.となる。btowはこの逆。
wtow:=btow*wtobとし、vを与えられたmarkのベクトルとする。最終的には
(N%2==1?wtob:I)*(wtow)^(N/2)*v
を求めれば良い。正方行列のn乗は、サイズをMとするとO(M^3*lg n)なのでぎりぎり間に合う。

本番ではblackとwhiteに頂点を分けてしまったおかげで煩雑な場合分けをしなければいけなくなってそれで死んだ。別に分けなくても良かった。あとMODを10^9+9と間違えたのとmul中でoverflowしてた。どうでもいいですね！

import java.util.Arrays;

public class GameOnAGraph {
	public int[] getMarks(String[] adj, String colors, String marks, int N) {
		int m = adj.length;
		
		int[][] wtob = new int[m][m];
		for(int i = 0;i < m;i++){
			if(colors.charAt(i) == 'W'){
				wtob[i][i] = 1;
			}else{
				for(int j = 0;j < m;j++){
					wtob[i][j] = adj[j].charAt(i) - '0';
				}
			}
		}
		int[][] btow = new int[m][m];
		for(int i = 0;i < m;i++){
			if(colors.charAt(i) == 'B'){
				btow[i][i] = 1;
			}else{
				for(int j = 0;j < m;j++){
					btow[i][j] = adj[j].charAt(i) - '0';
				}
			}
		}
		
		int[] v = new int[m];
		for(int i = 0;i < m;i++){
			v[i] = marks.charAt(i)-'0';
		}
		int[][] wtow = mul(btow, wtob);
		
		int nm = N / 2;
		for(;nm > 0;nm >>= 1){
			if(nm % 2 == 1){
				v = mul(wtow, v);
			}
			wtow = mul(wtow, wtow);
		}
		if(N % 2 == 1){
			v = mul(wtob, v);
		}
		
		return v;
	}

	static int MOD = 1000000007;
	
	public static int[][] mul(int[][] A, int[][] B)
	{
		int m = A.length;
		int n = A[0].length;
		int o = B[0].length;
		int[][] C = new int[m][o];
		for(int i = 0;i < m;i++){
			for(int j = 0;j < o;j++){
				long sum = 0;
				for(int k = 0;k < n;k++){
					sum += (long)A[i][k] * B[k][j];
					sum %= MOD;
				}
				C[i][j] = (int)(sum % MOD);
			}
		}
		return C;
	}
	
	public static int[] mul(int[][] A, int[] v)
	{
		int m = A.length;
		int n = v.length;
		int[] w = new int[m];
		for(int i = 0;i < m;i++){
			long sum = 0;
			for(int k = 0;k < n;k++){
				sum += (long)A[i][k] * v[k];
				sum %= MOD;
			}
			w[i] = (int)(sum % MOD);
		}
		return w;
	}
	
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}