C++ 少し大きめの配列を用意する意味はなんですか?

#C++ 少し大きめの配列を用意する意味はなんですか?

C++で競技プログラミングに取り組んでいますが、必要な配列よりも少し大きめの配列を準備している回答が多いです。
例えばN=1000個の入力が与えられその値をそれぞれ配列に入れるとなった場合に

int num[1000]とはせずに
int num[1050]のようにある程度大きめの配列をグローバルで宣言するコードをよく見ます。

このようなことはどうして行っているのでしょうか？
ご存知の方がいらっしゃったら教えてください。

行動規範の内容に同意します

回答2件

ベストアンサー

プログラムを書く速度を競う、という条件を前提とすれば、コードの考慮漏れで配列要素をオーバーするリスクがある場合に、余分に配列を取るコストはほぼ皆無なのに対して、配列が範囲をはみ出さないか考慮するコストは時間として負担になりえます。

投稿2020/10/11 01:36

maisumakun

総合スコア145208

maisumakun

2020/10/11 01:52

もちろん、普段のプログラミングでやってはいけない技です。

encho

2020/10/11 07:16

競技上の特性ということだったんですね。ありがとうございます

行動規範の内容に同意します

プログラムの実行速度を競う、という条件を前提とすれば、
配列のサイズを 2のべき乗にすることがあります。

C
1extern int a[500][1000];
2extern int b[500][1024];  // 1000で十分なのに 2の10乗の 1024 にする
3
4int getA(int i, int j) { return a[i][j]; }
5int getB(int i, int j) { return b[i][j]; }

このコードを gcc -c -O2 でコンパイルして、objdump -d で逆アセンブルすると

text
10000000000000000 <getA>:
2   0:	f3 0f 1e fa          	endbr64 
3   4:	48 63 ff             	movslq %edi,%rdi
4   7:	48 63 f6             	movslq %esi,%rsi
5   a:	48 8d 05 00 00 00 00 	lea    0x0(%rip),%rax        # 11 <getA+0x11>
6  11:	48 69 ff e8 03 00 00 	imul   $0x3e8,%rdi,%rdi
7  18:	48 01 f7             	add    %rsi,%rdi
8  1b:	8b 04 b8             	mov    (%rax,%rdi,4),%eax
9  1e:	c3                   	retq   
10
110000000000000020 <getB>:
12  20:	f3 0f 1e fa          	endbr64 
13  24:	48 63 ff             	movslq %edi,%rdi
14  27:	48 63 f6             	movslq %esi,%rsi
15  2a:	48 8d 05 00 00 00 00 	lea    0x0(%rip),%rax        # 31 <getB+0x11>
16  31:	48 c1 e7 0a          	shl    $0xa,%rdi
17  35:	48 01 f7             	add    %rsi,%rdi
18  38:	8b 04 b8             	mov    (%rax,%rdi,4),%eax
19  3b:	c3                   	retq