なぜ、配列をビットシフトして確保しているのか?(c++)

Question

Atcoderの競プロ典型 90 問の第一問目について

競プロ90 問の第一問目の

#include <iostream>
using namespace std;

long long N, K, L;
long long A[1 << 18];

において、

long long A[1 << 18];

のビットシフトで確保する理由とメカニズムが理解できないので、ご教授願います。

Answer 1

1 << 18は2の18乗です。C++に冪乗演算子**があれば、long long A[2**18];と書くのでしょうが、そういう演算子は無いのでlong long A[1<<18];と書く事になる。
（処理系によってはlong long A[(int)pow(2,18)];も可能）

普通のプログラマーは、「1 << 18は2の18乗」を脳内で一瞬で変換します。

Answer 2

コンパイラは、定数の計算であれば計算結果で置き換えてコンパイルしますから、ソース上に1<<18と書いてあればそれは262144と書いてあるのと同じことです。
普通は、その値の「意味」を表したい時にそういう書き方をするのですが...例えば1日の秒数を表したい場合に606024 みたいに書けば86400という数字が書いてあるよりも「意味」が読み取りやすいですよね。(コメントも添えますけれど)

ちょっと話を変えて

解答サンプルの全体を見渡すと、その後に出てくるAのインデックスは

    for (int i = 1; i <= N; i++) {
        if (A[i] - pre >= M && L - A[i] >= M) {
            cnt += 1;
            pre = A[i];
        }
    }

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

だけです。
ここで、問題としてN<10^5と規定されています。このプログラムではNを超える値は添字として与えられることはありません。
(付け加えるなら、A[i]<L<10^9というのも規定されています。つまり、Aの要素は(intが4byteの系であれば)intでもいいはず、少なくともlongであれば十分なはず)
ということで、配列の宣言は
long A[100000+1];//+1しているのはA[0]を使ってないから。これも「式で書く」例。
で良かったはずです。ちゃんと躾けられたプログラマならさらに「マジックナンバー」を嫌って

const int MAX_L=100000; //切れ目の最大個数
long A[MAX_L+1]; //A[0]は使用せずMAX_L個の要素を使用

とでもするところでしょう。

ではなぜ1<<18なのか。
Aの要素数真面目に考えるのめんどくさい。思考停止しよう。なんでもいいから、大きな値、そうだ1<<18だったらきっと十分大きいよね、というのが1<<18の意味であり、意図なのでしょう。

競技プログラミングってそういう世界なのかなぁ? だったら染まって欲しくないなぁ。