tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 525 Div1

まあ悪くは無いと思います。525だけあってMedium525点だったし。

300:BallsOfWolf
累積和でもとってみた。O(N^3M^3)でも間に合う。

import java.util.*;
public class DropCoins{
	public int getMinimum(String[]a,int b){
		int sum[][]=new int[a.length+1][a[0].length()+1];
		for(int i=1;i<=a.length;i++){
			for(int j=1;j<=a[0].length();j++){
				if(a[i-1].charAt(j-1)=='o')sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+1;
				else sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
			}
		}
		int ret=999999999;
		for(int i=0;i<a.length;i++){
			for(int j=i;j<a.length;j++){
				for(int k=0;k<a[0].length();k++){
					for(int l=k;l<a[0].length();l++){
						if(sum[j+1][l+1]-sum[i][l+1]-sum[j+1][k]+sum[i][k]==b){
							int v=i+a.length-j-1+k+a[0].length()-l-1;
							v+=Math.min(i,a.length-1-j);
							v+=Math.min(k,a[0].length()-1-l);
							ret=Math.min(ret,v);
						}
					}
				}
			}
		}
		if(ret==999999999)return -1;
		return ret;
	}
}

525:WolfRumors
狼が噂を広める問題らしいが、どこにもwolfと書いていなかったので通らない問題だと悟って落とされるためだけに送ってみた。BFSしたが落ちた

950:MonoChromeWolf
図があることだけ知ってます。

Challenge Phase:ながめるだけ
System Test:たくさん落ちてた。みんなの仲間に入れた。300は徹。

Result:
263.78くらいなきがする(218th)
1627 -> 1684

まあこのペースがもっと続いて欲しいんですよね