POJ 1312 Numerically Speaking

問題

文字列に対して自然数を一意に割り当てる。
割り当て方は、文字列を短い順に並べ、その中で辞書順で並べて、頭から1,2,3という規則で行う。

文字列または自然数が与えられるので、
文字列と対応する自然数（3桁ごとにコンマで区切る）を出力せよ。

制約条件

文字列の長さ≦20

方針

割り当てられる数がlong longでも収まらないので、多倍長整数演算を使う必要がある。

数字が与えられた場合、まず文字列の長さを求める。
これは26^iをi=1からはじめて引けるだけひけばよい。

次にその文字列の中でn番目のものは何かを求める。
これは残りの数字を26進数と見ていくつになるかに相当する。

文字が与えられた場合、それより短い文字列が何個あるかカウントする。
次に、その文字がその文字列の中で何番目かを求める。
これは、文字列を26進数とみたときに、10進数でいくつになるかに相当する。

ソースコード

class pku1312{
	void run(){
		Scanner sc=new Scanner(System.in);
		BigInteger pow26[] = new BigInteger[21];
		pow26[0] = BigInteger.ONE;
		for(int i=1;i<=20;i++)pow26[i]=pow26[i-1].multiply(BigInteger.valueOf(26));
		
		for(;;){
			String str=sc.next();
		
			if(str.charAt(0) == '*')return;
			
			if(Character.isDigit(str.charAt(0))){
				BigInteger n=new BigInteger(str), m=n;
				StringBuilder ans=new StringBuilder();
				
				n=n.subtract(BigInteger.ONE);
				
				int len=1;
				for(;;len++){
					if(n.compareTo(pow26[len])<0)break;
					else n=n.subtract(pow26[len]);
				}
				
				for(int i=0;i<len;i++){
					ans.append((char)('a'+n.mod(BigInteger.valueOf(26)).intValue()));
					n=n.divide(BigInteger.valueOf(26));
				}
				ans=ans.reverse();
				System.out.format("%-22s%,3d%n", ans, m);
			}
			else{
				BigInteger ans=BigInteger.ZERO;
				for(int i=0;i<str.length();i++){
					ans=ans.multiply(BigInteger.valueOf(26));
					ans=ans.add(BigInteger.valueOf(str.charAt(i)-'a'));
				}
				for(int i=0;i<str.length();i++)ans=ans.add(pow26[i]);
				System.out.format("%-22s%,3d%n", str, ans);
			}
		}
	}
}