結果
| 問題 | No.2354 Poor Sight in Winter |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-06-18 18:06:35 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 158 ms / 2,000 ms |
| コード長 | 40,538 bytes |
| コンパイル時間 | 4,820 ms |
| コンパイル使用メモリ | 257,104 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-26 07:19:41 |
| 合計ジャッジ時間 | 6,156 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 3 ms
5,376 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 3 ms
5,376 KB |
| testcase_12 | AC | 87 ms
5,376 KB |
| testcase_13 | AC | 82 ms
5,376 KB |
| testcase_14 | AC | 158 ms
5,376 KB |
| testcase_15 | AC | 26 ms
5,376 KB |
| testcase_16 | AC | 142 ms
5,376 KB |
| testcase_17 | AC | 118 ms
5,376 KB |
| testcase_18 | AC | 20 ms
5,376 KB |
| testcase_19 | AC | 46 ms
5,376 KB |
| testcase_20 | AC | 7 ms
5,376 KB |
| testcase_21 | AC | 4 ms
5,376 KB |
| testcase_22 | AC | 25 ms
5,376 KB |
| testcase_23 | AC | 9 ms
5,376 KB |
| testcase_24 | AC | 53 ms
5,376 KB |
| testcase_25 | AC | 11 ms
5,376 KB |
| testcase_26 | AC | 10 ms
5,376 KB |
| testcase_27 | AC | 3 ms
5,376 KB |
| testcase_28 | AC | 4 ms
5,376 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( ANSWER ) cerr << ANSWER << endl;
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#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( ANSWER )
#define LIBRARY_SEARCH
#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 ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#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 FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT
inline void AlertAbort( int n ) { cerr << "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" << endl; }
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 : ( a % p ) + 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 , TARGET , INEQUALITY , 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 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 << "-" << TARGET << ( EXPRESSION > TARGET ? ">0" : EXPRESSION < TARGET ? "<0" : "0" ) ); \
} else { \
CERR( 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&
int QuitLibrarySearch( const int& problems_size ){
cerr << "返答は" << problems_size - 1 << "以下の非負整数にしてください。";
CERR( "終了します。" );
CERR( "" );
return -1;
}
int LibrarySearch( int num = -1 )
{
vector<string> problems =
{
"数に関する問題。" ,
"配列に関する問題。" ,
"文字列に関する問題。" ,
"順列に関する問題。" ,
"矩形領域に関する問題。" ,
"グラフに関する問題。" ,
"部分和問題。" ,
"期待値に関する問題。" ,
"ゲームに関する問題。" ,
"論理に関する問題。" ,
"順序に関する問題。" ,
"関数適用に関する問題。" ,
"構築問題。" ,
"関数適用に関する問題。" ,
"構築問題。"
};
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CEXPR( int , num_game , 8 );
int problems_size = problems.size();
string reply{};
if( num == -1 ){
CERR( "ライブラリーを探索しますか？[y/n]" );
CIN( string , reply );
if( reply == "n" ){
CERR( "ライブラリーを探索せずに続行します。" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/nのいずれかで答えてください。" );
CERR( "終了します。" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "ライブラリーを探索します。" );
CERR( "問題の種類を番号で指定してください；" );
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
cin >> num;
}
CERR( "" );
int num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "入力は１つの数か、１つの数と法を表す数ですか？[y/n/c]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "次に出力の定義と等価な式を考察しましょう。" );
CERR( "- 単調ならば、冪乗や階乗" );
CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" );
CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
CERR( " オイラー関数、約数の個数など" );
CERR( "を検討しましょう。" );
} else if( reply == "n" ){
CERR( "このケースのライブラリー探索は未実装です。" );
} else if( reply == "c" ){
CERR( "終了します。" );
CERR( "" );
return -1;
} else {
CERR( "y/n/cのいずれかで答えてください。" );
CERR( "終了します。" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "マルチテストケースの場合は以下の前計算を検討しましょう；" );
CERR( "素数列挙、約数列挙、サブゴールとなる関係式を満たす解列挙。" );
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"区間処理問題。" ,
"最大化問題。" ,
"最長部分列問題。" ,
"数え上げ問題。" ,
"部分和問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "クエリ処理を整理し、代数構造を抽出しましょう。" );
CERR( "- 可換群構造+しか使わない場合は可換群BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template")
CERR( "- 可換羃等モノイド構造∨しか使わない場合は可換羃等モノイドBIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "- モノイド構造*しか使わない場合はモノイドBITかモノイド平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- 集合へのマグマ作用(*,\\cdot)しか使わない場合は双対平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "- モノイドへのマグマ作用(+,\\cdot)しか使わない場合は遅延評価平方分割" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "- 非結合演算が使われている時は写像のコード化" );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "- (+,max)が使われている時は場合分けで表し、配列の各成分の場合分けが切り替わる位置（イベント）と" );
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)で処理できます。" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
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)が通りそうで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++ ){
CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ配列を用いて、" );
CERR( " それらの部分列の末尾である項を記録すること" );
CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ連想配列を用いて、" );
CERR( " それら部分列の長さの最大値を記録すること" );
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "gcdやmaxなどの羃等演算に関する等式を指定した数え上げは不等式の方が" );
CERR( "扱いやすいのでゼータ変換／メビウス変換を検討しましょう。" );
} else {
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定しましょう；" );
problems =
{
"部分列マッチング問題。" ,
"回文探索問題。" ,
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "基本的には丁寧にループを回して解きましょう。" );
CERR( "- 比較対象が少ない場合、前または後ろから順に探索（貪欲法／動的計画法）" );
CERR( "- ワイルドカードを含む場合、" );
CERR( " - 前または後ろから順に場合分けをしてO(N)で処理できるか" );
CERR( " - 可能な代入方法を絞り込んでO(N)種類に落せるか" );
CERR( "- 比較回数が多い場合、ローリングハッシュ" );
CERR( "- マッチングする文字列の最長化をする場合、Zアルゴリズム" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "を検討しましょう。" );
} else {
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++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"探索問題。" ,
"絶対値の最小／最大化問題。" ,
"その他の最小／最大化問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else 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++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"２点最短径路（迷路）問題。" ,
"多点最短経路（スタンプラリー）問題。" ,
"木の問題。" ,
"連結性問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else 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 {
CERR( "- 0次の連結性はUnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- 高次の連結性は深さ優先探索" );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- マルチテストケースの場合は座標圧縮との併用" );
CERR( "を検討しましょう。" );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"部分和の最大化問題。" ,
"部分和の数え上げ問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "項数N、重みの総和の上限W（多変数も可）、価値（和を取る値）の上限Vとします。" );
CERR( "- B=∞ならば、通常のナップサック問題と同様の動的計画法" );
CERR( "- B<∞でO(2^N)が通りそうならば愚直に全探策" );
CERR( "- B<∞でO(2^{N/2} N)が通りそうならば半分全列挙" );
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" );
} else {
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\\Polynomial" );
}
CERR( "を検討しましょう。" );
} else if( num == num_temp++ ){
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++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"半順序集合上の関数の計算問題。" ,
"半順序集合上の降下／上昇列に関する問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "ゼータ変換を検討しましょう。" );
} else if( num == num_temp++ ){
CERR( "順序関係の定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"反復合成の計算問題。" ,
"反復合成による到達可能性問題。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else 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( "を検討しましょう。" );
} else {
CERR( "関数による遷移が定める有向グラフの問題に帰着させましょう。" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "より詳細な問題の種類を番号で指定してください；" );
problems =
{
"数や配列や文字列の構築。" ,
"経路の構築。" ,
"戦略の構築。"
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else 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 );
}
}
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個以下の和で表せるいかなる数よりも大きい。
// が成り立つ場合にのみサポート。
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&)に関して順序モノイドである。
// が成り立つ場合にのみサポート。
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)が互いに逆写像である。
// が成り立つ場合にのみサポート。
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 , 2147483647 , -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 CEXPR( int , bound_N , 500 );
pair<int,int> v[bound_N + 2];
int N , P;
list<pair<int,ll> > E( const int& t )
{
pair<int,int>& vt = v[t];
list<pair<int,ll> > answer{};
FOR( i , 0 , N ){
pair<int,int>& vi = v[i];
int x = Absolute( vt.first - vi.first );
int y = Absolute( vt.second - vi.second );
if( x < y ){
swap( x , y );
}
answer.push_back( { i , ( x - 1 ) / P } );
}
return answer;
}
int k( const int& answer )
{
P = answer;
Dijkstra<E,bound_N+2> d{ N };
return d.Solve( 0 , 1 );
}
int main()
{
UNTIE;
LIBRARY_SEARCH;
// CEXPR( int , bound_T , 100000 );
// CIN_ASSERT( T , 1 , bound_T );
// CEXPR( int , bound_N , 100000 ); // 0が5個
// CEXPR( ll , bound_N , 1000000000 ); // 0が9個
// CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
SET_ASSERT( N , 1 , bound_N );
CEXPR( int , bound , 100000 ); // 0が5個
CIN_ASSERT( K , 0 , bound );
N += 2;
FOR( i , 0 , N ){
CIN_ASSERT( x , 0 , bound );
CIN_ASSERT( y , 0 , bound );
v[i] = { x + y , x - y };
}
BS4( answer , 1 , bound , k( answer ) , K );
// REPEAT( T ){
// COUT( N );
// }
RETURN( answer );
}