問題概要
$Q$ 個のクアドラプレット（$4$ 要素タプル）が与えられる．$i$ 番目のクアドラプレットは $( a_i, b_i, c_i, d_i )$ である．
また，整数 $N, M $ が与えられる．以下の条件を満たす数列 $\{ A_i \}$ を考える．
- $| A | = N$
- $1 \leq A_1 \leq A_2 \leq \dots \leq A_N \leq M $
この数列 $A$ の「得点」を，
- $A_{ b_i } - A_{ a_i } = c_i$ を満たすようなクアドラプレットについての $d_i$ の総和
とする．
可能な数列の内，得点が最大のものの得点を求めよ．
制約
- $2 \leq N \leq 10$
- $1 \leq M \leq 10$
- $1 \leq Q \leq 50$
- $a_i, b_i, c_i$ はいい感じに意味のある値（原文みてください＞＜）
- $1 \leq d_i \leq 10^5$
解法
何か値を探し出したいときの最も基本的な戦略のひとつは全探索なので，ここでも全探索による解法を考えてみます．
数列を列挙したい場合，再帰関数などを用いて，数列の「戦闘要素を決める」→「$2$ 番目の要素を決める」→……→「末尾要素を決める」という工程を踏んであげれば，途中の選択肢（各要素を何にするか）を全通り試して分岐しつつ再帰することで列挙を行えます（自然言語のみだとやや説明しづらいのでコード参照）．数列の列挙ができれば，列挙された各数列について上記の得点を（ループなどを用いて）計算し，それらの最大値をとることでこの問題を解くことができます．
計算時間について
さて，全探索で問題を解く場合，正当性よりも実行時間が気になってきます*1．ではこの問題で，問題文で指定された条件を満たす数列はいくつぐらいあるのでしょうか？ 明らかな上界としては，数列の要素が $N$ 個あって，それぞれに最大 $M $ 通りの選択肢があることから $M^N$ というのが考えられます．が，$N = M = 10$ というケースを考えてみるとこれはちょっと大きすぎて TLE しそうです*2．しかし，数列が昇順列でなければならないことから，$M^N$ 個全ての数列が条件を満たすわけではなく，よくよく考えてみると条件を満たす数列は案外少ないということが分かります．では見ていきましょう．
昇順列の個数を考えるために，昇順列と一対一対応する別の対象を考えます*3．ある昇順列 $X$ が与えられたとします．このとき，各整数が $X$ に出現する回数を記録した列 $Y$ （「ヒストグラム」と呼ぶことにします）を構成することができます．もう少しちゃんと書くなら，
- $Y_i = X$ で $i$ が出現する個数
となるような列 $Y$ です（長さは適当に $M $ ぐらいでクリップします）．このとき，$X$ から $Y$ は一意的に構成され，逆に，$Y$ から $X$ も一意的に構成されます（値の昇順に，指定された個数ずつ並べるしかないため）．つまり，昇順列とヒストグラムの間には一対一対応（全単射）があり，個数は等しくなります．
さて，ヒストグラムを一つ決めるためには $1$ から $M $ の各整数について使う個数を決めて，個数の和が $N$ になっていればよいです．これは言い方を変えれば，「$1$ から $M $ までの整数から，重複を許して $N$ 個選ぶ」という操作で（使う個数を $1$ ずつインクリメントする気持ち），巷で言うところの「重複組合せ」です．証明等の諸々を他所様におまかせするとして，最大ケースで 計算してみると手に負えそうな個数であることが分かります．
コード
using VI = vector< int >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; } template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; } void in_impl(){}; template < typename T, typename... TS > void in_impl( T &head, TS &... tail ){ cin >> head; in_impl( tail ... ); } #define IN( T, ... ) T __VA_ARGS__; in_impl( __VA_ARGS__ ); #define NUMBERED( name, number ) NUMBERED2( name, number ) #define NUMBERED2( name, number ) name ## _ ## number #define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n ) #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ ) #define SZ( v ) ( (int)( v ).size() ) template < typename T > inline bool chmax( T &a, const T &b ){ if ( a < b ) { a = b; return true; } return false; } #define PB push_back constexpr auto INF = LIM<>::max() / 2; int solve( const int N, const int M, const VI &A, const VI &B, const VI &C, const VI &D, VI &xs ) { const int Q = SZ( A ); if ( SZ( xs ) == N ) { int res = 0; REP( i, Q ) { if ( xs[ B[i] ] - xs[ A[i] ] == C[i] ) { res += D[i]; } } return res; } int res = -INF; REP( i, ( xs.empty() ? 0 : xs.back() - 1 ), M ) { xs.PB( i + 1 ); chmax( res, solve( N, M, A, B, C, D, xs ) ); xs.pop_back(); } return res; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N, M, Q ); VI A( Q ), B( Q ), C( Q ), D( Q ); REP( i, Q ) { cin >> A[i] >> B[i] >> C[i] >> D[i]; --A[i], --B[i]; } VI xs; cout << solve( N, M, A, B, C, D, xs ) << endl; return 0; }
