加法・減法で成り立つ式の種類の数え上げ

Question

問題

問題

質問内容

上記のリンクの問題でAC(正解)をだしているコードについての質問なのですが、下記のコードの次の部分がどういうことなのか教えていただきたいです。
######1
[]の中のsc.nextInt()がどういう意味なのか分からないです。
入力はしないと思うのですが。

counts[sc.nextInt()] = 1;

######2
countsの要素数で回していますが，この要素数は何を表していますか？
一番外側のforは数字と数字の間のことだと思っています。
また，最後にcountsにnextを代入していますがこれらに[]がついていません。これらは配列ではないのですか？

for (int i = 1; i < n - 1; i++) {
			long[] next = new long[21];
			int x = sc.nextInt();
			for (int j = 0; j < counts.length; j++) {
				if (j - x >= 0) {
					next[j - x] += counts[j];
				}
				if (j + x <= 20) {
					next[j + x] += counts[j];
				}
			}
			counts = next;
		}

######3
上記の二つが分からないため、これでどうやって答えになっているのかが分かりませんこの代入しているだけの操作で。
40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
の入力で7069052760が出力されるとは考えられません。

とても基本的なことかもしれませんがよろしくお願いいたします。

疑問があるコードの全体

import java.util.*;
 
public class Main {
 
	public static void main (String[] args)  {
		Scanner sc = new Scanner(System.in);
		long[] counts = new long[21];
		int n = sc.nextInt();
		counts[sc.nextInt()] = 1;
		for (int i = 1; i < n - 1; i++) {
			long[] next = new long[21];
			int x = sc.nextInt();
			for (int j = 0; j < counts.length; j++) {
				if (j - x >= 0) {
					next[j - x] += counts[j];
				}
				if (j + x <= 20) {
					next[j + x] += counts[j];
				}
			}
			counts = next;
		}
		System.out.println(counts[sc.nextInt()]);
	}
}

Answer 1

質問の 2 への回答です。

countsの要素数で回していますが，この要素数は何を表していますか？

counts の要素数は 21 です。
JOI君は 0以上 20以下の 21種類の数しか確かめられません。
counts[0] は +- を繰り返して途中で 0 になるのが何通りあるかの値です。
counts[1] は +- を繰り返して途中で 1 になるのが何通りあるかの値です。
...
counts[20] は +- を繰り返して途中で 20 になるのが何通りあるかの値です。

また，最後にcountsにnextを代入していますがこれらに[]がついていません。これらは配列ではないのですか？

long[] counts や long[] next と宣言されているので、
counts や next は配列です。でも配列の実体は new long[21] を実行したときに
メモリ中にできるもので、counts や next はそれらを参照するだけです。

counts[i] と書くと、配列の実体の中の i番目の要素にアクセスできます。

counts だけだと、配列の実体ではなく、実体への参照です。

counts = next; を実行すると、
counts の値が next の値で書き換えられ、next が参照していた配列の実体を
counts も参照するようになります。それまでに counts が参照していた配列の
実体は誰も参照しなくなるので破棄されます。

next が参照している配列の実体を count が参照している配列の実体に
コピーしたわけではありません。

Comments

[grape_ll]

確かに21種類になっていますね。countの要素数が21になる理由は納得できました。ありがとうございます。
配列のところは、一個ずつやるとfor文のところをまとめてやっているという解釈で問題ないでしょうか。
破棄されるものはgarbageですよね。

Answer 2

1

このAtCoderをはじめ、プログラミング問題のサイトでは、処理をするべきデータセットが「標準入力」から与えられる場合が多いです。その入力を得ています。

        Scanner sc = new Scanner(System.in);

で入力の準備をし、これ以降、nextInt()を呼び出すたび、入力から整数値を取り出します。
入力例2の場合、最初の呼び出し

        int n = sc.nextInt();

で最初の整数値「40」を取り出してnに代入し、次の呼び出し

        counts[sc.nextInt()] = 1;

で「1」を取り出して使います。この場合、配列countの1番目に1を代入しています。

2

配列.lengthは配列の要素数ですが、「何を表していますか？」の質問の意味が分かりません。配列の要素数は配列の要素数であって、それ以上でもそれ以下でもありません。
countsもnextもlong[]型の変数です。long[]型の変数countsにlong[]型のnextを代入しています。

3

例えば、途中までの答えが4になる数式が10通りあったとして、その次の数字が2である場合、
その10通りの数式の後に「+2」を付けることで、答えが6になる数式を10通り作ることができ、
「-2」を付けることで答えが2になる数式を10通り作ることができます。
これを踏まえて次を読んでください。
入力例2で行くと、
0. 最初の数字だけで作れる数字はその数字そのもの1の1通りのみ。それをcounts[1]=1として保存する。当然他の数字を作れるパターンは0．
0. 次の数字を加えて作れる数式パターンの数を数えるための配列nextを用意。
0. その次の「1」との間に+を入れて、2を1通り作れる。next[2]=counts[1]
0. 同様に-を入れることで、0を1通り作れる。next[0]=counts[1]
0. 2個目までの答えのパターンを次のループで使うため、nextとしたものをcountsとして設定しなおす。
0. 3個目の1は、2個目までの答えが2になるものに「+1」で3が作れ、「-1」で1が作れる。
0になるものに「+1」で1が作れる。0の後に「-1」を付けると答えが負になるため、これは不適。
結果、1が2通り、3が1通り作れる

上記手順を、最後手前まで繰り返せば、0から20までの作り方全パターン数を記録できる。
欲しいのは最後の数になるパターン数だけであるため、それを出力して終了。

Comments

[grape_ll]

1.について
Scanner　のscanfのような使い方はすでに知っているので、nに入れる操作に疑問はないのですが
counts[sc.nextInt()] = 1;のときにはいれる整数を入力してない気がしています。これはcounts[1]=1;ではいけないのですか？

2.について
他回答者さまによって０から20までの数字が途中に出てくる回数ということが分かりました。

3.について
そのような流れになっていたのですね。理解することが出来ました。ありがとうございます。

[swordone]

最初の数字が8の場合、counts[8]に1を入れる必要があります。

[grape_ll]

いま、やっと理解できました。
for文のところですべての数字を入れるのかと勘違いしていたのですが、<n-1となっているので初めの数字はcountsのところに入るのですね。そこを見逃していたのでわけが分からなくなってしまっていました。
ご回答ありがとうございました。