BottomCoder SRM 390 div2

SRM 390 div2

points	result	time
250	AC	3m
500	AC	5m
1000	WA (MODつけ忘れ)	75m

250

おこちゃまが片手の親指から指を折っていって、小指にきたら指を戻していって数を数える。(123454321234543…)ある指(weakFinger)は脆く、maxCount(<=100000)回折る戻るの操作を行うと死ぬ。maxCount=0のときは、weakFingerまできたら死ぬ。指が死んだら数を数えられないとき、いくつまで数を数えられるか。

多くても100000*5回までなので愚直にシミュレーションする。現在位置と数える方向と脆い指に刺激を与えた回数を逐次的に動かせばよい。

import java.util.Arrays;

public class FingerCounting {

	public int maxNumber(int weakFinger, int maxCount) {
		int inj = 0;
		int cur = 0;
		int v = 1;
		for(int i = 0;;i++){
			cur += v;
			if(cur == weakFinger){
				if(inj >= maxCount){
					return i;
				}
				inj++;
			}
			if(cur == 5){
				v = -1;
			}
			if(cur == 1){
				v = 1;
			}
		}
	}

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

500

number(1<=*<=10^9)を横にくっつけた整数がはじめてk(<=10^5)で割りきれるときのくっつけた個数を求めよ。

numberを横にくっつける操作は、numberの桁数をdとすると、number:=number*10^d+number
となる。dは、numberをString化して求めれば速い。あとは、上の漸化式をkを法として計算して、0になればそこまでの操作の回数+1を答えとし、k回繰り返してもダメな場合は-1を答えとする。値は0〜k-1しかとらないのでk回まわっても0にならなければ他のどれかと等しい。つまりループに入っている。

import java.util.Arrays;

public class ConcatenateNumber {

	public int getSmallest(int number, int k) {
		int len = Integer.toString(number).length();
		int mod = 1;
		for(int i = 0;i < len;i++){
			mod = (mod*10)%k;
		}
		long cur = number % k;
		for(int i = 1;i <= k+1;i++){
			if(cur == 0)return i;
			cur = (cur * mod + number) % k;
		}
		return -1;
	}

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

1000

'?'を、a-zの任意の1文字とするパターンとする。同じ長さM(<=50)のパターンがN(<=15)個与えられたとき、このうちちょうどk個に合致する文字列の個数%1000003を答えよ。

20以下はbitといったろうが!この前のこれに似てるなあとおもって貪欲にできる方法を数十分探してしまった。

i:文字列中の位置(

import java.util.Arrays;

public class SetOfPatterns {

	int MOD = 1000003;
	
	public int howMany(String[] patterns, int k) {
		int n = patterns.length;
		int m = patterns[0].length();
		
		int[][] mask = new int[m][26];
		for(int i = 0;i < m;i++){
			for(int j = 0;j < 26;j++){
				int ms = 0;
				for(int l = 0;l < n;l++){
					char c = patterns[l].charAt(i);
					if(c == '?' || c == 'a'+j){
						ms |= 1<<l;
					}
				}
				mask[i][j] = ms;
			}
		}
		
		int[] ds = new int[1<<n];
		for(int u = 0;u < 26;u++){
			ds[mask[0][u]]++;
		}
		for(int i = 1;i < m;i++){
			int[] nds = new int[1<<n];
			for(int j = 0;j < 26;j++){
				for(int l = 0;l < 1<<n;l++){
					nds[l&mask[i][j]] += ds[l];
				}
			}
			
			for(int l = 0;l < 1<<n;l++){
				nds[l] %= MOD;
			}
			ds = nds;
		}
		
		long sum = 0;
		for(int i = 0;i < 1<<n;i++){
			if(Integer.bitCount(i) == k){
				sum += ds[i];
			}
		}
		
		return (int)(sum % MOD);
	}

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