競プロ典型 90 問に対する私的解説

@e869120 氏が中心となって実施されている競プロ典型 90 問に私も参加しているのですが、少しはコミュニティーにも還元したいと思って、一部の問題について非公式の解説を書いて公開することにしました。とはいえ、公式解説の質がとても高いので、この記事では想定解以外の解法でありながら典型的なテクニックと言えそうなもの、もしくは公式解説でカバーしきれていない内容に限って説明します。公式解説を見習って、キーワードもつけておきました。

多少なりともどなたかのお役に立てたならば幸いです。

なお、以下の解説の多くは、すでに GitLab で公開している解説文書にいくらかの加筆修正を加えたものです。

002 Encyclopedia of Parentheses（★3）

公式資料 : 問題 002 ｜ 解説 002

【キーワード】 不必要な探索はしない

想定解法は括弧列をビット列とみなして全探索するというものでしたが、そもそも正しい括弧列だけが得られるように探索を工夫することもできます。

アルゴリズムの基本的骨格は次のとおりです。構造が複雑になるので再帰関数を使って実装します（解説 072 など）。

• 文字列の先頭から順番に括弧を決める。残りの長さ（$n$）と閉じるべき左括弧の個数（$d$）を保持する。
• 左括弧を配置すると、$n$ が 1 だけ減り、$d$ が 1 だけ増える。
• 右括弧を配置すると、$n$ が 1 だけ減り、$d$ も 1 だけ減る。

このとき、以下の点に注意します。

• 辞書順に出力する必要があるので、常に左括弧のケースから先に調べる。
• $d = 0$ のとき、閉じるべき左括弧が存在しないので、右括弧は使えない。
• $d \ge n$ のとき、文字列の残り全部を右括弧で埋めなければ左括弧を閉じきれないので、左括弧は使えない。

あとは、文字列終端に達した時点で、全ての左括弧が確実に閉じられていること、すなわち $d = 0$ であることが確認できれば、その文字列は条件を満たすと結論づけられます。「列の途中に余分な右括弧があるため不正である」といったケースはすでに排除されている点に注意してください。

さて、$d = 0$ であることを確認すると書きましたが、実は $n$ の初期値（$N$）が偶数であれば文字列終端に達した時点で $d = 0$ になることが保証されています¹。したがって、いちいち確認する必要はありません。なお、$N$ が奇数のときは、そもそも左右の数を合わせることが不可能ですので、探索するまでもなく条件を満たす括弧列は存在しないと結論づけてよいです。

C++ による実装例を示します。

void doit(const string& s, int n, int d)
{
    if (n == 0) {
        cout << s << endl;
    } else {
        if (d < n) doit(s + "(", n - 1, d + 1);
        if (d > 0) doit(s + ")", n - 1, d - 1);
    }
}

条件違反が明らかな状態を回避する、もしくは条件違反が明らかになった時点で探索を打ち切ることで、不必要な探索を減らすことを枝刈りといいます。枝刈りを含む探索のことを枝刈り探索と呼びます。計算時間を短縮できることがあるほか、上記の例のように最後の条件判定が簡単もしくは不要になることがあるなどのメリットがあります。競プロという言葉がなかったころから定番中の定番とみなされている技法ですので、覚えておいて損はないと思います。

［参考］全探索の別名

競プロ界では全探索という用語が定着しましたが、ほかの分野では力まかせ探索、しらみつぶし探索、総当たり法、全数探索などと呼ばれています。いずれも brute-force search もしくは exhaustive search の訳語です。

また、「とりあえずパターンを生成してしまい、そのパターンが要件を満たすか改めて検査する」という構造になっていることから、生成検査法（generate and test）とも呼ばれます。

009 Three Point Angle（★6）

公式資料 : 問題 009 ｜ 解説 009

【キーワード】 円周上の尺取法は「始点」を一周させる

真ん中（点 B）を決め打ちして偏角ソートするところまでは想定解（解説 009）と同じですが、残りの 2 点（点 A と点 C）は二分探索ではなく尺取法（解説 034）の要領で求めることもできます。点 A をひとつ決めたら、偏角の差が 180° を超えるまで点 C を動かし続けます。超えたら、点 A をひとつ移動して、再び点 C を動かし続けます。以下、これを繰り返します²。

注意点があります。普通の配列に対する尺取法では、多くの場合、一方の端が配列の終端に到達した時点で計算を打ち切ることができます。しかし、今回は円周上の点に対して尺取法を適用しているため、点 C を一周させただけでは不十分です。たとえば、偏角が −180° から 180° の範囲の値をとるのであれば³、第二象限と第三象限の間（$x$ 軸のマイナス側）をまたいだ角度について調べる必要があります。

そこで、点 C が配列の終端に到達したら、再び先頭に戻します。そのまま処理を続行して、点 A が配列の終端に到達したところで処理を打ち切ります。こうすれば、全ての角を確実に調べることができます。なお、点 C がループした後は、偏角の差を計算するときに $2\pi$ を足す必要があります。

なお、二倍した列に対して処理する手法もあります（解説 076）。こちらの方が単純でよいかもしれません。

ちなみに、計算量の観点で言えば、二分探索を用いた場合は全体で $O(N^2 \log N)$ 時間かかるのに対して、尺取法を用いた場合は $O(N^2)$ 時間で済みますので、尺取法の方がわずかに優れています。

023 Avoid War（★7）

公式資料 : 問題 023 ｜ 解説 023-P1 ｜ 解説 023-P2 ｜ 解説 023-P3 ｜ 解説 023-P4

【キーワード】 状態に通し番号をつけよう

偉そうにキーワードを書いていますが、これは公式解説（解説 023-P4）に書かれている内容です。自力では満点がとれなかったので解説を読んだのですが、唯一足りなかったことは「あり得る状態に 0, 1, 2, … と番号を振る」ところでした。それだけ私にとっては重要な内容だったのですが、公式解説では扱いが小さかったので、キーワードとして取り上げました。

なお、公式解説では DP の遷移を 1 マスごとにすることで小課題 3 に対応していますが（解説 023-P3）、不要な状態を削れば行 DP のまま解くこともできます。$W = 24$ のとき、可能なキングの配置（1 行）は全部で 121393 通りあるため、単純に考えると遷移のパターンは $121393^2 \fallingdotseq 1.47 \times 10^{10}$ 通りありますが、あるキングの左下、下、右下（あるいは左上、上、右上）には別のキングを置けないという規則のおかげで、実際に遷移可能な状態の組み合わせはそこまで多くありません。これは、以下の 2 点から何となく予想がつきます。

• 縦に並んだ 2 マスに着目したとき、上のマス、下のマスのどちらかにしかキングを置けない（解説 045 によく似た状況です）。

• 以下の図のように、次の行にひとつもキングが置けなくなるような行配置が存在する。

  
  

具体的な数はプログラムを書いて調べるのが手っ取り早いと思います（私的解説 025）。不必要な状態は調べないように探索を適宜工夫します（私的解説 002）。C++ による実装例の一部を以下に示します。

// `upper`, `lower` はそれぞれ上段、下段の状態（キングの有無のビット列）
void init_trans_map(unordered_map<int, vector<int>>& trans_map,
                    int upper, int lower, int bit)
{
    if (bit == 0) {
        // 妥当な状態遷移がひとつ見つかった。
        trans_map[upper].push_back(lower);
    } else {
        // 上段にも下段にもキングを置かない。
        init_trans_map(trans_map, upper, lower, bit >> 1);
        // 下段にキングを置く。すぐ右隣の列には上段／下段ともキングを置けない。
        init_trans_map(trans_map, upper, lower | bit, bit >> 2);
        // 上段にキングを置く。すぐ右隣の列には上段／下段ともキングを置けない。
        init_trans_map(trans_map, upper | bit, lower, bit >> 2);
    }
}

実行して trans_map の中身を調べると、遷移可能な状態の組み合わせは 22369621 通りとわかります。遷移を最大 23 回繰り返すことになるため時間的にかなり厳しいですが、冒頭に書いたとおり、状態をビット列のまま扱うのではなく通し番号をつけておくことで更新部分が軽くなり、制限時間が少し長めなこともあって、満点を得ることができます。

025 Digit Product Equation（★7）

公式資料 : 問題 025 ｜ 解説 025

【キーワード】 とりあえずプログラムを書く

さすがに $10^{11}$ 通りを全部試すわけには行きませんが、果たして $f(m)$ が取り得る値はいくつあるのでしょうか。数字の順番が変わっても値は変わらないし、0 が 1 個でもあれば値は 0 だし、1 はあってもなくても同じだし、…、と考えると $10^{11}$ よりはかなり少なそうです。

公式解説（解説 025）でも触れられていますが、高校数学（重複組合せ）の知識があれば、ある程度は上限を見積もることもできます。とはいえ、問題によっては上限を計算で見積もるのが難しいときもあります（私的解説 023）。あるいは、重複組合せを知らない、忘れてしまったみたいなパターンもあるでしょう。そのときは、プログラムを書いて調べましょう。我々にはプログラミングという道具があるのですから、これを使わない手はありません。

C++ を使った例を示します。もちろん再帰関数で書いても構いませんが（それがまともな選択だと思います）、ここでは 1 は何回乗じても値が変わらないことに着目して、桁数決め打ちの 11 重ループ（!）で書きました。

#include <iostream>
#include <unordered_set>

using namespace std;

#define long long long  // For Windows

int main()
{
    unordered_set<long> f_values = {0};

    for (long ka = 1 ; ka <= 9; ka++)
    for (long kb = ka; kb <= 9; kb++)
    for (long kc = kb; kc <= 9; kc++)
    for (long kd = kc; kd <= 9; kd++)
    for (long ke = kd; ke <= 9; ke++)
    for (long kf = ke; kf <= 9; kf++)
    for (long kg = kf; kg <= 9; kg++)
    for (long kh = kg; kh <= 9; kh++)
    for (long ki = kh; ki <= 9; ki++)
    for (long kj = ki; kj <= 9; kj++)
    for (long kk = kj; kk <= 9; kk++) {
        f_values.insert(ka * kb * kc * kd * ke * kf * kg * kh * ki * kj * kk);
    }
    cout << f_values.size() << endl;

    return 0;
}

f_values.insert の行が何回実行されるか心配になるかもしれませんが、とりあえず実行します。

$ ./a.out
6085

たったの 6085 通りでした。実行もほぼ一瞬で終わるので、このプログラムをそのまま活かすことにします。$f(m)$ と $B$ の値が両方わかれば $m = f(m) + B$ と復元できますので、$f(m)$ の候補値に対して全探索（生成検査）をすればよさそうです。$m$ の値が計算できたら、$f(m)$ の値を改めて計算して、候補値と一致するかどうかを確認します。

long N, B;
cin >> N >> B;
int ans = 0;
for (const long f_m : f_values) {
    const long m = f_m + B;
    if (m <= N && f(m) == f_m) ++ans;
}
cout << ans << endl;

関数 f は適宜実装します。N 進法展開（解説 067）の考え方を使って実装するのが自然ですが、数値を文字列に変換して計算しても問題ないと思います。どちらにせよ、この部分もほとんど時間がかかりませんので、制限時間に引っかかることはありません。

［補足］実行に時間がかかる場合の対処法

候補の数は少ないが実行時間が少し厳しいという場合は、候補値をプログラムに埋め込むというテクニックがあります。その一例を示します。

vector<long> f_values = {0,1,2,3,/*...*/,31381059609L};

AtCoder では提出できるソースコードの大きさが 512 KiB に制限されていますが、今回は整数が 6085 個なので問題になりません。残りの部分は先に示したコードがそのまま使えます。

029 Long Bricks（★5）

公式資料 : 問題 029 ｜ 解説 029-P1 ｜ 解説 029-P2

【キーワード】 変化点をキーとしたマップを作る

小課題 1 の想定解を確認しておきます。$h[x]$ は左から $x$ 番目のマスの高さを表します。

1. $h[L_i]$, $h[L_i+1]$, ..., $h[R_i]$ の最大値に 1 を足したものを $i$ 番目のレンガの高さ $h'$ として出力する。
2. $h[L_i]$, $h[L_i+1]$, ..., $h[R_i]$ の全要素を $h'$ に書き換える。

これを正直に実装すると $W$ が大きいときに実行時間がかかるというのが課題でした。小課題 2 では $N$ が小さいので座標圧縮を用いることができましたが、小課題 3 には通用しません。

そこで、$h$ を配列ではなく、高さの変わる場所をキーとしたマップで表現してみましょう。たとえば、

という状態は {0: 1, 1: 2, 2: 1, 3: 0, 5: 1, 6: 2, 8: 0} と表せます。この状態から、$L_i=4$, $R_i=6$ の範囲に新たにレンガを積み上げると次のようになります。

この状態は {0: 1, 1: 2, 2: 1, 3: 0, 4: 3, 7: 2, 8: 0} と表せます。

マップの更新は、以下のような手順によって実現できます。

1. $L_i$ 以下で最大のキーを持つ要素 $E_L$ を見つける。上の例では 3: 0 となる。
2. $R_i$ 以上で最小のキーを持つ要素 $E_R$ を見つける。上の例では 8: 0 となる。
3. $E_L$ と $E_R$ の間にある要素（$E_L$ を含み $E_R$ を含まない）の値の最大値に 1 を足したものを $i$ 番目のレンガの高さ $h'$ として出力する。上の例では 6: 2 が最大なので $h' = 3$ を出力する。
4. $E_L$ と $E_R$ の間にある要素（両端を含まない）を削除する。上の例では 5: 1 と 6: 2 を削除する。このとき $E_R$ の値を保存しておく（2）。
5. $L_i$ をキー、$h'$ を値とする要素（4: 3）、$R_i$ をキー、手順 4 で保存した値を値とする要素（7: 2）をそれぞれ追加する。

なお、最初のレンガを積む前に、マップを {0: 0} に初期化しておきます。また、$L_i$、$R_i$ がもとからある境界と重なったときは適宜対処します（雑）。

このうち、手順 1、2、5 は平衡二分木を用いることで $O(\log N)$ 時間で実行できます。特に、C++ の std::map には lower_bound、upper_bound というメソッドが用意されているので、これを上手く使います。

一方、手順 3、4 は、最悪で $O(N \log N)$ 時間かかるように見えます。大丈夫でしょうか？

大丈夫です。説明の便宜上、手順 4 で $E_L$ も一度削除することにして、手順 5 で $E_L$ を改めて追加することにします。すると、手順 3 で高さを確認した要素は、手順 4 で必ず削除されます。つまり、マップに追加された要素は、高々 1 回しかアクセスされません。一方、手順 5 で追加される要素は高々 3 個です（$E_L$, $L_i$, $R_i$）。そのため、マップに追加される要素の総数は初期状態を含めて高々 $(3N+1)$ 個であり、手順 3 で高さを調べる要素の総数も高々 $(3N+1)$ 個です。したがって、手順 3、4 の計算量は全体で $O(N \log N)$ であることがわかります。1 回あたりのならし計算量で表せば $O(\log N)$ になります。

以上より、このアルゴリズム全体の計算量は $O(N \log N)$ とわかります。$N \le 2.5 \times 10^5$ なので、これで十分です。

［参考］もっと直感的な説明

上の説明だけではピンと来ない人がいるかもしれないので、直感的な説明をつけておきます。以下のような例を考えます。

まずは、長いレンガを積む場合を考えます。

このとき、最大値を求めるときに全てのマスの高さを調べることになりますが、新しいレンガによって凹凸が解消されたので、以降の計算は楽になります。

同様に、短いレンガを積む場合も考えます。

このとき、凹凸は残ってしまいますが、最大値を求めるときに何マスも高さを調べる必要がないので、あまり時間をかけずにレンガを積むことができます。

「長いレンガは一度積んでしまえば凹凸が消える」「短いレンガは凹凸だらけでも積むのに時間がかからない」という性質の合わせ技により、上記のアルゴリズムは現実的な時間で実行できるというわけです。

038 Large LCM（★3）

公式資料 : 問題 038 ｜ 解説 038

【キーワード】 多倍長整数について知ろう

公式解説（解説 038）でも一言だけ触れられていますが、多倍長整数を用いるアプローチもあります。多倍長整数とは、どれだけ大きな数でも（メモリーが許す限り）扱うことのできるデータ表現のことです。$(2^{31}-1)$ あるいは $(2^{63}-1)$ といった制限を気にすることなく計算できますが、代わりに普通の整数型よりも計算が遅くなります（解説 055）。

C++ の標準ライブラリには多倍長整数を扱うためのクラスや関数が提供されず、競プロにおける C++ の数少ない弱点のひとつになっています。ただし、AtCoder では Boost の使用が認められており、その中に多倍長整数のライブラリがあるので、AtCoder に限れば弱点はほぼ解消されています⁴。ただし、ヘッダーファイルと名前空間は覚えておく必要があります。

参考までに C++ で多倍長整数を使った解答例を示しておきます。なお、bits/stdc++.h を用いる場合でも、Boost のライブラリは明示的にインクルードする必要があります。

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/number.hpp>

using namespace boost::multiprecision;
using namespace std;

constexpr long kLarge = 1000000000000000000L;

int main()
{
    cpp_int a, b;
    cin >> a >> b;
    if (const cpp_int ans = lcm(a, b); ans > kLarge) {
        cout << "Large" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

ちなみに、Python、Ruby など、一部の言語では固定長整数と多倍長整数の区別がなく、「普通に」プログラムを書くだけで AC が得られます。参考までに私の解答（Ruby）を示します。

MAX = 10 ** 18

a, b = readline.split.map(&:to_i)
lcm = a.lcm(b)
puts (lcm <= MAX) ? lcm : 'Large'

出題者の意図は見事に骨抜きにされました。なお、言語による有利／不利に関しては別の節（私的解説 067）でも取り上げます。

［参考］各言語における多倍長整数の対応

• C++
  • 標準では非対応。AtCoder では Boost.Multiprecision が使用可能。
  • boost::multiprecision::cpp_int（英語）
  • boost::multiprecision::gcd（英語）
  • boost::multiprecision::lcm（英語）
• Java/Kotlin
  • java.math.BigInteger#gcd（日本語／英語）
• Python
  • 標準の整数型（int）が多倍長整数に対応している。⁵
  • math.gcd（日本語／英語）
  • math.lcm（日本語／英語） ※ Python 3.9 以降
• Ruby
  • 標準の整数型（Integer）が多倍長整数に対応している。⁶
  • Integer.gcd（日本語／英語）
  • Integer.lcm（日本語／英語）
• Rust
  • 標準では非対応。AtCoder では num crate が使用可能。
  • num::bigint::BigInt（英語）
  • num::integer::gcd（英語）
  • num::integer::lcm（英語）
• C#
  • System.Numerics.BigInteger.GreatestCommonDivisor（日本語／英語）
• Go
  • big.Int.GCD（日本語／英語）
• JavaScript/TypeScript
  • BigInt（日本語／英語）

041 Piles in AtCoder Farm（★7）

公式資料 : 問題 041 ｜ 解説 041-P1 ｜ 解説 041-P2 ｜ 解説 041-P3

【キーワード】 特殊ケースを考える／対称性に着目する

時間はかかったのですが、ピックの定理（の中身）を知らないまま満点解に至ることができたので⁷、いわゆるアドホックな解法例として一応紹介しておきます。

何はともあれ、効率的に点の個数を数える方法を考える必要があります。凸包の辺が斜めになっている部分をどう数えるかがポイントになりそうです。そこで、凸包の辺（のひとつ）を対角線に持つ、辺が軸に平行な長方形領域を考えてみます。その長方形領域の内部は、凸包の内側（杭のある側）と外側（杭のない側）が対角線によって半分ずつに分割されるので、杭の本数もその長方形領域に含まれる格子点の個数のだいたい半分になるはずです。

上の図から、さらに正確なことがわかります。

• 対角線上にある格子点は特別扱いする必要がある（今回の場合は個数に数える）。
• 残りの格子点は、対称性から、ちょうど半分が凸包に含まれる。

対角線上にある格子点の個数は最大公約数を使えば計算できます（解説 041-P3）。これで、斜めの部分を効率的に処理するメドがつきました。

あとは、凸包の各辺について上の方法を適用して、さらにいずれの長方形領域にも含まれなかった凸包内部の格子点の個数を何とかして数える…と言いたいところですが、かなりいびつな形になりそうですし、長方形領域が重なる場合もあるので、このまま実装するのは困難を極めそうです。そこで、視点を変えて、凸包の外側にある格子点を数えることを考えます（解説 017-P2）。

「外側」を定義する必要があるので、とりあえず凸包を完全に包含する最小の長方形で囲んでみます。この長方形は、x 座標、y 座標の最大値と最小値をそれぞれ求めるだけで得られます。

そして、上の図から、求める格子点の個数は、積分の区分求積法の要領で計算できそうだということに気づきます。凸包の下半分を構成する各頂点から垂線を下ろすと、凸包外部の下側の領域が台形に区切られます。台形のうち斜めになっている部分（直角三角形）は、先に説明した方法で計算できます。残りの部分は長方形ですので、幅と高さを求めて掛け算をするだけです。

あとは、同じ格子点を重複して数えないようにするといった細かいところを詰める必要がありますが、解法の大枠はこれで説明できたと思います。なお、公式解説に合わせて、垂直分割する方式で説明しましたが、私自身の解答（Ruby）では水平に分割しています。

067 Base 8 to 9（★2）

公式資料 : 問題 067 ｜ 解説 067

【キーワード】 C++ 以外の言語が有利になる場合がある

「N 進法展開を正しく実装できますか？」というのが出題側の意図だったわけですが、言語によっては標準ライブラリに必要な機能がそろっており、その中身をきちんと理解していなくても正解のプログラムを書くことができます。

参考までに Ruby による解答例を載せます。

n, k = readline.chomp.split
k.to_i.times do
    n = n.to_i(8).to_s(9).tr('8', '5')
end
puts n

to_i が（文字列などを）整数に変換するためのメソッド、to_s が（整数などを）文字列に変換するためのメソッドです。これらのメソッドは、省略可能な引数として基数（N 進法の N にあたる数）を指定できるようになっているため、基数変換のためのコードは必要ありません。あとは 8 を 5 に置換するために tr もしくは gsub メソッドを呼び出すだけです。

一方、C++ の標準ライブラリには整数を N 進数の文字列に変換する関数がないため、自分で N 進法展開を実装する必要があって少し不利であると言えます。ほかに C++ が比較的不利になる例として多倍長整数（私的解説 038）があります。

ひとつのコンテストで複数言語を同時に使用することにはデメリットもあるのですが、使用言語によって有利／不利の差が現れる場面があることは知っておくべきかと思います（言語間格差などと呼ばれています）。C++ に関して言えば、実行速度面の優位性はとても大きいですが、多倍長整数、N 進法変換など一部のライブラリが標準では用意されていないために不利になる場面がたまにあります。

まずは最初に習った言語に十分に慣れることに集中して欲しいですが、余裕が出てきたら別の言語に目を向けるのもひとつの選択肢だろうと思います⁸。特に、業務や趣味などで使っている言語があるならば 、競プロに使えそうな機能がないか、時間のあるときにドキュメントなどを眺めてみるのもよいでしょう。

なお、$3^N$ 個のパターンからなる全探索をする場合など（解説 045）、N 進法展開の考え方が必要になる場面はほかにもあるので、どの言語を使っているにせよ一度は自分で実装することを勧めます。

［参考］各言語における N 進法変換

言語	N 進数→整数	整数→N 進数
C++	std::stoll(s, N)	なし
Java	Long.parseLong(s, N)	Long.toString(i, N)
Python	int(s, base=N)	なし
Ruby	s.to_i(N)	i.to_s(N)
Rust	i64::from_str_radix(s, N)	なし
C#	Convert.ToUInt64(s, N)	なし9
Go	strconv.ParseInt(s, N, 64)	strconv.FormatInt(i, N)
JS/TS	parseInt(s, N)	i.toString(N)

080 Let's Share Bit（★6）

公式資料 : 問題 080 ｜ 解説 080

【キーワード】 変な制約に着目する／ビット DP

キーワードは公式解説からパクりました（解説 063、解説 045）。なお、以下では $A$ と $B$ のビットごとの論理積（AND）を $A \mathbin{\&} B$ と表記します。

一番単純なのは $2^D$ 通りの値を全部確認する方法ですが、$D \le 60$ なので、さすがに制限時間には間に合いません。一方で $N$ の最大値は 20 と妙に小さいですね。まるで 2 の肩に乗せてくれとアピールしているかのようです。

$A_i$ と $x$ で共通して 1 になっているビットがひとつでもあれば $(A_i \mathbin{\&} x) \neq 0$ になることを踏まえると、ビット DP が組み立てられそうです。すなわち、$\mathit{dp}[d][\mathit{bits}]$ を、以下の条件を満たす $d$ ビットの（すなわち $2^{d}$ 未満の）整数 $x$ の個数と定義します。

• $\mathit{bits}$ の $i$ ビット目が 1 のとき $(A_i \mathbin{\&} x) \neq 0$。
• $\mathit{bits}$ の $i$ ビット目が 0 のとき $(A_i \mathbin{\&} x) = 0$。

$\mathit{dp}$ の値は $d$ の値が小さい方から順に計算していきます。$x$ の下位のビットから順番に 0/1 を決めていくというイメージです。そして、$\mathit{bits}$ の $i$ ビット目が 1 であるというのは、$(A_i \mathbin{\&} x) \neq 0$ であることが既に確定しているという意味合いを持ちます。

更新式に関しては、コードの形で見せるのが手っ取り早いと思うので、C++ による実装例を載せます。

vector<vector<long>> dp(D + 1, vector<long>(1 << N));
dp[0][0] = 1;

for (int d = 1; d <= D; d++) {
    // `m` の `i` ビット目 == `A[i]` の `d` ビット目
    int m = 0;
    for (int i = 0; i < N; i++) {
        if ((A[i] & (1L << (d - 1))) != 0) { m |= 1 << i; }
    }
    for (int bits = 0; bits < (1 << N); bits++) {
        dp[d][bits | 0] += dp[d - 1][bits];  // `d` ビット目が 0 の場合を考慮
        dp[d][bits | m] += dp[d - 1][bits];  // `d` ビット目が 1 の場合を考慮
    }
}

$d$ ビット目を 0 に決めた場合、$(A_i \mathbin{\&} x) \neq 0$ となる $i$ の集合は変わりませんので、$\mathit{bits}$ の内容はそのままです。一方、$d$ ビット目を 1 に決めた場合、$A_i$ の $d$ ビット目が 1 であるような $i$ が集合に加わりますので、$\mathit{bits}$ の値もそれに従って改めます。それが上のコードで行っていることです。

$O(D)$ のループの内部で $O(2^N)$ のループを回していますので、全体の計算量は $O(D \cdot 2^N)$ です。

---

1. 証明は読者への課題とします。 ↩

2. けんちょん氏の解説にある「しゃくとり法が使える条件」で言うと、1 番目の構造、つまり『区間 [left, right) が「条件」を満たすなら、それに含まれる区間も「条件」を満たす』に該当します。ここでいう「条件」とは「偏角の差が 180° 以下であること」です。 ↩

3. ほとんどの言語において、atan2（に相当する関数）は $[-\pi, \pi]$ の範囲の値を返します。 ↩

4. AtCoder 以外のコンテストでは Boost は使えないと思います。 ↩

5. Python 2.x では、固定長（int）と多倍長（long）の間に一応の区別がありましたが、Python 3.x で int に統一されました。もっとも、Python 2.x でも、整数が int の範囲に収まらなくなると、自動的に long に昇格する仕様でした。 ↩

6. Ruby 2.3 までは固定長（FixNum）と多倍長（BigNum）の間に一応の区別がありましたが、Ruby 2.4 で Integer に統一されました。もっとも、Ruby 2.3 以前でも、整数が FixNum の範囲に収まらなくなると、自動的に BigNum に昇格する仕様でした。 ↩

7. 公式解説を読んで「そういえばそんな定理もあったな」という気にはなったので、完全に初耳というわけではないと思います。とはいえ、公式解説を読むまでピックの定理について思い出すことはありませんでした。 ↩

8. 競プロのことだけを考えると、別の言語を習得するよりアルゴリズムの勉強をする方が効率が良いようには思います。しかし、競プロの世界を飛び出して、仕事等でプログラムを書くことになれば複数の言語を使えることは長所として働きます。また、別の言語を習得することで、もとの言語を別の視点から捉えることができるようになり、理解を深めることにもつながります。 ↩

9. Convert.ToString(i, N) というメソッドがありますが、2 進数、8 進数、10 進数、16 進数にしか対応していません。 ↩