トップコーダーで大きな入力サイズのJavaプログラムを解決する

Question

私はjavaのSRM 144 DIV 1から問題を解決しています。私のコードはすべてのテストケースで動作しますが、値が "12221112222221112221111111112221111" のテストケースがあります。これはjavaのデータ型の制限を超えていることがわかりました。

これを解決する方法があります。 ここに私のコードのサンプルです。

public class BinaryCode{ 
public String[] decode(String message){ 
    int mess = Integer.parseInt(message); 
    int encmess[] = new int[message.length()]; 
    for(int i = message.length()-1;i>=0;i--){ 
     encmess[i] = mess%10; 
     mess = mess/10; 
    } 
    int[] decmess1 = new int[message.length()]; 
    int[] decmess2 = new int[message.length()]; 
    decmess1[0] = 0; 
    decmess2[0] = 1; 
    String mess1 = ""; 
    String mess2 = ""; 

    for(int i = 1;i<decmess1.length;i++){ 
     if(i == 1){ 
      decmess1[i] = encmess[i-1] - decmess1[i-1]; 
     } 
     else{ 
      decmess1[i] = encmess[i-1] - decmess1[i-1] - decmess1[i-2]; 
     } 
     if(decmess1[i]>1||decmess1[i]<0){ 
      mess1 = "NONE"; 
      break; 
     } 
    } 
    for(int i = 1;i<decmess2.length;i++){ 
     if(i == 1){ 
      decmess2[i] = encmess[i-1] - decmess2[i-1]; 
     } 
     else{ 
      decmess2[i] = encmess[i-1] - decmess2[i-1] - decmess2[i-2]; 
     } 
     if(decmess2[i]>1||decmess2[i]<0){ 
      mess2 = "NONE"; 
      break; 
     } 
    } 
    int num1 = 0; 
    int num2 = 0; 
    if(!mess1.equals("NONE")){ 
     for(int i = 0;i<decmess2.length;i++){ 

       num1 = num1*10 + decmess1[i]; 

     } 
    } 
    if(!mess2.equals("NONE")){ 
     for(int i = 0;i<decmess2.length;i++){ 

      num2 = num2*10 + decmess2[i]; 
     } 
    } 
    if(!mess1.equals("NONE")) 
     mess1 = "0"+Integer.toString(num1); 
    if(!mess2.equals("NONE")) 
     mess2 = Integer.toString(num2); 

    String[] result = {mess1,mess2}; 
    return result; 
} 

}

Answer 1

あなたはその

BigInteger mess = new BigInteger(message); 

Answer 2

BigIntegerのようなものを試してみてください代わりにint

のBigIntegerを使用することができ任意精度を持っています。あなたの既存の方法は

public static String[] decode(String message) { 
    BigInteger TEN = BigInteger.valueOf(10); 
    BigInteger mess = new BigInteger(message); 
    BigInteger encmess[] = new BigInteger[message.length()]; 
    for (int i = message.length() - 1; i >= 0; i--) { 
     encmess[i] = mess.mod(TEN); 
     mess = mess.divide(TEN); 
    } 
    BigInteger[] decmess1 = new BigInteger[message.length()]; 
    BigInteger[] decmess2 = new BigInteger[message.length()]; 
    decmess1[0] = BigInteger.ZERO; 
    decmess2[0] = BigInteger.ONE; 
    String mess1 = ""; 
    String mess2 = ""; 

    for (int i = 1; i < decmess1.length; i++) { 
     if (i == 1) { 
      decmess1[i] = encmess[i - 1].subtract(decmess1[i - 1]); 
     } else { 
      decmess1[i] = encmess[i - 1].subtract(decmess1[i - 1])// 
        .subtract(decmess1[i - 2]); 
     } 
     if (decmess1[i].compareTo(BigInteger.ONE) > 0 // 
       || decmess1[i].compareTo(BigInteger.ZERO) < 0) { 
      mess1 = "NONE"; 
      break; 
     } 
    } 
    for (int i = 1; i < decmess2.length; i++) { 
     if (i == 1) { 
      decmess2[i] = encmess[i - 1].subtract(decmess2[i - 1]); 
     } else { 
      decmess2[i] = encmess[i - 1].subtract(decmess2[i - 1])// 
        .subtract(decmess2[i - 2]); 
     } 
     if (decmess2[i].compareTo(BigInteger.ONE) > 0 // 
       || decmess2[i].compareTo(BigInteger.ZERO) < 0) { 
      mess2 = "NONE"; 
      break; 
     } 
    } 
    BigInteger num1 = BigInteger.ZERO, num2 = BigInteger.ZERO; 
    if (!mess1.equals("NONE")) { 
     for (int i = 0; i < decmess2.length; i++) { 
      num1 = num1.multiply(TEN).add(decmess1[i]); 
     } 
    } 
    if (!mess2.equals("NONE")) { 
     for (int i = 0; i < decmess2.length; i++) { 
      num2 = num2.multiply(TEN).add(decmess2[i]); 
     } 
    } 
    if (!mess1.equals("NONE")) 
     mess1 = "0" + num1.toString(); 
    if (!mess2.equals("NONE")) 
     mess2 = num2.toString(); 

    String[] result = { mess1, mess2 }; 
    return result; 
} 

のようなものに変更することができる次に、あなたは

public static void main(String[] args) { 
    System.out.println(Arrays.toString(decode("12221112222221112221111111112221111"))); 
} 

ようにそれを呼び出すことができますそして、私は

[01101001101101001101001001001101001, 10110010110110010110010010010110010]