No.7 プライムナンバーゲーム｜yukicoder｜メモ化再帰
No.7 プライムナンバーゲーム - yukicoder を 1ヶ月半 かけて解きました。
(何故 1ヶ月かかったのかは後述)
題意：
・はじめに先攻プレイヤーに自然数 N が与えられます。
・N以下の素数のどれかで減算し相手に渡す、を先攻・後攻で交互に繰り返し、
N が 0 か 1 になったら負けとなる。
・自分(先攻)が勝つ場合は"Win", 負ける場合は"Lose"を出力します。
・ゲームは互いに最善を尽くすものとする。
・2 ≤ N ≤ 10000
考察①：グラフを描く
まず、N = 7 の場合のプライムナンバーゲームの状態をグラフに描いて考えました。
先攻プレーヤーの持ち点 7 を根とし､子ノードの値となるのは N - ( N 以下の素数 ) です。
N == 0 か N == 1 を作った方が負けという観点から、 0 か 1 を受け取った方が勝ちと考えます。
ピンクの頂点が、先手勝ちとなる選択が存在する局面です。
この様に、ゲームの状態を頂点にして、遷移可能な状態を辺で結んだグラフを一般に ゲーム木 *1と呼びます。
ゲーム木上の子ノードの局面において、全ての値に対する勝敗のAND/ORを取ると､
・先手番時に先手勝ちが一つでもあれば先手勝ち(OR)
・後手番時に全て先手勝ちなら先手の勝ち(AND)
となる事が判ります。
この様に、2人で対戦し勝敗のみを気にするゲームのゲーム木をAND/OR木 *2 と呼びます｡
以上を踏まえ、例に挙げた N = 7 の場合の勝敗( Win/Lose )を考えると、
下記図の様に 先手勝ち( Win ) となる事が判ります。
ここまで判ったら、ゲームに関する考察は終わりで、これをそのまま実装する事となります。*3
考察②：素数の準備
与えられた N から N以下の素数 で引く為、N 以下の素数列挙が必要となります。
O( N^2 ) での列挙では TLE する為、O(N^2)より早くする必要があります。
素数列挙方法につきましては長くなる為、以下別記事に O( N√N ) ver と O( N log log N ) ver の2つを書きました。
考察③：計算量を減らす
考察②までを終えて提出した結果、N = 9299 のケースでTLE してしまいました。
何が無駄かを考える為に、ここでもう一度 グラフ を見ます｡
先手番時に同じ値を持つ部分木(黄色い頂点) が2回出現している事がグラフを見ると判ります。
この図は N = 7 の場合なので同じ値を持つ部分木の数が少ないですが、
N = 10000 の場合を考えると、もっと膨大な同じ値を持つ部分木が出現するのが予想できます。
そこで、一度訪れた頂点の勝敗結果を記憶し、既に訪問済みであれば記憶した結果を返すようにする事で計算量を減らします。
それを一般に メモ化 と呼ぶようです。*4
実装：
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int N; vector<int> P; vector<vector<int>> visit( 2, vector<int>( 10001, -1 ) );//<---初期化！！！ void prime( int N ) { for( int i = 2; i <= N; i++ ) { bool flag = true; for( int j = 2; j * j <= i; j++ ) { if( i % j == 0 ) { flag = false; break; } } if( flag ) { P.emplace_back( i ); } } reverse( P.begin(), P.end() ); } bool dfs( const int T, const int N ) { if( N == 0 || N == 1 ) { return T == 0 ? 1 : 0; } if( visit[ T ][ N ] >= 0 ) { return visit[ T ][ N ]; } if ( T == 0 ) { for( const auto &x : P ) { if( N - x >= 0 ) { if( dfs( 1, N - x ) ) { visit[ T ][ N ] = 1; return 1; } } } visit[ T ][ N ] = 0; return 0; } else { for( const auto &x : P ) { if( N - x >= 0 ) { if( !dfs( 0, N - x ) ) { visit[ T ][ N ] = 0; return 0; } } } visit[ T ][ N ] = 1; return 1; } } int main() { cin >> N; prime( N ); cout << ( dfs( 0, N ) ? "Win" : "Lose" ) << endl; return 0; }
まとめ：
考察 4 : 実装 6 くらいの割合で 1か月半 を消費した気がします。
考察では、グラフの基礎やゲーム木・AND/OR木の概念を学習、ゲームの状態を考察するのにグラフも沢山描きました。
実装では、素数列挙のアルゴリズム・エラトステネスの篩(ふるい)を学習したり、計算量を落とすメモ化も初めて書きました。
他にも実装面ではかなり細かい部分で消費しました。
(二次元配列の正しい要素数確保(今更)、メモリの概念(今更) とか...)
色んな学習要素が含まれている問題で、予想外に時間が掛かりましたが、
年内に AC 出来て良かったです(年内怪しいかな...って思ってた)。
※この記事を書いたのは昨年末です(公開するの忘れていた)
No.476 正しくない平均｜yukicoder
No.476 正しくない平均 - yukicoder を解きました。
std::accumulateの戻り値の型 にはまったのでメモ。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N; long long A; cin >> N >> A; vector<long long> vc( N ); for( auto &x : vc ) { cin >> x; } cout << ( (double)accumulate( vc.begin(), vc.end(), 0LL ) / N == A ? "YES" : "NO" ) << endl; return 0; }
accumulate *1で総和を正しく得られなかったのですが、
問題の制約を見ると、最大で を 10回 加算する事を想定しなくてはいけませんでした。
int型の数値表現可能な範囲は、 *2 なので、加算途中で桁あふれしてしまう事が判ります。
accumulate の計算途中および結果の型は、第３引数で指定します。
型を明示する為、サフィックス *3を初期値に付加します。
今回は long long にする為、第3引数を 0LLとしました。
(初期値の0とlong longのサフィックスであるLLを付加)
これでオーバーフローせず正しい戻り値を受け取れました！
std::accumulate の型
今すぐ使える C++ コーディングテクニック集 - torus711 のアレ
前項でも微妙に触れていますが、std::accumulate の戻り値の型は第三引数によって決まります。入力の範囲が long long 型だったとしても、初期値が int 型のリテラルである 0 であれば int 型として足し込んでいくのでオーバーフローしてしまいます。こういった場合は 0LL とサフィックスを付けて long long 型のリテラルにしてあげるとうまくいきます。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N; long long A; cin >> N >> A; vector<long long> vc( N ); for( auto &x : vc ) { cin >> x; } cout << ( accumulate( vc.begin(), vc.end(), 0.0 ) / N == A ? "YES" : "NO" ) << endl; return 0; }
最初のコードでは第3引数を0LLとしてlong long型を明示しましたが、
accumulateの戻り値の型は、初期値として渡した値の型になる事を踏まえると、
第3引数に最初から double の 0.0 を渡すと、オーバーフローもせず、更に総和をキャストする事が不要となる様でした(学び)。
double型の仮数部は 個の数(
)を表現出来る為、制約にも収まります。*4
ですが、浮動小数点数の演算に固有の誤差(丸め誤差、桁落ち、情報落ち)が常に生じる可能性がある *5 事を考慮すると、可能な限り整数での計算が好ましい様です。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N; long long A; cin >> N >> A; vector<long long> vc( N ); for( auto &x : vc ) { cin >> x; } cout << ( accumulate( vc.begin(), vc.end(), 0LL ) == N * A ? "YES" : "NO" ) << endl; return 0; }
なので結論としては、↑このコードが最適そう...(おわり)
ABC045 - B 3人でカードゲームイージー｜AtCoder
B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder を解きました。
題意：
・Aさん、Bさん、Cさんの3人でするカードゲーム。
・Aさんのターンからゲームは始まり、各自持っているカードに書かれている
a, b, c それぞれの人のターンになる。
・カードの順序は入れ替え不可。
・ターンが来たら先頭から1枚カードを捨てれる。
・自分のターンでカードを 1 枚も持っていなければ、その人が勝ち(ゲーム終了)。
( 細かい制約は問題文へ )
解法：
問題文通りに実装したら解けました。
Aさん、Bさん、Cさんの持つカード数にバラ付きがあるので、それぞれ別のカウンタを用意したぐらいです。
(もっと簡潔な解き方があるかも知れません...)
計算量 O( |Sa| + |Sb| + |Sc| )
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { string A, B, C; cin >> A >> B >> C; string next; next.push_back( A[ 0 ] ); int a{}, b{}, c{}; while( true ) { if( next == "a" ) { if( A.empty() ) { cout << "A" << endl; break; } next = *A.begin(); A.erase( A.begin() ); a++; } if( next == "b" ) { if( B.empty() ) { cout << "B" << endl; break; } next = *B.begin(); B.erase( B.begin() ); b++; } if( next == "c" ) { if( C.empty() ) { cout << "C" << endl; break; } next = *C.begin(); C.erase( C.begin() ); c++; } } return 0; }
KUPC2013 A - 旧総合研究７号館｜AtCoder
A: 旧総合研究７号館 - 京都大学プログラミングコンテスト2013 | AtCoderを解きました。
題意：
・N個の改名後の校舎名と改名年度と、資料が作成された年度Qが与えられるので、
Q年度の校舎の名前を出力する。
・平成元年度の校舎名は "kogakubu10gokan"
・1 ≤ N < 50
・1 ≤ Q ≤ 50
・2 ≤ year 1 < year 2 < … < year n ≤ 50
( その他細かい制約は問題文参照で )
解法：
年度は高々50年までしかないので、50 + 1 の配列を 平成元年度の校舎名 "kogakubu10gokan" で埋めて、その後改名された年度の校舎名で配列を上書きしてQ年度を出力する。
計算量はO( N )
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define REP2(i,x,n) for(int i=x; i<(n); i++) struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N, Q; cin >> N >> Q; vector<int> year( 50 + 1 ); vector<string> name( N ); REP( i, N ) { cin >> year[ i ] >> name[ i ]; } vector<string> res( 50 + 1 ); string tmp = "kogakubu10gokan"; REP( i, 50 + 1 ) { REP( j, N ) { if( i == year[ j ] ) { tmp = name[ j ]; } res[ i ] = tmp; } } cout << res[ Q ] << endl; return 0; }
応用・発展：
例えば、Q の制約が 1 ≤ Q ≤ 10^9 だったらどう解く？と云う発展課題！
上記コードでは別配列を用意して 50 + 1 年分をわざわざ全て埋めたけれど、実はその必要は無く、指定されたQ年度の校舎名をそのまま返してあげれば良いだけ、という解法に至りました。
(なので上記コードは無駄な事をしている事が判った...)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define REP2(i,x,n) for(int i=x; i<(n); i++) struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N, Q; cin >> N >> Q; vector<int> year( N ); vector<string> name( N ); REP( i, N ) { cin >> year[ i ] >> name[ i ]; } year.emplace_back( 51 ); string res = "kogakubu10gokan"; REP( i, N + 1 ) { if( year[ i ] <= Q && year[ i + 1 ] > Q ) { res = name[ i ]; } if( Q > year[ N - 1 ] ) { res = name[ N - 1 ]; } } cout << res << endl; return 0; }
loop 1個減ったのですが、こちらも計算量はO( N )。
2つのコードを比較する為に書き示すとしたらO( year* N )。
計算量(ステップ数)とO記法は別の概念というのをなんとなく覚えました。
※記事中の計算量にご指摘がある場合はご連絡ください...
C++で多倍長整数！
C++で多倍長整数が使える事をコンテスト中に知ったのでメモ。
でも標準ライブラリではなく、boost (オープンソースライブラリ) を使う様です。
参考）Chapter 1. Boost.Multiprecision - 1.53.0
参考）多倍長整数 - boostjp
cpp_int はメモリが許す限り無限の桁数を扱える型。
#include <bits/stdc++.h> #include <boost/multiprecision/cpp_int.hpp> // <-- add!!! using namespace std; using namespace boost::multiprecision; // <-- add!!! cpp_int sum( cpp_int N ) { if( N == 0 ) return 1; else return N * sum( N - 1 ); } int main() { int N; cin >> N; cout << sum( N ) << endl; }
実行コード：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
↑1000! もちゃんと全桁出力できる(感動)
