C - N進数

CODE FESTIVAL 2014 決勝 - AtCoder

20200519のあさかつで出た問題

概要

10以上の整数 に対して、進数で表したときと表せる数をとする。

与えられた整数に対して、 と表すことができるが存在すればを出力。

なければを出力せよ。

制約

方針

の性質より、調べなければならないの範囲はそんなに大きくないです。全探索します。

整数を進数で表したときの10進数表記をとします。

のすべてのkに対して、を満たすかどうか判定します。

進数

Long#toStringはJavaで進数変換するときによく使います。*1

数字と基数を与えれば、文字列型で進数変換した結果を返してくれます。*2

long N = 100;
System.out.println(Long.toString(N, 2));
System.out.println(Long.toString(N, 16));
System.out.println(Long.toString(N, 17));

/*
1100100
64
5f
*/

ただしこれには制約があり、2～36進数の間でしか変換してくれません。*3

それ以外の基数を与えると10進数の結果で返ってきます。*4

long N = 100;
System.out.println(Long.toString(N, 1));
System.out.println(Long.toString(N, 2));
System.out.println(Long.toString(N, 36));
System.out.println(Long.toString(N, 37));

/*
100
1100100
2s
100
*/

自前で基数変換を行いました。

大枠としては基数で割ったあまりを文字列に追加していくことを繰り返していきます。

ミュータブルであるStringBuilderを利用すると気楽に実装できます。reverseメソッドが便利です。

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int ans = -1;
        long A = sc.nextLong();
        for(int i=10; i<10001; i++){
            StringBuilder tmp = new StringBuilder();
            long a = A;
            while(a>0){
                long t = a%i;
                if(t > 9)break; //表記が数字でなくなった時点で無視
                tmp.append(t);
                a -= t;
                a /= i;
            }
            tmp = tmp.reverse();
            if(String.valueOf(i).equals(tmp.toString()))ans = i;
        }
        System.out.println(ans);
        sc.close();
    }
}

*1:実際は、Integer#toStringの方がよく使います。今回は問題の制約条件的にLongを紹介

*2:2進数はtoBinaryString、8進数はtoOctalString、16進数はtoHexStringと専用のメソッドがありますが、競技プログラミングをする上では全部toStringで実装しちゃいます。

*3:アルファベットが26文字しかないからでしょうか

*4:これを知らなかったのでだいぶ時間をとられました。