BottomCoder SRM 388 div2

SRM 388 div2

points	result	time
250	AC	2.8m
500	AC	8m
1000	AC	4.8m

やたら簡単だった今回。撃墜祭り。
最初500をひらいてしまってテンパッた。

250

与えられた数列(||<=50)の、連続した狭義単調増加or減少部分列の最大の長さを求めよ。

規模が小さいので、O(N^2)の方法でも余裕。部分列の頭を選んでできるだけ長く追う。
O(N)でもできる。

import java.util.Arrays;

public class MonotoneSequence {
	public int longestMonotoneSequence(int[] seq) {
		int n = seq.length;
		int max = 0;
		for(int i = 0;i < n;i++){
			{
				int j;
				for(j = i + 1;j < n;j++){
					if(seq[j] - seq[j-1] >= 0){
						break;
					}
				}
				max = Math.max(max, j - i);
			}
			{
				int j;
				for(j = i + 1;j < n;j++){
					if(seq[j] - seq[j-1] <= 0){
						break;
					}
				}
				max = Math.max(max, j - i);
			}
		}
		return max;
	}

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

500

それぞれの候補者(||<=50)への票数(<=100)が与えられる。自分(0)以外の候補者への投票者に賄賂を送って、自分に投票するようにする。他の候補者よりも得票数が多いと当選になるとき、最低何人に賄賂を送ればよいか。

k(0から昇順で走査)人に賄賂を送るとして、votes[0]+k票よりも他の人の得票数が少なければよいので、votes[0]+k以上になっている票をぜんぶ削る。削った合計がkより小さくなったらそのkが答え。削った票は単調減少なので2分探索も可だが、小さすぎるのでやる必要がない。

テンパって何故か得票数の2分探索で書いてしまった。こっちの方針は2分探索だけでは決まらず少々めんどくなる。

import java.util.Arrays;

public class VoteRigging {
	public int minimumVotes(int[] votes)
	{
		for(int i = 0;i < 999;i++){
			int self = votes[0] + i;
			int sum = 0;
			for(int j = 1;j < votes.length;j++){
				if(self <= votes[j]){
					sum += votes[j] - self + 1;
				}
			}
			if(i >= sum){
				return i;
			}
		}
		return 0;
	}

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

テンパッた結果

import java.util.Arrays;

public class VoteRigging {
	public int minimumVotes(int[] votes) {
		int start = 0;
		int end = 100;
		while(end - start > 1){
			int mid = (end+start)/2;
			int sum = 0;
			for(int i = 1;i < votes.length;i++){
				if(mid < votes[i]){
					sum += votes[i] - mid;
				}
			}
			int self = votes[0] + sum;
			if(self > mid){
				start = mid;
			}else{
				end = mid;
			}
		}
		
		int last = 0;
		for(int i = 1;i < votes.length;i++){
			if(start < votes[i]){
				last += votes[i] - start;
			}
		}
		int se = votes[0] + last;
		
		return last - Math.max(se - (start+2), 0);
	}

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

1000

k(<=1000)以下の素因数だけからなる数をk-smoothという。N(<=5000000)以下のk-smoothな自然数の個数を求めよ。

kまでの素数を求めて、順にS={1}の各要素に{p, p^2, p^3,...}を掛けていくようなことをすれば良い。最後に|S|を求めればOK.
実装上では、Sをbitで管理して、下からbitが立っているところがあればそれにpをかけたbitを立てることを繰り返すだけでよい。

オーダーは・・pをかけた結果は高々5000000通り(被らない)で、多めに見ても10^7なのでいける。(実際は1200000ぐらいしかまわってない)

import java.util.Arrays;
import java.util.BitSet;

public class SmoothNumbersHard {
	public int countSmoothNumbers(int N, int k) {
		BitSet ps = new BitSet();
		BitSet smooth = new BitSet();
		ps.set(2, k+1);
		smooth.set(1);
		for(int p = 2;p <= k;p++){
			if(ps.get(p)){
				for(int i = p * 2;i <= k;i += p){
					ps.clear(i);
				}
				for(int i = smooth.nextSetBit(0);i != -1;i = smooth.nextSetBit(i+1)){
					if(i * p <= N){
						smooth.set(i * p);
					}else{
						break;
					}
				}
			}
		}
		return smooth.cardinality();
	}

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