BottomCoder SRM 367 div2

SRM 367 div2

points result time
250 AC 2.5m
500 AC 2m
1000 WA 17m

1000はケアレスミス・・なのか?どうすればいいんだこれ

250

8*8のチェス盤(左上端は白)が与えられる。このうちいくつかのセルが埋められているとき、埋められているセルのなかで白いセルは何個あるか。

こんな簡単な問題でいいの・・ってかんじの。
偶数行は白セルが偶数番目に出てくるのでそこを調べる。
奇数行は白セルが奇数番目に出てくるのでそこを調べる。

public class WhiteCells {

	public int countOccupied(String[] board) {
		int ct = 0;
		for(int i = 0;i < 8;i++){
			for(int j = i%2==0 ? 0 : 1;j < 8;j += 2){
				if(board[i].charAt(j) == 'F'){
					ct++;
				}
			}
		}
		return ct;
	}

}

500

originalNumber(<=10^50)に対し、ある数(>=0)を加えてそのどれか1桁がkになるとき、加える数の最小値を求めよ。

Javaでやると瞬殺。多倍長を扱えないものではインクリメントによる繰り上がりを実装しないといけないのかな。
1の位のことを考えると、加える数は最大でも9なので、全探索でOK.

import java.math.BigInteger;

public class ObtainingDigitK {

	public int minNumberToAdd(String originalNumber, int k) {
		BigInteger bi = new BigInteger(originalNumber);
		for(int i = 0;i <= 9;i++){
			BigInteger x = bi.add(BigInteger.valueOf(i));
			if(x.toString().indexOf('0'+k) != -1){
				return i;
			}
		}
		return -1;
	}

}

1000

N(<=50)個の区間[offset[i],offset[i]+size[i]) (<=10^9)が与えられる。これはoffset[i]からoffset[i]+size[i]-1までのバイトが埋まっていることを表す。各区間は互いに交わらない。これらを連続したmaxSizeバイトの区間(packet)を使ってすべて覆うとき、必要な区間の最小数を求めよ。

妙な引っかかり方してた。でもDPで解く気にはなれない・・

前のほうから貪欲にpacketを並べて埋めていく。1個1個シミュレートしていると間に合わないのである程度端折る必要がある。
まず区間を前にいる方から順にソートする。次に前から次の操作を行う。埋め始める位置をstartとする。
startからpacketを隙間なく並べていく。この個数はp=[(offset[i]+size[i]-start+(maxSize-1))/maxSize]で求められる。並べたあと、start+p*maxSizeの位置と次の区間の先頭を比べて、後にきている方を次のstartとする。ただしstart

import java.util.Arrays;
import java.util.Comparator;

public class ProgrammingDevice {

	public int minPackets(final int[] offset, int[] size, int maxData) {
		int n = offset.length;
		Integer[] ord = new Integer[n];
		for(int i = 0;i < n;i++){
			ord[i] = i;
		}
		Arrays.sort(ord, new Comparator<Integer>(){
			public int compare(Integer x, Integer y)
			{
				return offset[x] - offset[y];
			}
		});
		
		long cur = offset[ord[0]];
		int ret = 0;
		for(int i = 0;i < n;i++){
			long o = offset[ord[i]];
			cur = Math.max(cur, o); 
			long s = size[ord[i]];
			if(cur < o+s){
				long np = (o+s-cur+maxData-1) / maxData;
				ret += np;
				cur = cur + np*maxData;
			}
		}
		return ret;
	}

}