English Sentence｜AOJ｜ Volume0-0029
単語の出現頻度 | Aizu Online Judge を解きました。
題意：
・英文が与えられるので､｢出現頻度が最も高い単語｣と､｢文字数が最も多い単語｣を出力する。
・与えられる英文は半角英文字で、半角スペースを含む。
・文章の文字数は1000文字以下
・一つの単語の文字数は32文字以下
・｢出現頻度が最も高い単語｣｢最長の文字数を持つ単語｣はそれぞれ文中に一つだけしか存在しない事が保証されている。
考察：
＜出現頻度が最も高い単語＞
出現頻度が最も高い = 重複数が最も多い と言えるので、各単語の重複数のMAX値をとる。
➡︎ 指定された値と等値な要素の数を数える事ができる std::count *1 を使う。
＜文字数が最も多い単語＞
文字数が最も多い = 文字列長(要素数)が最も長い(多い) と言えるので、各単語の文字列長のMAX値をとる。
➡︎ 文字列長は string::size *2 で取得する。
計算量：
入力の受け取りに 時間、vector への要素構築に償却定数時間、MAX値を探索するloopに
時間, std::count で 1つの単語について重複を数えるのに
回なので、1回の loop で
時間となり、全体では
時間。
コード：
復習：
プロの提出を見ていたら map解 があったので、 mapでも解いてみました。
値の持ち方を map< 単語, 重複数 > として、重複を始めにカウントしてしまうという解き方。
計算量は、全体で なので、こちらの方が良さそう。
追記：
( int ) とキャストしている箇所を size_t にしたら？とアドバイス頂いたので、修正してみました。
無駄なキャストがなくなりました！
ABC062 A - Grouping｜AtCoder
A: Grouping - AtCoder Beginner Contest 062 | AtCoder を解きました。
A 問題ですが、学びがあったのでメモ。
題意：
・1 から 12 までの整数が下記のようにグループ分けされています。
- 1, 3, 5, 7, 8, 10, 12
- 4, 6, 9, 11
- 2
・整数 が与えられるので、
が同一のグループに属している場合 Yes を、そうでない場合は No を出力する。
コード：
#include <bits/stdc++.h> using namespace std; int main() { int x, y; cin >> x >> y; int cnt1{}, cnt2{}; for( auto &i : vector<int>{ 1, 3, 5, 7, 8, 10, 12 } ) { if( i == x || i == y ) cnt1++; } for( auto &i : vector<int>{ 4, 6, 9, 11 } ) { if( i == x || i == y ) cnt2++; } cout << ( cnt1 == 2 || cnt2 == 2 ? "Yes" : "No" ) << endl; }
実装を少し考えてみたけれど、自分ではこれ以上簡潔に書けなくて、
AC した後、他の方の提出を見たらグループ番号を持たせるという工夫があり、学びでした。
- 1, 3, 5, 7, 8, 10, 12 ➡︎ グループ 0
- 4, 6, 9, 11 ➡︎ グループ 1
- 2 ➡︎ グループ 2
↑上記のようにグループ番号( 0, 1, 2 )を付加します。(番号は何でも良い)
↓そして､ 1 から 12 までの整数を昇順に並び替え、グループ番号で配列に持ちます。
vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }
この時、制約より に 0 が与えられる事はないので、適当に -1 とかで vc[ 0 ] を埋めておく。
これにより、vc[ x ] と vc[ y ] がどのグループか で知る事ができ、一致判定が可能となる訳です。
#include <bits/stdc++.h> using namespace std; int main() { vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }; int x, y; cin >> x >> y; cout << ( vc[ x ] == vc[ y ] ? "Yes" : "No" ) << endl; }
↑コードが凄く簡潔になりました！
std::equal_to｜C++｜STL
std::equal_to の覚書
C++日本語リファレンスによると下記の通り↓
メンバ変数を持たず、状態を保持しないとのこと。
equal_toクラスは、等値比較を行う関数オブジェクトである。*1
equal_to< 型 >()( left, right ); で、指定した型による left == right の比較が行われ、
bool 値( 0 / 1 )が返ってくる様です。
#include <bits/stdc++.h> using namespace std; int main() { //int for( int i = 0; i < 3; i++ ) { cout << i << ":" << equal_to<int>()( i, 2 ) << endl; } cout << endl; //string vector<string> vc{ "NO","YES","NO" }; for( int i = 0; i < 3; i++ ) { cout << i << ":" << equal_to<string>()( vc[ i ], "YES" ) << endl; } return 0; }
#include <bits/stdc++.h> using namespace std; int main() { //int auto f = [ = ]( int x ){ return x == 2; }; for( int i = 0; i < 5; i++ ) { cout << i << ":" << f( i ) << endl; } cout << endl; //string vector<string> vc{ "NO","YES","NO" }; auto f2 = [ = ]( string x ){ return x == "YES"; }; for( int i = 0; i < 3; i++ ) { cout << i << ":" << f2( vc[ i ] ) << endl; } return 0; }
ラムダでも同じ感じで書けました◎
(単にラムダを書く練習です...)
std::equal_to の使い所はまだ思い浮かばないのですけど、
使うとしたら、std::all_of *2 との合わせ技で使う例を見たので、
vector 等に入った要素の比較判定とかで使えそうではあります。
std::function｜C++｜STL
std::function(C++11) の覚書
C++日本語リファレンスによると下記の通り↓
functionクラステンプレートは、パラメータの型リストArgTypes...、戻り値の型Rに合致する、あらゆる関数ポインタ、関数オブジェクト、メンバ関数ポインタ、メンバ変数ポインタを保持できるクラスである。*1
...難しいので理解出来る範囲でまとめると、
std::function< 戻り値の型(引数の型) > で宣言すると、関数オブジェクトを代入出来るっぽい。
#include <bits/stdc++.h> using namespace std; int sum( int n ) { return n + n; } int main() { //関数 sum を変数 f に保存 function<int(int)> f = sum; //保持している sum 関数を呼び出す cout << f( 10 ) << endl; //result 20 //ラムダ関数を保存 function<string(string)> s = [&]( string s ){ return s.substr( 2, 3 ); }; cout << s( "wwcwwww" ) << endl; //result cww return 0; }
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 出来て良かったです(年内怪しいかな...って思ってた)。
※この記事を書いたのは昨年末です(公開するの忘れていた)
