結果
| 問題 | No.2387 Yokan Factory |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-07-22 08:53:06 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,486 ms / 5,000 ms |
| コード長 | 53,737 bytes |
| コンパイル時間 | 4,372 ms |
| コンパイル使用メモリ | 270,740 KB |
| 実行使用メモリ | 25,792 KB |
| 最終ジャッジ日時 | 2024-09-22 08:48:33 |
| 合計ジャッジ時間 | 15,380 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
6,816 KB |
| testcase_01 | AC | 3 ms
6,940 KB |
| testcase_02 | AC | 3 ms
6,940 KB |
| testcase_03 | AC | 3 ms
6,940 KB |
| testcase_04 | AC | 3 ms
6,944 KB |
| testcase_05 | AC | 4 ms
7,236 KB |
| testcase_06 | AC | 4 ms
7,112 KB |
| testcase_07 | AC | 4 ms
6,940 KB |
| testcase_08 | AC | 3 ms
6,944 KB |
| testcase_09 | AC | 4 ms
6,976 KB |
| testcase_10 | AC | 3 ms
6,940 KB |
| testcase_11 | AC | 3 ms
6,940 KB |
| testcase_12 | AC | 3 ms
6,940 KB |
| testcase_13 | AC | 3 ms
6,940 KB |
| testcase_14 | AC | 3 ms
7,492 KB |
| testcase_15 | AC | 562 ms
21,952 KB |
| testcase_16 | AC | 312 ms
20,420 KB |
| testcase_17 | AC | 1,486 ms
25,792 KB |
| testcase_18 | AC | 1,007 ms
17,584 KB |
| testcase_19 | AC | 710 ms
14,660 KB |
| testcase_20 | AC | 348 ms
12,996 KB |
| testcase_21 | AC | 1,098 ms
16,836 KB |
| testcase_22 | AC | 338 ms
12,352 KB |
| testcase_23 | AC | 901 ms
14,532 KB |
| testcase_24 | AC | 417 ms
13,744 KB |
| testcase_25 | AC | 391 ms
11,844 KB |
| testcase_26 | AC | 1,196 ms
15,556 KB |
| testcase_27 | AC | 652 ms
16,196 KB |
| testcase_28 | AC | 5 ms
6,944 KB |
| testcase_29 | AC | 7 ms
6,944 KB |
| testcase_30 | AC | 6 ms
6,940 KB |
| testcase_31 | AC | 7 ms
7,360 KB |
| testcase_32 | AC | 5 ms
6,944 KB |
| testcase_33 | AC | 5 ms
6,944 KB |
| testcase_34 | AC | 8 ms
7,616 KB |
| testcase_35 | AC | 7 ms
6,940 KB |
| testcase_36 | AC | 4 ms
6,948 KB |
| testcase_37 | AC | 4 ms
6,944 KB |
ソースコード
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
#define CERR( MESSAGE ) cerr << MESSAGE << endl;
#define COUT( ANSWER ) cout << ANSWER << endl
#define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#define START_WATCH( PROCESS_NAME ) StartWatch( PROCESS_NAME )
#define STOP_WATCH( HOW_MANY_TIMES ) StopWatch( HOW_MANY_TIMES )
#else
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
#define CERR( MESSAGE )
#define COUT( ANSWER ) cout << ANSWER << "\n"
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH
#define START_WATCH( PROCESS_NAME )
#define STOP_WATCH( HOW_MANY_TIMES )
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS_ )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#ifdef DEBUG
inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
void StartWatch( const string& process_name = "nothing" );
void StopWatch( const int& how_many_times = 1 );
#endif
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( ( MODULO ) + ( ( ARGUMENT ) % ( MODULO ) ) ) % ( MODULO ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
static ll ANSWER[CONSTEXPR_LENGTH]; \
static ll ANSWER_INV[CONSTEXPR_LENGTH]; \
static ll INVERSE[CONSTEXPR_LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_INDEX ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= ( MODULO ); \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_INDEX ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = ( MODULO ) - ( ( ( ( MODULO ) / i ) * INVERSE[ ( MODULO ) % i ] ) % ( MODULO ) ) ) %= ( MODULO ); \
} \
} \
// 二分探索テンプレート
// EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER = MINIMUM; \
if( MINIMUM <= MAXIMUM ){ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( "二分探索中： " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY_FOR_CHECK 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \
} \
ANSWER = UPDATE_ANSWER; \
} \
CERR( "二分探索終了： " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << ( EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) << TARGET ); \
CERR( ( EXPRESSION DESIRED_INEQUALITY TARGET ? "二分探索成功" : "二分探索失敗" ) ); \
assert( EXPRESSION DESIRED_INEQUALITY TARGET ); \
} else { \
CERR( "二分探索失敗： " << MINIMUM << ">" << MAXIMUM ); \
assert( MINIMUM <= MAXIMUM ); \
} \
// 単調増加の時にEXPRESSION >= TARGETの最小解を格納。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調増加の時にEXPRESSION <= TARGETの最大解を格納。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調減少の時にEXPRESSION >= TARGETの最大解を格納。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 単調減少の時にEXPRESSION <= TARGETの最小解を格納。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \
// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define ASK_NUMBER( ... ) \
CERR( "問題の区分は以下の中で何番に該当しますか？" ); \
problems = { __VA_ARGS__ }; \
problems_size = problems.size(); \
FOR( i , 0 , problems_size ){ \
CERR( i << ": " << problems[i] ); \
} \
cin >> num; \
CERR( "" ); \
num_temp = 0; \
if( num < 0 || num >= problems_size ){ \
CERR( "返答は" << problems_size - 1 << "以下の非負整数にしてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return -1; \
} \
#define ASK_YES_NO( QUESTION ) \
CERR( QUESTION << "[y/n]" ); \
cin >> reply; \
if( reply != "y" && reply != "n" ){ \
CERR( "y/nのいずれかで答えてください。" ); \
CERR( "終了します。" ); \
CERR( "" ); \
return -1; \
} \
CERR( "" ); \
int LibrarySearch( int num = -1 )
{
vector<string> problems{};
int problems_size = 13;
int num_temp = 0;
string reply{};
if( num == -1 ){
ASK_YES_NO( "ライブラリーを探索しますか？" );
if( reply == "y" ){
CERR( "ライブラリーを探索します。" );
} else {
CERR( "ライブラリーを探索せずに続行します。" );
CERR( "" );
return 0;
}
ASK_NUMBER(
"数や関数に関する問題。" ,
"配列に関する問題。" ,
"文字列に関する問題。" ,
"順列に関する問題。" ,
"矩形領域に関する問題。" ,
"グラフに関する問題。" ,
"確率／期待値に関する問題。" ,
"ゲームに関する問題。" ,
"論理に関する問題。" ,
"半順序集合に関する問題。" ,
"関数適用に関する問題。" ,
"構築問題。"
);
} else {
CERR( "" );
}
CEXPR( int , num_graph , 5 );
CEXPR( int , num_game , 7 );
if( num == num_temp++ ){
ASK_YES_NO( "入力は１つの数か、１つの数と法を表す数ですか？" );
if( reply == "y" ){
CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "次に出力の定義と等価な式を考察しましょう。" );
CERR( "- 単調ならば、冪乗や階乗" );
CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" );
CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
CERR( " オイラー関数、約数の個数など" );
CERR( "を検討しましょう。" );
} else {
ASK_NUMBER(
"求解問題。" ,
"最大化問題。" ,
"数え上げ問題。" ,
"ソート問題。"
);
if( num == num_temp++ ){
CERR( "まず" );
CERR( "- 単調関数は二分探索" );
CERR( "- 可微分関数はニュートン法" );
CERR( "- 一次関数は掃き出し法" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "それらが間に合わない時は" );
CERR( "- 探索範囲を絞れそうな場合は全探策" );
CERR( "- 多変数の合成関数で表せる場合は半分全列挙" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 凸関数は三分探索" );
CERR( "- 可微分関数は微分のニュートン法" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 変数の対称性があれば大小関係を制限した全探策" );
CERR( "- 何らかの約数となるなど動く範囲が狭い変数があればそれらを決め打った全探策" );
CERR( "- 多変数の合成関数で表せる場合は半分全列挙" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "集合Sを何らかの順序でソートした配列aに関する問題で、" );
CERR( "- 与えられた要素sが下から何番目かを答える場合は、非負整数iごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、iに関する二分探索" );
CERR( "- 与えられた非負整数iに対するa[i]を答える場合は、Sの要素sごとに" );
CERR( " 不等式a[i]<=sを判定する方法を考察し、sに関する二分探索" );
CERR( "を検討しましょう。" );
}
}
CERR( "" );
ASK_YES_NO( "マルチテストケースですか？" );
if( reply == "y" ){
CERR( "テストケース全体でのNの総和に直接上限が与えられている問題では、" );
CERR( "ライブラリーの使用時は、配列の初期化が各テストケースに必要となる場合に" );
CERR( "TLEとなる可能性が高いです。適宜動的配列に置き換えましょう。" );
CERR( "" );
CERR( "配列を手元の環境でデバッグしやすくするためにstaticをつけている場合は" );
CERR( "テストケースを跨いで値が残ってしまわないように注意しましょう。" );
CERR( "" );
CERR( "前計算の候補としては" );
CERR( "- 素数列挙" );
CERR( "- １つまたは複数の整数の約数列挙" );
CERR( "- オイラー関数の値の列挙" );
CERR( "- サブゴールとなる関係式を満たす解の列挙" );
CERR( "を検討しましょう。" );
} else {
CERR( "入力が大きい場合と小さい場合で解法を変える考察を忘れないようにしましょう。" );
}
CERR( "" );
} else if( num == num_temp++ ){
ASK_YES_NO( "入力に配列が与えられますか？" );
if( reply == "y" ){
ASK_NUMBER(
"区間等の領域処理問題。" ,
"成分を受け取る関数の総和問題" ,
"部分列を受け取る関数の総和問題" ,
"その他の関数に関する問題。" ,
"隣接成分間関係式に関する問題。"
);
if( num == num_temp++ ){
ASK_NUMBER(
"可換群構造+を使う問題。" ,
"可換羃等モノイド構造∨を使う問題。" ,
"モノイド構造*を使う問題。" ,
"非結合的マグマ構造*を使う問題。" ,
"集合へのマグマ作用(*,\\cdot)を使う問題。" ,
"モノイドへのマグマ作用(+,\\cdot)を使う問題。" ,
"定数とのmaxを取った値の区間和取得を使う問題。"
);
if( num == num_temp++ ){
CERR( "- 区間加算／区間取得が必要ならば可換群BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template" );
CERR( "- 一点代入／一点加算／区間取得が必要ならば可換群平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template" );
CERR( "- 区間以外の領域で加算／全更新後の一点取得が必要ならば階差数列" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点代入／区間加算／一点取得／区間取得が必要ならば可換羃等モノイドBIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点代入／区間取得が必要ならばモノイドBIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( "- 一点加算／区間加算／一点取得／区間取得が必要ならばモノイド平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- 一点代入／一点取得／区間取得が必要ならばモノイドセグメント木" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SegmentTree" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 写像のコード化" );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "によりモノイドに帰着させることを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 一点作用／区間作用／一点取得が必要ならば双対平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "- 区間代入／区間作用／区間加算／一点取得／区間取得が必要な場合は遅延評価平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "maxで全体更新でなく区間更新をする場合の汎用的な解法は分かりません。" );
CERR( "例えば区間が包含について単調でmaxを取る値も単調であれば全体更新と" );
CERR( "同様の処理ができます。状況に応じた考察をしましょう。" );
CERR( "" );
CERR( "maxで全体更新をする場合、maxを取る値は単調である場合に帰着できます。" );
CERR( "maxで全体更新をしない場合、つまりただmaxの区間和を処理するだけの場合、" );
CERR( "クエリの順番を入れ替えることができるので、単調な全体更新に帰着できます。" );
CERR( "従って以下では単調な全体更新の問題を考えます。" );
CERR( "" );
CERR( "maxを取る定数を変数化し、元の値との大小を表す{0,1}値の係数を考えます。" );
CERR( "すると区間作用前後の値は統一的にその係数と変数を使って表せます。" );
CERR( "配列の各成分の係数の値が変化するイベントとクエリをソートして管理し、" );
CERR( "クエリがイベントを跨ぐたびに係数を更新することを検討しましょう。" );
CERR( "" );
CERR( "例えばクエリB_qに対するmax(A_i,B_q)の区間和は、" );
CERR( "- 優先度つきキューA'={(A_i,i)|i}（構築O(N log N)）" );
CERR( "- (B_q,q)_qをソートしたB'（構築O(Q log Q)）" );
CERR( "- 長さNの数列C=(0,...,0)（構築O(N)）" );
CERR( "を用意し、B'を前から探索して順に各クエリ(B_q,q)を処理します。" );
CERR( "具体的にはA'を前から探索して順にA_i<B_qとなる各iに対し" );
CERR( "- A'から(A_i,i)を削除（クエリ合計O(N)）" );
CERR( "- A_iを0に更新（クエリ合計O(N log N)）" );
CERR( "- C_iを1に更新（各クエリO(log N)）" );
CERR( "- A+C×B_qの区間和取得（各クエリO(log N)）" );
CERR( "とすれば合計O((N + Q)log N + Q log Q)で処理できます。" );
}
} else if( num == num_temp++ ){
ASK_YES_NO( "総和を取る前に配列に操作をする問題ですか？" );
if( reply == "y" ){
CERR( "関数が一次式の場合、実質内積と定数の和となります。" );
CERR( "内積は片方の添え字を反転させることで畳み込みに帰着させることができます。" );
CERR( "配列への操作がシフトである場合は繰り返し内積を求めることになるので、" );
CERR( "適当な法での高速フーリエ変換" );
CERR( "\\Mathematics\\Arithmetic\\Mod" );
CERR( "\\Mathematics\\Polynoial" );
} else {
CERR( "関数を予め各成分に適用してしまえば、ただの総和に関する問題となります。" );
CERR( "" );
ASK_NUMBER(
"部分和の最大化問題。" ,
"部分和を固定した部分列の数え上げ問題。" ,
);
if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限W（多変数も可）、価値（和を取る値）の上限Vとします。" );
CERR( "- B=∞ならば、通常のナップサック問題と同様の動的計画法" );
CERR( "- B<∞でO(2^N)が通りそうならば愚直に全探策" );
CERR( "- B<∞でO(N 2^{N/2})が通りそうならば半分全列挙" );
CERR( "- B<∞で重みと価値が等しくO(NV)が通りそうならば[B-V,B+V]での実現可能性を" );
CERR( " 遷移する動的計画法" );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- Wが10^5オーダーで重みと価値が等しくO((N+W)log_2 W)が通りそうならば" );
CERR( " 適当な法での畳み込み（確率的解法）" );
CERR( " \\Mathematics\\Polynomial" );
CERR( "- 選択に順序と制約がある場合、O(N 2^N)が通りそうならばbit全探策" );
} else if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限Wとします。" );
CERR( "- 重みと価値が異なりO(2^N)が通りそうならば愚直な２変数多項式乗算" );
CERR( "- 重みと価値が等しくO(2^N)が通りそうならば愚直な１変数多項式乗算" );
CERR( "- 重みと価値が等しくO(2^{N/2}N)が通りそうならば半分ずつ多項式乗算を" );
CERR( " して最後にそれらの積の１係数のみの計算" );
CERR( "- 重みと価値が等しくWが10^5オーダーで法が与えられていてO((N+W)log_2 W)が" );
CERR( " 通りそうならば適当な法での高速フーリエ変換" );
CERR( " \\Mathematics\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
}
}
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "配列を受け取る関数fが与えられているとします。" );
CERR( "以下、連続部分列を扱う問題について考えます。" );
CERR( "連続とは限らない部分列の場合、分割に区間でなく部分集合を使います。" );
CERR( "" );
CERR( "配列Aの分割Pに対し、Pの各成分pを渡るf(p)の総和をF(P)と置きます。" );
ASK_YES_NO( "fがbit演算である問題ですか？" );
if( reply == "y" ){
CERR( "「配列の第i成分までで切った時にj桁目に1の立つ個数dp[i][j]」" );
CERR( "を管理するi,jに関する動的計画法を検討しましょう。" );
CERR( "更にその計算量を評価し、適宜bitsetやデータ構造で高速化しましょう。" );
} else {
CERR( "Pの末尾pを削除した分割P'が元の配列からpを削除した配列の分割であり" );
CERR( "F(P)=F(P')+f(p)と表せることに注意して、" );
CERR( "- F(P)の最大化問題は" );
CERR( " 「第i成分までで切った時のF(P)たちの最大値dp[i]」" );
CERR( " を管理するiに関する動的計画法（O(N^2×fの計算量)）" );
CERR( "- F(P)が固定された時のPの数え上げ問題は" );
CERR( " 「第i成分までで切った時のF(P)=vを満たすPの個数dp[i][v]」" );
CERR( " を管理するi,vに関する動的計画法（O(N^2 v_max×fの計算量)）" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "更にfが部分列の長さに関する再帰的な構造を持つ場合、全ての連続部分列に" );
CERR( "対しfの値を前計算することを検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "配列を受け取る関数Fが与えられているとします。与えられた配列Aに" );
CERR( "何らかの処理をして得られる配列Bに対するF(B)の最大化問題は、" );
CERR( "最大化すべき式のサブゴールfに表れる項xのうち決め打ちやすいものを探しましょう。" );
CERR( "- 配列の長さをiで打ち切った時のxの候補数をX(i)" );
CERR( "- 配列の長さをiで打ち切ってxを決め打った時の配列の長さi+1でのxの候補数をdX(i)" );
CERR( "と置きます。" );
CERR( "- O(sum_i X(i) dX(i))が通りそうでfがxからO(1)で計算できるならば、iとxに関する動的計画法" );
CERR( "- O(N log_2 X(N))が通りそうで" );
CERR( " - fがxからO(N)で計算できxに関して単調ならば、xの二分探索" );
CERR( " - fがxからO(N/x)で計算できるならば、xの全探索" );
CERR( "- O(N log_2 N)が通りそうでxを上手く並び替えるとfがxからO(log_2 N)で計算できるならば、" );
CERR( " 優先度つきキューなどでのxの管理" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
ASK_NUMBER(
"関係式を満たす部分列の最長化問題。" ,
"関係式を満たす部分列の数え上げ問題。"
);
if( num == num_temp++ ){
CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ" );
CERR( " 配列を用いて、それらの部分列の末尾である項を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence" );
CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ" );
CERR( " 連想配列を用いて、それら部分列の長さの最大値を記録すること" );
CERR( " \\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence\\Subwalk" );
CERR( "を検討しましょう。" );
} else {
ASK_NUMBER(
"連続部分列の数え上げ問題。" ,
"連続とは限らない部分列の数え上げ問題。" ,
"部分順列（部分列の並び換え）の数え上げ問題。" ,
);
CERR( "長さNの配列Aと、L+n<=N+1を満たす整数n,Lと" );
CERR( "- 整数iに関する条件Q(i)" );
CERR( "- 各0<=l<Lに対するn-tuple(b_0,...,b_{n-1})に関する条件R_l(b_0,...,b_{n-1})" );
CERR( "が与えられているとし、配列Bの条件P(B)を" );
CERR( "「Bの長さ|B|がQ(|B|)かつ|B|<L+nを満たし、かつ任意の0<=l<=|B|-nに対し" );
CERR( " R_l(B_l,...,B_{l+n-1})が成り立つ。」" );
CERR( "の論理積として定めます。" );
CERR( "" );
CERR( "例えば山型の部分列の数え上げ問題ではN>=3かつ(n,L)=(2,2)で" );
CERR( "- Q(i)=「i=3」" );
CERR( "- R_0(b_0,b_1)=「b_0<b_1」" );
CERR( "- R_1(b_0,b_1)=「b_0>b_1」" );
CERR( "と表されます。" );
CERR( "" );
if( num == num_temp++ ){
CERR( "P(B)を満たすAの連続部分列Bの数え上げは、" );
CERR( "- R_lたちがlに依存しないならば尺取り法O(N)" );
CERR( "- R_lたちがlに依存する場合、" );
CERR( " - O(N^2)が通りそうなら左端を固定した愚直探索" );
CERR( " - O(N^2)が通らなさそうならR_lたちの読み替え" );
} else if( num == num_temp++ ){
CERR( "P(B)を満たすAの連続とは限らない部分列Bの数え上げは、" );
CERR( "- n-1<=i<=max{j<=N|Q(j)}を満たす各i" );
CERR( "- (0,1,...,N-1)の長さn-1の各部分列s" );
CERR( "に対する" );
CERR( "「長さiで、任意の0<=l<=i-nに対しR_l(B)を満たし、" );
CERR( " 末尾n-1項がsに対応するAの部分列Bの個数dp[i][s]」" );
CERR( "を管理するi,sに関する動的計画法" );
CERR( "\\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence" );
CERR( "\\Mathematics\\Combinatorial\\Counting\\IncreasingSubsequence\\Subwalk" );
} else if( num == num_temp++ ){
CERR( "P(B)を満たすAの部分順列Bの数え上げは、" );
CERR( "- n-1<=|S|<=max{j<=N|Q(j)}を満たす(0,1,...,N-1)の部分集合S" );
CERR( "- Sの長さn-1の各部分順列s" );
CERR( "に対する" );
CERR( "「任意の0<=l<=|S|-nに対しR_l(B)を満たし、末尾n-1項がsに対応し、」" );
CERR( " 全体がSに対応するAの部分順列Bの個数dp[S][s]」" );
CERR( "を管理するS,sに関する動的計画法を検討しましょう。" );
CERR( "" );
CERR( "sの網羅は[0,N)^{n-1}の全探策でもS内の順列探索と定数倍しか変わらないので" );
CERR( "実装の速さを優先しましょう。" );
CERR( "" );
CERR( "Nが小さい場合は概算値" );
CERR( "7! ≒ 5×10^3" );
CERR( "8! ≒ 4×10^4" );
CERR( "9! ≒ 4×10^5" );
CERR( "10! ≒ 4×10^6" );
CERR( "11! ≒ 4×10^7" );
CERR( "12! ≒ 5×10^8" );
CERR( "を参考に順列の全列挙" );
CERR( "\\Mathematics\\Combinatorial\\Permutation" );
}
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "特にR_l(B)たちがgcdやmaxなどの羃等演算に関する等式で与えられる場合は、" );
CERR( "不等式の方が扱いやすいのでゼータ変換／メビウス変換を検討しましょう。" );
}
}
} else {
ASK_NUMBER(
"配列を受け取る関数に関する問題。" ,
"隣接成分間関係式に関する問題。"
);
if( num == num_temp++ ){
ASK_NUMBER(
"最大化問題。" ,
"数え上げ問題。"
);
if( num == num_temp++ ){
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に可能な値全体または一部の集合dp[i]」" );
CERR( " を管理するiに関する動的計画法" );
CERR( "- 「v以上の値を取り得るか否か」が判定可能である時は" );
CERR( " vに関する二分探索" );
} else {
CERR( "- マルチテストケースで配列の種類が少ない場合は、" );
CERR( " 全ての配列に対する関数の値の前計算" );
CERR( "- 取り得る値が少なく関数が長さに関して再帰的構造を持つ場合は、" );
CERR( " 「長さiの時に値vである配列の総数dp[i][v]」" );
CERR( " を管理するi,vに関する動的計画法" );
}
} else {
CERR( "- いくつかの条件の重ね合わせの時は包除原理" );
CERR( "- 全順序の場合は数の分割方法などへの翻訳" );
CERR( "- 疎な半順序の場合はグラフの前計算" );
}
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"部分列マッチング問題。" ,
"回文探索問題。"
);
if( num == num_temp++ ){
CERR( "基本的には丁寧にループを回して解きましょう。" );
CERR( "- 比較対象が少ない場合、前または後ろから順に探索（貪欲法／動的計画法）" );
CERR( "- ワイルドカードを含む場合、" );
CERR( " - 前または後ろから順に場合分けをしてO(N)で処理できるか" );
CERR( " - 可能な代入方法を絞り込んでO(N)種類に落せるか" );
CERR( "- 比較回数が多い場合、ローリングハッシュ" );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- マッチングする文字列の最長化をする場合、Zアルゴリズム" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "- マッチングする文字数の最大化をする場合、文字の種類分の{0,1}値配列に" );
CERR( " 分けて内積の最大化（添え字を反転させて適当な法での畳み込み）" );
CERR( " \\Mathematics\\Arithmetic\\Mod" );
CERR( " \\Mathematics\\Polynomial" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "回文判定は長さに関して再帰的に計算できます。" );
CERR( "- O(N^2)が通る場合、愚直な再帰により前計算で全ての部分列の回文判定" );
CERR( "- O(N^2)が通らない場合、Manacherのアルゴリズムやローリングハッシュで前計算" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "符号の計算は転倒数の計算に帰着させましょう。" );
CERR( "符号と何かの積の和は行列式に帰着させましょう。" );
CERR( "- 行列式そのものなら行基本変形でO(N^3)" );
CERR( "- 余因子展開の途中の値はメモ化再帰でO(N 2^N)" );
CERR( "で計算できます。" );
CERR( "" );
CERR( "１つの順列の転倒数は、" );
CERR( "- O(N^2)が通りそうならば愚直な二重ループ" );
CERR( "- O(N log_2 N)が通りそうならば可換群BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "で計算しましょう。" );
CERR( "" );
CERR( "条件を満たす順列全体をわたる転倒数の総和は、" );
CERR( "各i<jごとにそこで転倒が生じる順列の個数を計算し、その総和を取りましょう。" );
CERR( "条件が良ければ、転倒が生じる順列の個数は転倒が生じるとは限らない順列の個数の" );
CERR( "半分となります。" );
} else if( num == num_temp++ ){
ASK_NUMBER(
"探索問題。" ,
"絶対値の最小／最大化問題。" ,
"その他の最小／最大化問題。"
);
if( num == num_temp++ ){
CERR( "隣接関係の定める無向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "符号を用いて絶対値を外しましょう。" );
CERR( "- 単調な式に帰着できる場合、二分探索を検討しましょう。" );
CERR( "- 最大化問題の場合、符号パターンの全探策を検討しましょう。" );
CERR( "- マンハッタン距離などは一次変換で簡単にすることを検討しましょう。" );
CERR( "複数のパラメータを決定すべき場合は、サブゴールの式の値を決め打ちましょう。" );
} else if( num == num_temp++ ){
CERR( "このケースのライブラリー探索は不完全です。" );
CERR( "- O(HW)が通りそうならば動的計画法" );
CERR( "- O(HW)が通らなさそうならば見方を変えて最短経路問題に帰着できないか" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "例えば迷路の攻略可能性は" );
CERR( "- スタートとゴールが同一の弧状連結成分に属すこと" );
CERR( "- スタートとゴールを分断する壁のパスの非存在性" );
CERR( "などから翻訳できます。" );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"２点最短径路（迷路）問題。" ,
"多点最短経路（スタンプラリー）問題。" ,
"木の問題。" ,
"連結性問題。"
);
if( num == num_temp++ ){
CERR( "特定の経路を進むと思い込んで考察漏れをする可能性があります。" );
CERR( "なるべく全ての経路を許した探索アルゴリズムを適用した方が無難です。" );
CERR( "- 特定の２点のみを考える場合、BFSやDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- 全ての２点の組み合わせを考える場合、" );
CERR( " - 一般のモノイド演算を考えておりO(V^3)が通りそうならば、FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - max演算を考えておりO(E(log_2 E + α(V)))が通りそうならば、UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "HeldKarpや、移動方法を分類するパラメータの全探策などを検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "深さ優先探索や動的木を検討しましょう。" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else if( num == num_temp++ ){
CERR( "- 0次の連結性はUnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- 高次の連結性は深さ優先探索" );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- マルチテストケースの場合は座標圧縮との併用" );
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "確率計算は" );
CERR( "- 余事象や包除原理（高速ゼータ変換）" );
CERR( "- 同様に確からしい事象の特定" );
CERR( "- ベイズの定理" );
CERR( "を検討しましょう。" );
CERR( "" );
CERR( "期待値計算は" );
CERR( "- 上記方法での確率計算" );
CERR( "- 対象を独立な和で表して線形性" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "ゲームの和に分解できる場合は最小単位で考察をし、グランディ数を実装しましょう。" );
CERR( "これ以上分解できないゲームには整礎構造を探し、順序数の小さい順に実験をしましょう。" );
} else if( num == num_temp++ ){
CERR( "複数の命題に対する" );
CERR( "- 区間処理は各種代数的データ構造" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- 充足可能性判定は頂点数を２倍してUnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
ASK_NUMBER(
"関数の計算問題。" ,
"降下／上昇列に関する問題。"
);
if( num == num_temp++ ){
CERR( "ゼータ変換を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "順序関係の定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"反復合成の計算問題。" ,
"反復合成による到達可能性問題。"
);
if( num == num_temp++ ){
CERR( "定義域の要素数N、テストケース数T、反復回数の上限Kとします。" );
CERR( "- O((N + T)log_2 K)が通りそうならばダブリング" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)が通りそうならばループ検出" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)すら通らなさそうならば関数の規則性を見付けるための実験" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "関数による遷移が定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_NUMBER(
"数や配列や文字列の構築。" ,
"経路の構築。" ,
"戦略の構築。" ,
"ソースコードの構築。"
);
if( num == num_temp++ ){
CERR( "p進法を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "可能な経路の定める無向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "ゲームの問題に帰着させましょう。" );
return LibrarySearch( num = num_game );
} else if( num == num_temp++ ){
CERR( "正解を出力をするソースコードを提出しましょう。" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "ライブラリー探索は以上です。終了します。" );
CERR( "" );
return -1;
}
#define DIJKSTRA_BODY( INITIALISE_PREV , SET_PREV ) \
static const U& unit = Unit(); \
assert( unit != m_found && unit < m_infty ); \
U weight[size_max]; \
\
for( int i = 0 ; i < m_size ; i++ ){ \
\
weight[i] = m_infty; \
\
} \
\
set<pair<U,int> > vertex{}; \
const int i_start = e_inv( t_start ); \
const int i_final = e_inv( t_final ); \
vertex.insert( pair<U,int>( weight[i_start] = unit , i_start ) ); \
INITIALISE_PREV; \
\
while( ! vertex.empty() ){ \
\
auto itr_vertex = vertex.begin(); \
const pair<U,int> v = *itr_vertex; \
const int& i = v.second; \
\
if( i == i_final ){ \
\
break; \
\
} \
\
const U& u = v.first; \
weight[i] = m_found; \
vertex.erase( itr_vertex ); \
const list<pair<T,U> > edge_i = E( e( i ) ); \
list<pair<U,int> > changed_vertex{}; \
\
for( auto itr_edge_i = edge_i.begin() , end_edge_i = edge_i.end() ; itr_edge_i != end_edge_i ; itr_edge_i++ ){ \
\
const int& j = e_inv( itr_edge_i->first ); \
U& weight_j = weight[j]; \
\
if( weight_j != m_found ){ \
\
const U& edge_ij = itr_edge_i->second; \
const U temp = Addition( u , edge_ij ); \
assert( edge_ij != m_found && temp != m_found && !( temp < edge_ij ) && temp < m_infty ); \
\
if( weight_j > temp ){ \
\
if( weight_j != m_infty ){ \
\
vertex.erase( pair<U,int>( weight_j , j ) ); \
\
} \
\
SET_PREV; \
changed_vertex.push_back( pair<U,int>( weight_j = temp , j ) ); \
\
} \
\
} \
\
} \
\
for( auto itr_changed = changed_vertex.begin() , end_changed = changed_vertex.end() ; itr_changed != end_changed ; itr_changed++ ){ \
\
vertex.insert( *itr_changed ); \
\
} \
\
} \
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
class DijkstraBody
{
private:
int m_size;
U m_infty;
U m_found;
int m_length;
map<T,int> m_memory;
vector<T> m_memory_inv;
public:
inline DijkstraBody( const int& size , const U& infty , const U& found );
U Solve( const T& t_start , const T& t_final );
U Solve( const T& t_start , const T& t_final , list<T>& path );
private:
virtual const U& Unit() const = 0;
virtual U Addition( const U& , const U& ) const = 0;
virtual T e( const int& i );
virtual int e_inv( const T& t );
virtual void Reset();
};
// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分が0以上である。
// (2) 2^{31}-1がEの値の各成分の第2成分size_max個以下の和で表せるいかなる数よりも大きい。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。
// O((size+|E|)log size)で単一始点最短経路探索。
template <list<pair<int,ll> > E(const int&) , int size_max>
class Dijkstra :
public DijkstraBody<int,ll,E,size_max>
{
public:
inline Dijkstra( const int& size );
private:
inline const ll& Unit() const;
inline ll Addition( const ll& , const ll& ) const;
inline int e( const int& i );
inline int e_inv( const int& t );
inline void Reset();
};
// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分がe_T()以上である。
// (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。
// (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。
// (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。
// O((size+|E|)(log size)^2)で単一始点最短経路探索。
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max>
class MemorisationDijkstra :
public DijkstraBody<T,U,E,size_max>
{
public:
inline MemorisationDijkstra( const int& size , const U& infty = 2147483647 , const U& found = -1 );
private:
inline const U& Unit() const;
inline U Addition( const U& , const U& ) const;
};
// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分がe_T()以上である。
// (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。
// (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。
// (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。
// (5) (enum_T,enum_T_inv)が互いに逆写像である。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。
// O((size+|E|)log size)で単一始点最短経路探索。
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)>
class EnumerationDijkstra :
public DijkstraBody<T,U,E,size_max>
{
public:
inline EnumerationDijkstra( const int& size , const U& infty = 2147483647 , const U& found = -1 );
private:
inline const U& Unit() const;
inline U Addition( const U& , const U& ) const;
inline T e( const int& i );
inline int e_inv( const T& t );
inline void Reset();
};
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max> inline DijkstraBody<T,U,E,size_max>::DijkstraBody( const int& size , const U& infty , const U& found ) : m_size( size ) , m_infty( infty ) , m_found( found ) , m_length() , m_memory() , m_memory_inv() {}
template <list<pair<int,ll> > E(const int&) , int size_max> inline Dijkstra<E,size_max>::Dijkstra( const int& size ) : DijkstraBody<int,ll,E,size_max>( size , 9223372036854775807 , -1 ) {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::MemorisationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody<T,U,E,size_max>( size , infty , found ) {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::EnumerationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody<T,U,E,size_max>( size , infty , found ) {}
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
U DijkstraBody<T,U,E,size_max>::Solve( const T& t_start , const T& t_final )
{
DIJKSTRA_BODY( , );
Reset();
return weight[i_final];
}
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
U DijkstraBody<T,U,E,size_max>::Solve( const T& t_start , const T& t_final , list<T>& path )
{
DIJKSTRA_BODY( T prev[size_max] = {} , prev[j] = i );
int i = i_final;
while( i != i_start ){
path.push_front( e( i ) );
i = prev[i];
}
path.push_front( t_start );
Reset();
return weight[i_final];
}
template <list<pair<int,ll> > E(const int&) , int size_max> inline const ll& Dijkstra<E,size_max>::Unit() const { static const ll unit = 0; return unit; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline const U& MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::Unit() const { return e_U(); }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline const U& EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Unit() const { return e_U(); }
template <list<pair<int,ll> > E(const int&) , int size_max> inline ll Dijkstra<E,size_max>::Addition( const ll& u0 , const ll& u1 ) const { return u0 + u1; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline U MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline U EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); }
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
T DijkstraBody<T,U,E,size_max>::e( const int& i )
{
assert( i < m_length );
return m_memory_inv[i];
}
template <list<pair<int,ll> > E(const int&) , int size_max> inline int Dijkstra<E,size_max>::e( const int& i ) { return i; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline T EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::e( const int& i ) { return enum_T( i ); }
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
int DijkstraBody<T,U,E,size_max>::e_inv( const T& t )
{
if( m_memory.count( t ) == 0 ){
assert( m_length < m_size );
m_memory_inv.push_back( t );
return m_memory[t] = m_length++;
}
return m_memory[t];
}
template <list<pair<int,ll> > E(const int&) , int size_max> inline int Dijkstra<E,size_max>::e_inv( const int& t ) { return t; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline int EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::e_inv( const T& t ) { return enum_T_inv( t ); }
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
void DijkstraBody<T,U,E,size_max>::Reset()
{
m_length = 0;
m_memory.clear();
m_memory_inv.clear();
return;
}
template <list<pair<int,ll> > E(const int&) , int size_max> inline void Dijkstra<E,size_max>::Reset() {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline void EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Reset() {}
inline DEXPR( int , bound_N , 100000 , 100 ); // 0が5個
list<pair<int,ll> > e[bound_N] = {};
inline list<pair<int,ll> > E( const int& i ) { return e[i]; }
inline DEXPR( int , bound_M , 100000 , 100 ); // 0が5個
tuple<int,int,ll,int> uvab[bound_M+1];
ll Solve( const int& N , const int& M , const int& b_max )
{
FOR( i , 0 , N ){
e[i].clear();
}
FOREQ( i , 0 , M ){
auto& [u,v,a,b] = uvab[i];
if( b_max <= b ){
e[u].push_back( { v , a } );
e[v].push_back( { u , a } );
}
}
Dijkstra<E,bound_N+1> d{ N };
return d.Solve( 0 , N - 1 );
}
int main()
{
UNTIE;
LIBRARY_SEARCH;
// DEXPR( int , bound_T , 100000 , 100 );
// CIN_ASSERT( T , 1 , bound_T );
// REPEAT( T ){
// }
// CEXPR( int , bound_N , 10 );
// CEXPR( int , bound_N , 1000000000 ); // 0が9個
// CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
CIN_ASSERT( N , 2 , bound_N );
// CEXPR( int , bound_M , 10 );
// CEXPR( int , bound_M , 1000000000 ); // 0が9個
// CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
CIN_ASSERT( M , 1 , bound_M );
CEXPR( ll , bound_X , 1000000000000000000 ); // 0が18個
CIN_ASSERT( X , 1 , bound_X );
CEXPR( ll , bound_a , 1000000000 ); // 0が9個
CEXPR( int , bound_b , 1000000000 ); // 0が9個
// CEXPR( ll , P , 998244353 );
// CEXPR( ll , P , 1000000007 );
// DEXPR( int , bound_Q , 100000 , 100 );
// CIN_ASSERT( Q , 1 , bound_Q );
// REPEAT( Q ){
// COUT( N );
// }
FOR( i , 0 , M ){
CIN_ASSERT( ui , 1 , N );
CIN_ASSERT( vi , 1 , N );
CIN_ASSERT( ai , 1 , bound_a );
CIN_ASSERT( bi , 1 , bound_b );
uvab[i] = { --ui , --vi , ai , bi };
}
uvab[M] = { 0 , N - 1 , 0 , 0 };
sort( uvab , uvab + M + 1 );
BS2( b_max , 0 , bound_b , Solve( N , M , b_max ) , X );
if( b_max == 0 ){
RETURN( -1 );
}
RETURN( b_max );
// ll answer = 0;
// RETURN( answer );
// QUIT;
}