ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

Facebook Hacker Cup 2014 Round 1 : Labelmaker

概要

L種類のアルファベットを用いて文字列を作る。(各アルファベットは複数回使うことができる。)

そのアルファベットを用いて作ることのできる文字列をある方法で並べたとき、N番目にくる文字列を求めよ。

ある方法で並べるとは、1文字からなる文字列を昇順ソート、2文字からなる文字列を昇順ソート、...、M文字からなる文字列を昇順ソートしていくことである。

例えば、{D,T,Z}の3種類のアルファベットが与えられた場合の並び順は以下のようになる。
D, T, Z, DD, DT, DZ, TD, TT, TZ, ZD, ZT, ZZ, DDD, DDT, DDZ, ..., ZZZ, DDDD, ...

  • L <= 25
  • N <= 2^63 - 1

https://www.facebook.com/hackercup/problems.php?pid=637270059647812&round=1437956993099239

解法

上記の並べ方はL進数表記そのものなので、十進数で与えられるNをL進数に直すことができればよいことになる。

私の書き方だとlong long intでもオーバーフローしそうだったのでJavaで書くことにした。

ソースコード

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {

    String solve(String L, BigInteger N) {
        String res = "";
        int len = L.length();
        BigInteger p = BigInteger.ONE;
        BigInteger q = new BigInteger(Integer.toString(len));

        // 0-origin
        N = N.subtract(BigInteger.ONE);

        for(int i = 1; i < 70; i++) {
            p = p.multiply(q);
            if(N.compareTo(p) == -1) {
                long n = N.longValue();
                for(int j = 0; j < i; j++) {
                    res = L.charAt((int)(n % len)) + res;
                    n /= len;
                }
                break;
            }
            N = N.subtract(p);
        }

        return res;
    }
    
    void run() {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int tc = 1; tc <= T; tc++) {
            String L = sc.next();
            BigInteger N = sc.nextBigInteger();
            System.out.println("Case #" + tc + ": " + solve(L, N));
        }
    }

    
    public static void main(String[] args) {
        new Main().run();
    }
}