AOJ2323 Revenge of Champernowne Constant - nanikakaのAOJ航海日誌

概要

チャンパーノウン定数とは、"0."に続いて、正の整数を昇順に連続で並べたような無理数である。
"0"-"9"の文字で構成された文字列Sがチャンパーノウン定数の中で最初に出現する位置はどこか答えよ。答えは10^16未満である。

<= 100

解法

Revengeとあるようにこれの類題です。
Sの中のh番目の文字からk文字を抜き出し、これが1つの整数xと解釈することにします。そして、Sの文字列をカバーするように、
..."x-3"+"x-2"+"x-1"+"x"+"x+1"+"x+2"...
という風に文字列を拡大します。Sをカバーしたら、Sに相当する部分と比較し、完全一致するかを調べます。完全一致した場合、チャンパーノウン定数中で、数xが登場するインデックスを算出します。数xはSの先頭からh番目にあるわけなので、この値からhを引いたものがすなわちtargetの開始インデックスとなります。これを(h, k)の組み合わせをざっと調べて、その最小値が答えとなります。Sのh番目からk文字を抜き出したときにリーディング0になっていた場合はアウトです。
このh番目からk文字を抜き出す処理ですが、k <= min(17, |S|)で十分といえます。17桁以上の整数で解釈すると、きっと10^16を超えるし、|S|以上の文字列で解釈しても、それより小さい解が必ず存在するので計算するだけムダです。
h番目からk文字取りだすとき、targetの文字が足りない場合があります。このとき、hより手前の文字列に注目すればOKです。k <= min(17, |S|)としているので、足りない文字数以上の文字がhの手前にあります。例えば、"123412"でh=4, k=4としたとき、hからk文字取ると"12??"となります。手前にある"1234"から後ろ2文字を持ってきて("34")、更に1を加えて("35")、これをくっつけて"1235"と解釈すればうまくいきます。桁上がりが生じるときも気にせず、このまま処理すれば大丈夫です。
例えば、"9994"でh=3, k=4のとき"4???"となり、手前の文字列から足りない3文字を取り("999")、1を加えて("1000")、後ろ3文字を取ってくっつければ"4000"になります。

ソース

import java.util.Scanner;

//Revenge of Champernowne Constant
public class AOJ2323 {

	long DIGIT_LIMIT = 1000000000000000000L;
	long MAX_NUMBER = 59477124183006535L;
	long[] endK;
	long[] ten;
	
	void init(){
		endK = new long[20];
		endK[0] = 0;
		long num = 9;
		for(int k=1;k<=17;k++,num*=10){
			endK[k] = endK[k-1]+k*num;
		}
		endK[18] = DIGIT_LIMIT;
		endK[0] = -1;
		ten = new long[20];
		ten[0] = 0;
		ten[1] = 10;
		for(int k=2;k<=17;k++)ten[k]=ten[k-1]*10;
	}
	
	long findNumber(long x){
		if(x<=0||MAX_NUMBER<x)return DIGIT_LIMIT;
		if(x<10)return x;
		int k = (x+"").length()-1;
		return endK[k]+1+(k+1)*(x-ten[k]);
	}
	
	long findString(String target){
		boolean allzero = true;
		for(char ch:target.toCharArray())allzero&=ch=='0';
		if(allzero)return findNumber(Long.parseLong("1"+target))+1;
		int len = target.length();
		if(len==1){
			return findNumber(Long.parseLong(target));
		}
		long res = DIGIT_LIMIT;
		int lenMax = Math.min(17, len);
		for(int h=0;h<lenMax;h++)for(int k=1;k<=lenMax;k++)res = Math.min(res, findStringSub(target, h, k));
		return res;
	}
	
	long findStringSub(String target, int h, int k){
		if(target.charAt(h)=='0')return DIGIT_LIMIT;
		String sub = target.substring(0, h);
		String s = "";
		for(int i=h;i<h+k;i++){
			if(i<target.length())s+=target.charAt(i);
			else {
				int L = h+k-i;
				String r = (Long.parseLong(sub.substring(sub.length()-L))+1)+"";
				while(r.length()-L<0)r="0"+r;
				s+=r.substring(r.length()-L); break;
			}
		}
		long base = Long.parseLong(s);
		if(MAX_NUMBER<base)return DIGIT_LIMIT;
		String match = base+"";
		int pos = h, addLen = 0;
		long b = base-1;
		while(pos>0){
			if(b<=0)return DIGIT_LIMIT;
			String add = b-- +"";
			pos-=add.length();
			addLen+=add.length();
			match = add+match;
		}
		b = base+1;
		pos = h+k;
		while(pos < target.length()){
			String add = b++ +"";
			pos+=add.length();
			match+=add;
		}
		for(int i=0;i<target.length();i++)if(target.charAt(i)!=match.charAt(addLen-h+i))return DIGIT_LIMIT;
		return findNumber(base)-h;
	}
	
	void run(){
		init();
		Scanner sc = new Scanner(System.in);
		for(;;){
			String s = sc.next();
			if("#".equals(s))break;
			System.out.println(findString(s));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2323().run();
	}
}