https://nitrone7.hatenablog.com/entry/2025/04/21/pairscoreattack

はじめに

Q. この記事今更出すの？
A. わかる

前置き

こんにちは，Морожеです🛰️^*1

現在，ポップンミュージックという人気音楽ゲームで非公式のスコアアタック企画のペアスコアタが開催されています。ペアスコアタはその名前の通り，プレイヤーが 2 人集まってペアでチームを組んで参加するスコアタです。僕も友だちとペアを組んで参加しています。

ペアスコアタ3 -THE FINAL-
只今よりエントリーを開始します！
今回はDiscordを利用した開催となります。Discord不可の方はDM解放可能な方のみ参加可能です。

画像の詳細をペアの方とご確認の上、エントリーをお待ちしております。https://t.co/bRxZpgWRJn

#ペアスコアタ pic.twitter.com/JI7mU75oWo
— mayo:) (@mayo_mst) 2025年3月9日

twitter.com

さて，ペアスコアタには「お祭り部門」という企画があります。これの企画は，課題曲に設定された 2 曲があり，それぞれのプレイヤーが各課題曲で出した得点の和をできるだけ近づけるというものです。たとえば，

プレイヤー X が
- 課題曲① で 94000 点のリザルト，
- 課題曲② で 93500 点のリザルト（合計 187500）を，
プレイヤー Y が
- 課題曲① で 92750 点のリザルト，
- 課題曲② で 94250 点のリザルト（合計 187000）を

提出するケースでは，「それぞれのプレイヤーの得点の和」の差の絶対値が |187500-187000| = 500 点となります。チームメンバーたちは何度も課題曲をプレーして色々なリザルトを生成し，差の絶対値を最小化することを目標にします。

ルールに関して質問があり、先日ご案内した内容を含めた全体のルール説明を再掲します。
繰り返しのご案内になる部分も多々ありますが、各チームの方は今一度ご確認ください。#ペアスコアタ pic.twitter.com/ORNrJO4XDO
— mayo:) (@mayo_mst) 2025年3月20日

twitter.com

※ 今回は条件 2 と 3 は無視します。

ところで，リザルトがたくさんある時，差の絶対値を最小化するような組み合わせはどのように見つければいいでしょうか？例えば，今集まっているリザルトが次のようになっている場合，どのように選ぶのが最適でしょうか？

プレイヤー X
- 課題曲①: 94155 点, 93517 点, 91477 点
- 課題曲②: 93566 点, 90494 点, 90989 点
プレイヤー Y
- 課題曲①: 92051 点, 91764 点, 87332 点
- 課題曲②: 90054 点, 94634 点, 92985 点

この記事では，最適解を求める方法とコード(C++)を紹介します。（環境があればお手元でも走らせてみてください）

厳密な問題設定

$N_A$ 個の整数からなる列 $A = ( a_1, a_2, ..., a_{N_A})$ ，
$N_B$ 個の整数からなる列 $B = ( b_1, b_2, ..., b_{N_B})$ ，
$N_C$ 個の整数からなる列 $C = ( c_1, c_2, ..., c_{N_C})$ ，
$N_D$ 個の整数からなる列 $D = ( d_1, d_2, ..., d_{N_D})$ がある。
$\displaystyle \left|(a_{(1 \leq i \leq N_A)}+b_{(1 \leq j \leq N_B)})-(c_{(1 \leq k \leq N_C)}+d_{(1 \leq l \leq N_D)})\right|$
を最小化せよ。

条件

$N_A, N_B, N_C, N_D$ は $1$ 以上の整数
$N = N_A + N_B + N_C + N_D$ としたとき， $N \leq 10^5$
列の要素 $x$ は整数で， $0 \leq x \leq 10^5$

入力フォーマット

N_A N_B N_C N_D
a_1 a_2 ... a_(N_A)
b_1 b_2 ... b_(N_B)
c_1 c_2 ... c_(N_C)
d_1 d_2 ... d_(N_D)

全探索

一番簡単に思いつく方法で，列 A, B, C, D から 1 つづつ選ぶ組み合わせ $N_A × N_B × N_C × N_D$ 通りを全て試します。プログラミング的にはいわゆる 4 重ループになります。

実際の C++ コード（クリック　or タップで開閉）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

int main(){
    int N_A, N_B, N_C, N_D;
    std::cin >> N_A >> N_B >> N_C >> N_D;
    
    std::vector<int> A(N_A);
    for ( auto &t : A ) std::cin >> t;
    std::vector<int> B(N_B);
    for ( auto &t : B ) std::cin >> t;
    std::vector<int> C(N_C);
    for ( auto &t : C ) std::cin >> t;
    std::vector<int> D(N_D);
    for ( auto &t : D ) std::cin >> t;

    int minDiff = std::numeric_limits<int>::max();
    for( int a : A ){
        for( int b : B ) {
            for( int c : C ){ 
                for( int d : D ){
                    minDiff = std::min( minDiff, abs((a+b)-(c+d)) );
                }
            }
        }
    }
    
    std::cout << minDiff << std::endl;
    return 0;
}

最小値を構成する $(i, j, k, l)$ も実際に求めたい場合は，ループをもう一度回して最小値になったときに記録すれば良いです。

時間計算量は $\Theta (N^4)$ です。

二分探索

先程の 4 重ループはとても書きやすい処理ですがちょっと重いですね。課題曲を粘着しすぎて，勢い余ってリザルトを 1000 枚くらい生成してしまったパターンも考えられると思います。ちょっとした工夫をして高速化してみましょう。

まず，列 $A$ と $B$ の要素からそれぞれ選んだときの和の全通りを列 $X$ に格納しておきます。列 $C$ と $D$ に対しても同様に行い，列 $Y$ に格納します。
列 $Y$ をソートし，列 $X$ から要素 $x$ を一つ取り出して， $x$ に最も近い列 $Y$ の要素 $y$ を二分探索で探します。

二分探索とは？（クリック or タップで開閉）

ソートされた列（広義単調増加ならなんでも良い）の中から値を見つけるときに，列のすべての要素を見るのではなく，「今見ている範囲の真ん中にある値を基準に，見る範囲を半分に狭める」ことを繰り返す方法です。日常的な例としては，文字ごとの印がついていない辞書を使って，目当ての単語を引く時のやり方をイメージすると良いです。
見る範囲がだんだん半分に減っていくので，例えば列の長さが 10 億くらいあっても 30 回ほどで探索が終了します^*2。

具体的には: 列 $Y$ に対して，「今見ている値は $x$ 以上かどうか？」で探索範囲を狭めていくと，「列 $Y$ に含まれる数の中で， $x$ 以上で最も小さいもの」が見つかります。 $x$ に最も近い列 $Y$ の要素の候補は，「 $x$ 以上で最も小さいもの」または「 $x$ 未満で最も大きいもの」の 2 通りしかないので，両方に対して差の絶対値を計算して，小さい方を採用します。

時間計算量は $\Theta (N^2\log N)$ です。 $N = 1000$ とかでも一瞬で終わりますね。

実際の C++ コード（クリック　or タップで開閉）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

int main(){
    int N_A, N_B, N_C, N_D;
    std::cin >> N_A >> N_B >> N_C >> N_D;
    
    std::vector<int> A(N_A);
    for ( auto &t : A ) std::cin >> t;
    std::vector<int> B(N_B);
    for ( auto &t : B ) std::cin >> t;
    std::vector<int> C(N_C);
    for ( auto &t : C ) std::cin >> t;
    std::vector<int> D(N_D);
    for ( auto &t : D ) std::cin >> t;
    
    std::vector<int> sumAB, sumCD;
    for( int a : A ){
        for ( int b : B ){
            sumAB.push_back(a+b);
        }
    }
    for( int c : C ){
        for( int d : D ){
            sumCD.push_back(c+d);
        }
    }

    std::sort(sumCD.begin(), sumCD.end());
    int minDiff = std::numeric_limits<int>::max();
    for ( int x : sumAB ) {
        auto it = std::lower_bound(sumCD.begin(), sumCD.end(), x);
        if ( it != sumCD.end() ) minDiff = std::min(minDiff, abs(x-*it));
        if ( it != sumCD.begin() ) {
            --it;
            minDiff = std::min(minDiff, abs(x-*it));
        }
    }

    std::cout << minDiff << std::endl;
    return 0;
}

更なる高速化

ところでこのゲームは pop'n music なので，スコアは $0$ 以上 $10^5$ 以下です。 $M = 10^5$ とします。

突然ですが列 $A$ と $B$ を $M$ 次多項式とみなします。すなわち，

$\displaystyle X_A = \sum_{1 \leq i \leq N_A} x^{a_i}, \quad X_B= \sum_{1 \leq i \leq N_B} x^{b_i}$

とします。列 $A$ と $B$ の要素からそれぞれ選んで足してできる全通りの値は， $X_A$ と $X_B$ の積の，係数が 1 以上の項の次数を見ることで求まります。

例えば， $A = (0, 1, 3, 5)$ ， $B = (3, 4, 10)$ のとき，

$\displaystyle X_A = 1 + x^1 + x^3 + x^5$
$\displaystyle X_B = x^3 + x^4 + x^{10}$

であり，これらの積が（モバイル端末から見てる人は右にスクロール）

$\displaystyle X_A X_B = x^3 + 2x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11} + x^{13} + x^{15}$

となることから，列 $A$ と $B$ の要素からそれぞれ選んだときの和の全通りが $(3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15)$ であることが分かります。ところで，多項式の積は高速フーリエ変換を経由することで $\Theta (M \log M)$ で求められますね。

FFT（高速フーリエ変換）とは？（クリックorタップで開閉）

離散フーリエ変換を分割統治で高速化するアルゴリズムです。これと "時間領域におけるたたみこみ ⇄ 周波数領域における積" を利用することで，多項式の積を高速に計算できます。FFT 自体は有名なアルゴリズムなのでインターネット上のわかりやすい記事（これとか）を見るのが良いと思います（丸投げ）

あとは上の解法と同じで，二分探索で和の近い組み合わせを見つけます。時間計算量は $\Theta (N+M \log M)$ で， $N = 10^6$ 個のデータを入れても 0.5 秒もかからず結果が出る程度には高速に動作します。FFT は定数倍が重いので注意。

実際の C++ コード^*3（クリック or タップで開閉）

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <algorithm>

using cd = std::complex<double>;
const double PI = std::acos(-1);

void fft(std::vector<cd> &a, bool invert) {
    int n = a.size();
    if (n == 1) return;

    std::vector<cd> a0(n/2), a1(n/2);
    for (int i = 0; 2 * i < n; i++) {
        a0[i] = a[i*2];
        a1[i] = a[i*2 + 1];
    }

    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * PI / n * (invert ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; 2 * i < n; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n/2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n/2] /= 2;
        }
        w *= wn;
    }
}

std::vector<int> multiply(const std::vector<int> &a, const std::vector<int> &b) {
    std::vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n); fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);

    std::vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = std::round(fa[i].real());
    return result;
}

int main() {
    std::vector<int> N(4);
    for( auto &n : N ) std::cin >> n;
    
    std::vector<int> score[4];
    std::vector<int> maxscore(4);

    for( int k = 0; k < 4; k++ ){
        maxscore[k] = 0;
        for( int i = 0; i < N[k]; i++ ){
            int temp; std::cin >> temp;
            score[k].push_back(temp);
            maxscore[k] = std::max(maxscore[k], score[k][i]);
        }
    }

    std::vector<int> sumAB, sumCD;
    
    for( int k = 0; k < 2; k++ ){
        std::vector<int> XA(maxscore[k*2]+1, 0), XB(maxscore[k*2+1]+1, 0);
        for( int a : score[k*2] ) XA[a]++;
        for( int b : score[k*2+1] ) XB[b]++;
        std::vector<int> XAB = multiply(XA, XB);
        for( int i = 0; i < XAB.size(); i++ ){
            if( XAB[i] > 0 ){
                switch(k){
                    case 0: sumAB.push_back(i); break;
                    case 1: sumCD.push_back(i); break;
                }
            }
        }
    }
    
    int minDiff = std::numeric_limits<int>::max();

    for ( int x : sumAB ) {
        auto it = std::lower_bound(sumCD.begin(), sumCD.end(), x);
        if ( it != sumCD.end() ) minDiff = std::min(minDiff, abs(x-*it));
        if ( it != sumCD.begin() ) {
            --it;
            minDiff = std::min(minDiff, abs(x-*it));
        }
    }
    
    std::cout << minDiff << std::endl;
    return 0;
}

同じ処理が続いて冗長な部分はまとめています。

ちなみに

4 重ループで書いたところで，仮にプレイヤーが各曲 50 枚リザルトを撮った場合でもループの回数は 6250000 回と対して大きくならず，処理も 1 秒以内に終わるため，実用的な観点ではこの記事はほとんど意味がありません（実際，わなうさんのこのツールでは 4 重ループが採用されています）。

あと僕らのペアなんですが，

お祭り部門3位確定したしここだけやや喋るか

🐈‍⬛ ͗「お祭り部門、忘れる前にやっときません？」
🦖「🆗 とりあえず何回かずつやるか」

🐈‍⬛ ͗「Fly far bounce 32点差出た」
🦖「草」 pic.twitter.com/qR2xQW5VUZ
— 🎹ZEKKI🎮 (@otoge_de_zekki) 2025年4月13日

（Spiral Clouds最後の赤ロングを押しながら）
🐈‍⬛ ͗「この並び隣で見た気がするしワンチャンで赤捨てるか」
🦖「それ同点あるよ」
🐈‍⬛ ͗「キターーーー」 pic.twitter.com/qVeuYolym2
— 🎹ZEKKI🎮 (@otoge_de_zekki) 2025年4月13日

（Fly far bounce 適当に952調整狙い）
🐈‍⬛ ͗「@🦖 このぐらいの点数のリザルト持ってない？」
🦖「同点あるんだけど　マジで何？」
🐈‍⬛ ͗「草　順位確定したわ終わり終わり」 pic.twitter.com/sISKAdCE4P
— 🎹ZEKKI🎮 (@otoge_de_zekki) 2025年4月13日

なんか 30 分やったら 2 曲とも同点が出てしまったので，最小値は当然 $0$ で最小値を構成する $(i, j, k, l)$ も自明です。対戦ありがとうございました。

*1:これは pop'n music のパラボーというキャラを表しています（パラボーかわいくない？）

*2: $2^{30} \fallingdotseq 10^9$ なので

*3:FFT 部分はめんどくさいので GPT-4o に丸投げ