BottomCoder SRM 369 div2

TopCoder

SRM 369 div2

points result time
250 AC 4.7m
500 WA
1000 AC 17.1m

あああ500みたいな問題苦手だ・・どうすればひらめくんだろう

250

配列width, height, color(||<=50)が与えられる。width[i]*height[i]の長方形をcolor[i]で塗る。i>=1なら、i-1番目の長方形の内部に長方形を塗る。このとき、RGB各色の占める面積のうち最大のものを求めよ。

微妙にいやらしい問題。面積を求める対象の色をC、それ以外の色をEとすると、配列の頭から走査して、現在の色がCで(直前の色がEまたは現在が先頭)の場合は、面積をプラス。現在の色がEで直前の色がCの場合は、面積をマイナス、とすればよい。

面積の差だけに着目すればもっと楽に書けたかも・・まあいいか

import java.util.Arrays;

public class ChainOfRectangles {
	public int getMaximalArea(int[] width, int[] height, String color) {
		int n = width.length;
		int max = 0;
		for(char c : "RGB".toCharArray()){
			int sum = 0;
			for(int i = 0;i < n;i++){
				if((i == 0 || color.charAt(i-1) != c) && color.charAt(i) == c){
					sum += width[i] * height[i];
				}
				if((i-1 >= 0 && color.charAt(i-1) == c) && color.charAt(i) != c){
					sum -= width[i] * height[i];
				}
			}
			max = Math.max(max, sum);
		}
		return max;
	}

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

500

次の条件をすべて満たす'A','B'だけからなる文字列の最大長を求めよ。
countA(0<=*<=10^6)個以下の'A'が入っている。
countB(0<=*<=10^6)個以下の'B'が入っている。
連続している'A'の個数はmaxA(0<=*<=10^6)以下。
連続している'B'の個数はmaxB(0<=*<=10^6)以下。

最大ばかり追って小さい塊で区切る場合を完全に外してた・・
まじめにかんがえるとめっさめんどい・・自分の考え方と、最適？な解き方を書く。どちらも、maxA=0 or maxB=0の場合は先に場合分けしておく。

使うAの個数をlA, Bの個数をlBとする。maximize lA+lB. あるcを考えて、Aのかたまりがc+1個の間にBがc個といったふうにすると, (A,B)=(c+1,c),(c,c+1),(c,c)が考えられる。最初の場合だと、
c+1<=lA<=(c+1)maxA かつ c<=lB<=c*maxB かつ lA<=countA, lB<=countB. 最大をとればいいので、lA=min(countA, (c+1)maxA)として、lA>=c+1をみたしていればよい。同様をlBについてもやって、両方満たしていればlA+lBが最大候補となる。これを0<=c<=10^6で行う。

次に最適な方法。A,Bどちらかは必ず全部使う。Aを全部使うとすると、Aを1個ずつ細切れにした間にBを突っ込むのがBを最大限収められる方法で、これは(countA+1)*maxB個まで収められる。これとcountBとの最小値をとればよい。同じことをBとAを交換してもやって、最大のほうを答えとする。

A,Bどちらかは必ず全部使う。ということになぜ気づかないのだろう・・はぁ

import java.util.Arrays;

public class BeautifulString {
	public int maximumLength(int countA, int countB, int maxA, int maxB) {
		if(maxA == 0 && maxB == 0)return 0;
		if(maxA == 0){
			return Math.min(maxB, countB);
		}
		if(maxB == 0){
			return Math.min(maxA, countA);
		}
		
		int max = 0;
		for(long c = 0;c <= 1000000;c++){
			{
				long la = Math.min(countA, c * maxA);
				long lb = Math.min(countB, c * maxB);
				if(la >= c && lb >= c){
					max = (int)Math.max(max, la + lb);
				}
			}
			{
				long la = Math.min(countA, (c+1) * maxA);
				long lb = Math.min(countB, c * maxB);
				if(la >= c+1 && lb >= c){
					max = (int)Math.max(max, la + lb);
				}
			}
			{
				long la = Math.min(countA, c * maxA);
				long lb = Math.min(countB, (c+1) * maxB);
				if(la >= c && lb >= c+1){
					max = (int)Math.max(max, la + lb);
				}
			}
		}
		return max;
	}

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

1000

正N(<=50)角形をN-3本の互いに端点以外で交わらない対角線で分割する。このときできるN-2本の三角形のうち、二等辺三角形がK個あるような分割の仕方は何通りあるか。

SRM406とどこか似たような問題だとおもったのでとりあえず区間DPったらあっさり解けた。まるでどこかからコピペしたかのような綺麗なコードに・・

連続するM本の辺からなる区間を考える。正N角形の一部なので、どこからとってきても性質はかわらない。dp[M][T]を、このM本の辺+端をつなぐ対角線からなる多角形(P_M)を分割したときのT個の二等辺三角形が現れる分割の仕方とする。
区間の端からi個目(i=1〜M-1)の頂点を考えて、両端からそこへ対角線をひくと、P_iとP_{M-i}と、円周長がi:M-i:N-Mの三角形(R)に分かれる。
正n角形の頂点からなる三角形では、正n角形の外接円を考えると弧長->三角形の辺の長さに対応していて、N-x,xがそれぞれ同じ値に写る。三角不等式より比較してもしょうがないのを除くと、i==M-i || i==N-M || M-i==N-Mであればその三角形は二等辺三角形となる。
よって、f(i)=(Rが二等辺三角形かどうか?1:0)とすると、
dp[M][T]=\sum_i \sum_j dp[i][j]*dp[M-i][T-f(i)-j]となる。
こうしてDPしていって、最後はdp[N-1][K]を求めれば良い。dp[N][k]じゃないのがミソ。

import java.util.Arrays;

public class IsoscelesTriangulations {
	int MOD = 123456789;
	public int getCount(int n, int k) {
		long[][] dp = new long[n+1][k+1];
		dp[1][0] = 1;
		for(int i = 2;i <= n-1;i++){
			for(int j = 1;j < i;j++){
				boolean iso = i-j == j || j == n-i || n-i == i-j;
				
				for(int l = 0;l <= k;l++){
					for(int m = 0;l+m+(iso?1:0) <= k;m++){
						dp[i][l+m+(iso?1:0)] += dp[j][l] * dp[i-j][m];
						dp[i][l+m+(iso?1:0)] %= MOD;
					}
				}
			}
		}
		
		return (int)dp[n-1][k];
	}

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