BottomCoder SRM 396 div2

SRM 396 div2

points	result	time
250	AC	10m(frozen)
500		AC	5m
1000	WA	31m

250

各桁が0〜9からなるn(<=50)桁の番号が与えられる。nが偶数のときは奇数番目の桁を2倍し、すべての桁の合計を出す。nが奇数のときは偶数番目の桁を2倍し、同様に合計を出す。この合計が10の倍数だったらVALID, そうでなければINVALIDを返せ。

実装ゲー。桁の合計は、2倍したあとの数が14だったら+5になるとかいうことに注意すれば簡単。

import java.util.Arrays;

public class VerifyCreditCard {

	public String checkDigits(String cardNumber) {
		int sum = 0;
		int n = cardNumber.length();
		for(int i = 0;i < n;i++){
			if((i ^ n) % 2 == 0){
				sum += sd((cardNumber.charAt(i) - '0') * 2);
			}else{
				sum += sd((cardNumber.charAt(i) - '0'));
			}
		}
		return sum % 10 == 0 ? "VALID" : "INVALID";
	}
	
	int sd(int n)
	{
		int sum = 0;
		for(;n > 0;n /= 10)sum += (n % 10);
		return sum;
	}

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

500

A,T,C,Gからなる文字列(||<=2500)が与えられる。この文字列の文字を置換して、周期的な文字列にしたい。周期maxPeriod以下にする場合、置換する文字の最小数を求めよ。

ぎりぎり全探索でいける。周期iのとき、i文字おきにとった文字の集合のうち、一番頻度の高いものに置換すれば最小になるので、(集合の要素数-最大頻度数)を、iの剰余類のi個の集合について求めて合計すればよい。
コードではctの定義が128で2500^2*128が結構やばい値になるが、最大ケースでも1秒ちょいだったので直さずにおいた。要素数4の配列にしておくのが無難。

import java.util.Arrays;

public class DNAString {

	public int minChanges(int maxPeriod, String[] dna) {
		StringBuilder sb = new StringBuilder();
		for(String s : dna)sb.append(s);
		char[] str = sb.toString().toCharArray();
		int n = str.length;
		char[] atcg = "ATCG".toCharArray();
		int min = 99999;
		for(int i = maxPeriod;i >= 1;i--){
			int x = 0;
			for(int j = 0;j < i;j++){
				int[] ct = new int[128];
				int sum = 0;
				for(int k = j;k < n;k += i){
					ct[str[k]]++;
					sum++;
				}
				int max = 0;
				for(char c : atcg){
					max = Math.max(max, ct[c]);
				}
				x += sum - max;
			}
			min = Math.min(min, x);
		}
		
		return min;
	}

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

1000

数字列number(||<=50)から、数字列digits(||<=50)にある数字をdigitsにある個数分だけ消してできる最大の数(数字列)を求めよ。

貪欲法。まずdigitsの数字をカウントしてもっておく。numberの前の方から1文字見ては該当するカウントをデクリメントして、デクリメントできなくなる数字まで到達したら、それまでのなかで最大で、かつそれを残してもカウントに余裕が残っているような数字Mを結果文字列に追加する。次はMの次の位置にカウントを戻し、同じことを繰り返す。こうすると左のほうから大きい数字が割り当てられるような気がするけど厳密な証明はよくわからない。

どうやろうか迷って時間を食った。WAだったが、原因はif(num[j] == num[i]){のところを == num[pos]と書いてただけの馬鹿でした。コードは少し冗長だが、O(N^3)でも余裕で通るのでリファクタリングしてない。

import java.util.Arrays;

public class RemovingDigits {

	public String maxNumber(String number, String digits) {
		int[] ct = new int[10];
		for(int i = 0;i < digits.length();i++){
			ct[digits.charAt(i) - '0']++;
		}
		char[] num = number.toCharArray();
		int n = num.length;
		int[] nct = new int[10];
		for(int i = 0;i < n;i++){
			nct[num[i] - '0']++;
		}
		
		int[] xct = new int[10];
		for(int i = 0;i < 10;i++)xct[i] = ct[i];
		StringBuilder sb = new StringBuilder();
		int pos = 0;
		for(;pos < n;pos++){
			int[] imp = new int[10];
			int max = 0;
			int maxi = -1;
			for(int i = pos;i < n;i++){
				int lct = 0;
				for(int j = i;j < n;j++){
					if(num[j] == num[i]){
						lct++;
					}
				}
				if(lct > xct[num[i]-'0'] && max < num[i]-'0'){
					max = num[i]-'0';
					maxi = i;
					for(int j = 0;j < 10;j++)imp[j] = xct[j];
				}
				if(xct[num[i]-'0'] == 0){
					break;
				}
				xct[num[i]-'0']--;
			}
			sb.append(max);
			xct[max]++;
			if(sb.length() == num.length - digits.length())break;
			pos = maxi;
			xct = imp;
		}
		
		return sb.toString();
	}

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