BottomCoder SRM 395 div2

TopCoder

SRM 395 div2

points result time
250 AC 3.5m
500 AC 10m
1000 AC 11.5m

1000より500のほうが難しかった。

250

0,1,4,9から構成される非負整数のうち、下からn(<=1000)番目は何か。

前に似たような問題でMatsuの解き方にｳﾎｳﾎしたのでそれっぽくやってみた。nを"0,1,4,9"の4進数とみて下の桁からnを解体し数字を構成していく。

import java.util.Arrays;

public class SquareDigitNumbers {

	public int getNumber(int n) {
		int u = 0;
		int mul = 1;
		int[] t = {0,1,4,9};
		for(;n > 0;n /= 4){
			int x = n % 4;
			u += t[x] * mul;
			mul *= 10;
		}
		return u;
	}

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

500

無限に続く格子状の道で、(0,0)から(X,Y)(<=(10^9,10^9))まで行きたい。格子にそって1だけ移動するのにwalkTime(<=10000), 格子の対角線を突っ切って1区画移動するのにsneakTime(<=10000)だけかかるときの最短時間を求めよ。

X,Yがでかいので場合分け的になる問題。
まず、sneakTime >= walkTime*2のときは、どうやってもwalkのほうが効率いいので、全部歩く。
次に、sneakTime < walkTime*2で、sneakTime>=walkTimeのときは、斜めに動くときだけsneakのほうが効率が良い。(X,Y)への移動を斜めずばーっとsneakしたあとどっちかの軸に平行になったらあとはwalk、という戦術が最適。
最後に、sneakTime < walkTimeのときは、ただまっすぐwalk*2するよりもジグザグにsneak*2したほうが速いという(クレイジーな)ことになる。つまり、上述でのあとはwalkのところをsneakにして高速化できる。ただし、あくまでwalk*2→sneak*2の変換しかできないので、walk*1だけ残ったらそこは歩くしかない。(最後のsampleがここをつついてくるけど、なかったらWAくらってた・・)

import java.util.Arrays;

public class StreetWalking {

	public long minTime(int X, int Y, int walkTime, int sneakTime) {
		if(sneakTime < walkTime * 2){
			int min = Math.min(X,Y);
			if(sneakTime < walkTime){
				if(((X-min)+(Y-min)) % 2 == 0){
					return ((long)min+(X-min)+(Y-min)) * sneakTime;
				}else{
					return ((long)min+(X-min)+(Y-min)-1) * sneakTime + walkTime;
				}
			}
			return (long)min * sneakTime + (long)((X-min)+(Y-min)) * walkTime;
		}
		return (long)(X+Y)*walkTime;
	}

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

1000

N問のクイズが順に出題される。各問題(i)には正解したときpoints[i]点がもらえ、不正解したときpoints[i]点がボッシュートされる。また、正解したときのみtokenがもらえ(これは不正解の時は何もおこらない)、これをtokensNeeded個集めたときに、tokenすべてと引き換えにbonus[i]点がもらえる。各問題の正解・不正解を自由に決められるとき、もらえる最大の点数を答えよ。

典型DP. dp[今までの問題数][tokenの個数]=(最大ポイント)として漸化式は以下。
tokenの個数=jが0以外になるときは、j-1個から正解した場合とj個から不正解した場合なので、
dp[i][j]=max(dp[i-1][j-1]+points[i-1], dp[i-1][j]-points[i-1]),
j=0になるときは、tokenNeeded-1個から正解した場合(ボーナスももらう)と、0個から不正解した場合なので、
dp[i][j]=max(dp[i-1][tokenNeeded-1]+points[i-1]+bonus[i-1], dp[i-1][j]-points[i-1])
で、最後にdp[n][*]のうちの最大値を求めればOK.
(dp[0]を初期値にしているので1個ずつずれてる)

import java.util.Arrays;

public class TriviaGame {

	public int maximumScore(int[] points, int tokensNeeded, int[] bonuses) {
		int n = points.length;
		int[][] dp = new int[n+1][tokensNeeded];
		Arrays.fill(dp[0], -10000000);
		dp[0][0] = 0;
		for(int i = 1;i <= n;i++){
			for(int j = 0;j < tokensNeeded;j++){
				if(j == 0){
					dp[i][j] = Math.max(dp[i-1][j] - points[i-1], dp[i-1][tokensNeeded-1] + points[i-1] + bonuses[i-1]);
				}else{
					dp[i][j] = Math.max(dp[i-1][j] - points[i-1], dp[i-1][j-1] + points[i-1]);
				}
			}
		}
		
		int max = 0;
		for(int i = 0;i < tokensNeeded;i++){
			max = Math.max(max, dp[n][i]);
		}
		return max;
	}

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