BottomCoder SRM 384 div2

SRM 384 div2

points	result	time
250	AC	5.5m
500	AC	6.3m
1000	AC	21m

罠っぽい気がしたけどそんなことはなかった。

250

妹がapparentGain(<=100000)だけ太ったみたい。妹の体重がxからyに変化してy^2-x^2=apparentGainが成り立つときyの候補を列挙せよ。x,yは1以上の整数とする。(意訳)

100000以下なので、yを走査して、個別にxを求めに行っても間に合う。

お利口にやると、y^2-x^2=aから(y-x)(y+x)=a, aの約数dにたいして、y-x=d, y+x=a/dなので、
y=(d+a/d)/2, x=(d-a/d)/2となる。dを列挙して、x>0、つまりd^2>aとなるようなdについて、(d+a/d)/2のうち整数となるものを列挙すればよい。

import java.util.Arrays;

public class Prank {
	public int[] realWeight(int apparentGain) {
		int[] q = new int[50001];
		int p = 0;
		
		for(int i = (int)Math.ceil(Math.sqrt(apparentGain));i <= 50001;i++){
			long di = (long)i * i - apparentGain;
			if(di == 0)continue;
			long sq = (long)Math.sqrt(di);
			if(sq * sq == di){
				q[p++] = i;
			}
		}
		int[] ret = new int[p];
		for(int i = 0;i < p;i++){
			ret[i] = q[i];
		}
		return ret;
	}
}

お利口なやり方

import java.util.Arrays;

public class Prank {
	public int[] realWeight(int apparentGain)
	{
		int[] q = new int[50001];
		int p = 0;
		for(int i = 1;i * i < apparentGain;i++){
			if(apparentGain % i == 0){
				int dg = i + apparentGain / i;
				if(dg % 2 == 0){
					q[p++] = dg/2;
				}
			}
		}
		int[] ret = new int[p];
		for(int i = 0;i < p;i++){
			ret[i] = q[i];
		}
		Arrays.sort(ret);
		return ret;
	}

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

500

文書(||<=50)は、(文書, 部屋, ユーザーグループ)の組で管理されていて、該当する部屋(||<=50)に入れて、ユーザーグループ(||<=50)に属していなければ手に入れられない。また、異なる組でも名前が同じなら同じ文書、部屋、ユーザーグループである。入れる部屋の一覧と属しているユーザーグループが与えられたとき、手に入れられる文書の個数を求めよ。

なんか罠があるんじゃないかなとおもったけどそんなことはなかった。
HashSetを使ってしこしこ仕分けすれば良い。

import java.util.Arrays;
import java.util.HashSet;

public class Library {
	public int documentAccess(String[] records, String[] userGroups, String[] roomRights) {
		int n = records.length;
		HashSet<String> set = new HashSet<String>();
		for(int i = 0;i < n;i++){
			String[] sp = records[i].split(" ");
			boolean uin = false;
			boolean rin = false;
			for(int j = 0;j < userGroups.length;j++){
				if(userGroups[j].equals(sp[2])){
					uin = true;
					break;
				}
			}
			for(int j = 0;j < roomRights.length;j++){
				if(roomRights[j].equals(sp[1])){
					rin = true;
					break;
				}
			}
			if(uin && rin){
				set.add(sp[0]);
			}
		}
		return set.size();
	}

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

1000

Alanが先攻、Bobが後攻でゲームをする。2つのpileにstick(<=10000)が刺さっていてそれぞれ、ふたつのpileからそれぞれ平方数個(>=1)のstickを取り除く(同数でなくてもよい)。取り除けなくなったら負けとする。必勝の場合は最短で終わるように、必敗の場合は最長で終わるようにするとき、どちらが何手で勝つかを出力せよ。

一瞬メモ化再帰でもできるんじゃないかなと思わせるような制約。
pileを選んで除くわけではなく同時に除くため、pileそれぞれでゲームを進行できる。dp[i]=(pileにi個stickが刺さっているときの最適手数)とすると、この値が偶数のときは後手勝利(必敗)で、奇数のときは先手勝利(必勝)である。
dp[i-j*j]のなかで、必敗のものがひとつでもあれば、そうするようなdp[i-j*j]のうち最小のものを選んで(最短で終わるように)、+1したものをdp[i]とする。ひとつもなければ、dp[i-j*j]の最大値を選んで(最長で終わるように)、+1したものをdp[i]とする。
最後に、2つのpileに刺さっているstick[0],stick[1]のうち、dp[stick[0]],dp[stick[1]]が小さいほうが最適手数となる。

必敗を0以下にしていた当初書いたバージョン

import java.util.Arrays;

public class PowerGame {
	public String winner(int size0, int size1) {
		int[] tree = new int[10001];
		for(int i = 1;i <= 10000;i++){
			int opt = -999999;
			int opt2 = 0;
			for(int j = 1;j * j <= i;j++){
				if(tree[i-j*j] <= 0){
					opt = Math.max(opt, tree[i-j*j]);
				}else{
					opt2 = Math.max(opt2, tree[i-j*j]);
				}
			}
			if(opt == -999999){
				tree[i] = -opt2-1;
			}else{
				// win
				tree[i] = -opt+1;
			}
		}
		
		boolean alan = true;
		int num = -1;
		if(tree[size0] > 0 && tree[size1] > 0){
			alan = true; num = Math.min(tree[size0], tree[size1]);
		}else if(tree[size0] <= 0 && tree[size1] <= 0){
			alan = false; num = Math.min(-tree[size0], -tree[size1]);
		}else if(tree[size0] > 0 && tree[size1] <= 0){
			if(tree[size0] > -tree[size1]){
				alan = false; num = -tree[size1];
			}else{
				alan = true; num = tree[size0];
			}
		}else if(tree[size1] > 0 && tree[size0] <= 0){
			if(tree[size1] > -tree[size0]){
				alan = false; num = -tree[size0];
			}else{
				alan = true; num = tree[size1];
			}
		}
		return (alan?"Alan":"Bob") + " will win after " + num + " moves";
	}

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

@y3eadgbeのやり方に感銘して書きなおしたバージョン。こっちのほうがすっきり。

import java.util.Arrays;

public class PowerGame {
	public String winner(int size0, int size1) {
		int[] tree = new int[10001];
		for(int i = 1;i <= 10000;i++){
			int opt = 999999;
			int opt2 = 0;
			for(int j = 1;j * j <= i;j++){
				if(tree[i-j*j]%2==0){
					opt = Math.min(opt, tree[i-j*j]);
				}else{
					opt2 = Math.max(opt2, tree[i-j*j]);
				}
			}
			if(opt == 999999){
				tree[i] = opt2+1;
			}else{
				tree[i] = opt+1;
			}
		}
		
		int min = Math.min(tree[size0], tree[size1]);
		return (min%2==1?"Alan":"Bob") + " will win after " + min + " moves";
	}

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