XORのアルゴリズムでRUNTIME ERROR

Question

実現したいこと

・TechfulのサイトでXORの問題を解いているのですが、何回試してもRUNTIME ERRORが出力されてしまいます

ここに実現したいことを箇条書きで書いてください。

• ▲▲機能を動作するようにする

前提

[解いている問題]
あなたは M+1 個の N 桁の 2 進数 I1,I2,…,IM+1 と、それらを全て XOR した結果得られる 2 進数 P を持っていました。

しかし、あなたは I1,I2,…,IM+1 のうち、一つを紛失してしまいました。
あなたが現在持っている M 個の 2 進数 J1,J2,…,JM と、2 進数 P から紛失した 2 進数を復元してください。

[入力される値]
N M
P
J_1
J_2
J_3
.
.
.
J_M

・1 行目に 2 進数の桁数 N と、現在持っている 2 進数の数 Mが与えられます。
・2行目に現在持っている M 個の 2 進数と紛失した 2 進数を全て XOR することで得られる ２進数 Pが与えられます。
・3行目から M 行にわたって、現在持っている 2 進数Jiが与えられます。
また、全ての２進数は '1' または '0' からなる文字列で与えられます。

[期待される出力値]
紛失した 2 進数を出力してください。 ただし、出力はゼロ埋めを行って、N 桁ちょうどにしてください。

[制約]
・N,M: 整数
・P,Ji: '1' または '0' からなる文字列
・10≤ N ≤ 50
・1≤ M ≤ 500
・|P|= N
・|Ji|= N
・ただし、|P|,|Ji| はそれぞれ文字列 P,Ji の長さを表す。

サンプルケース

サンプルケース①の入力値

10 1
1010100110
0101001000

サンプルケース①の出力値

1111101110

サンプルケース②の入力値

10 3
0100101001
1010100110
0101001000
0001010011

サンプルケース②の出力値

1010010100

発生している問題・エラーメッセージ

現在10個あるテストケースの内2つは「PASS」になっていますが、残りの8つはRUNTIME ERRORになっています。

RUNTIME ERROR

該当のソースコード

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scnn = new Scanner(System.in);
        int N = scnn.nextInt();
        int M = scnn.nextInt();

        String p, b;
        List<String> j = new ArrayList<>();
        p = scnn.next();   //p　(XORした答え)
        int p2sin = Integer.parseInt(p, 2);//pを10進数に変換

        int []j2sin=new int[M];
        for (int i = 0; i < M; i++) {
            b = scnn.next();//j
            j2sin[i] = Integer.parseInt(b, 2);//jを10進数に変換
            j.add(i, b);
        }
        int s=j2sin[0];
        for(int k=0;k<M-1;k++){
            s=s^j2sin[k+1];
        }
        s=s^p2sin;//660
        String o=Integer.toBinaryString (s);//2進数に変換
        if(o.length()!=N){                  //0でN桁にする
            System.out.println(padLeft(o, N));
        }else{
            System.out.println (o);
        }
    }
//N桁じゃない場合ゼロパディング
    public static String padLeft(String s, int n) {
        return String.format("%0" + n + "d", Integer.parseInt(s));
    }
}

試したこと

・Techfulの仕様があまりわかっておらず、Nの制約「10≤ N ≤ 50」の範囲外になったら「System.exit(0)」で終了させたり、p,jが"0"もしくは"1"でない場合は入力を受け付けないようにするなどしてみましたがどうしてもRUNTIME ERRORが出てしまいます。
・サンプルケースの値は期待される出力値になっているのでアルゴリズム自体は合っているのかなと勝手に思っています。

Comments

[jimbe]

>現在10個あるテストケースの内2つは「PASS」になっていますが、残りの8つはRUNTIME ERROR

その8つはどのような入力なのでしょうか。

>Nの制約「10≤ N ≤ 50」の範囲外になったら「System.exit(0)」で終了させたり、p,jが"0"もしくは"1"でない場合は入力を受け付けないようにするなどしてみました

「その範囲の値のデータを処理できるプログラムでなければならない」ということではないでしょうか。
ですのでその範囲外の値は渡されないので範囲外は考える必要は無い一方、範囲内のデータは確実に処理できる必要があるということでしょう。
そしてそれはつまり、 N は最大 50 文字 = 50 ビットになるということです。 java の int は何ビットでしょうか?

それと、この問題は結局 P と i1～iM 全てを XOR するだけなので、 P を(p2sin 等と)別扱いする必要はありません。
入力を次々と XOR していくだけですので、配列やリストに入れる必要も無いものと思います。( j って使ってます?)

[fi4tb]

＞その8つはどのような入力なのでしょうか。
自分が解いていた問題はどんな入力値が与えられているのか公開されていなかったです。
なので単純に、テストケース１：RUNTIME ERRORという風にしか教えてくれないです。

jimbleさんのプログラムをもとに直した結果、無事PASSになりましたありがとうございます。
Nをビットの数ではなく入力される数値の桁数として考えていたのができない原因でした。
変にListを作る癖がついているので今後気をつけます。この度はありがとうございました。

[xebme]

XORは共通鍵の暗号化と復号で使われます。失ったワードを平文L、手元のワードを共通鍵JM、暗号文をPとする。P、JMから平文Lを復号する操作を行います。
暗号化: P = L xor JM
復号: L = P xor JM

XOR swap も同じ原理を利用します。

[jimbe]

>Nをビットの数ではなく入力される数値の桁数として考えていた

いっそのこと、数値化して "^" を使うのではなく、 String 状態のまま文字毎に xor 相当の処理をして結果 String を作り出すようなことにするというテもあります。
これなら例え N=100 でも 1000 でも対応出来ますね。いわゆる "オーバースペック" ですが…。

Answer 1

N はビット数に当たります。 50 ビットは int では処理出来ません。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int M = scanner.nextInt();

    long v = 0; //63?ビットまで
    for(int i=0; i<=M; i++) v ^= Long.parseLong(scanner.next(), 2);
    String s = Long.toBinaryString(v);
    System.out.println("0".repeat(N - s.length()) + s);
  }
}

入力

50 1
00001010010010100110000100100000010100110000101001
00010100010100100100101010100000011111001110100010

出力

00011110000110000010101110000000001011111110001011