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 - 旧総合研究7号館|AtCoder
A: 旧総合研究7号館 - 京都大学プログラミングコンテスト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! もちゃんと全桁出力できる(感動)
WUPC2012 A - 招待状|AtCoder
A: 招待状 - WUPC 2012 | AtCoderを解きました。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { vector<int> M{ 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int MM1, DD1, MM2, DD2; cin >> MM1 >> DD1 >> MM2 >> DD2; //受け取った日と開催月が同じ場合は開催日-受け取った日 if( MM1 == MM2 ) { cout << DD2 - DD1 << endl; return 0; } //メールを受け取った日の月の「日数」を算出(受け取った日を含むので +1 する) int res = ( M[ MM1 ] - DD1 ) + 1; //メールを受け取った日の月と開催日"以外"の月の「日数」を足す for( int i = MM1 + 1; i <= MM2 - 1; i++ ) { res += M[ i ]; } //開催月の開催日までの「日数」を足す(開催日は含まないので -1 する) cout << res + ( DD2 - 1 ) << endl; return 0; }
2016年 進捗大反省会
今年の振り返りをカテゴリ別に書き残そうと思います。
C++ について:
C++ を勉強し始めて、1年が経ちました。
春頃に range-based for *1 を覚えてから何故か劇的に C++力 が伸びました。
一気に vector, map, set などのコンテナを使える様になって出来る事の幅も広がりました。
STL や algorithm header にある関数も実際使う機会があると楽しくて、色々と覚えました。
それから、ラムダ式も覚え、苦手だった処理の関数化も出来る様になりました。
1年前と比較してコードもだいぶ綺麗になりました。(可読性的に)
C言語から勉強を始めた為、変数宣言をまとめて文頭でする癖があったのですが、きちんとスコープを考慮して書ける様にもなってきました。(実はこれが結構大変でした)
全体的には1年で基礎的な事を学習出来た気がします。
(C++というよりプログラミングの基礎?かも)
競プロについて:
競プロについては、進捗は少ししか出せなかったです。
現状はABCのC が全然埋められていないです。*2
3月末に ARC-A 埋めが終了して、ABC-C 埋めに移行しましたが、16問しか埋められていません。
原因としては、基本的なアルゴリズムの知識が無い事だったので、今年の後半は主にアルゴリズムの勉強をTLE本を使ってしていました。
とは云え、日々問題を解かないとC++力も低下しそうだし、適度な問題を解く事( C++を書く事 )と、アルゴリズムの勉強との両立が出来ず悩んだ時期もありました(本当に時間が足りない)。
最近は、自分に合ったアルゴリズムの勉強の仕方(?)も徐々に判って来て、DFSならDFSのタグが付いた問題を探して、勉強しつつ問題を解く、みたいな勉強方法に帰着できました。
それから、問題をしっかり「考察」する事を覚え始めました。
考察をするにあたって「計算量」を見積もるという事も必要になってきたので、最近の勉強内容は専ら「考察」と「計算量」を考えるのが中心です。
コード面での大きな変化と言えば、REPマクロを含む、競プロ テンプレートを使う様になった事です。*3
自分が使う様になって、それまで全然読めなかったプロのコードが読める様になったのは凄く良かったですね。
AC埋め的には、前半はARC-A埋め, 後半はAOJ, codeforces, yukicoder を良く解いていました。
AOJでは、文字列の問題を解いていました。(苦手だったので強化していた)
codeforcesは、解いた人が多い順にsortして解きました。
簡単な問題が多かったですが、コードは簡潔か、もっと便利なSTLで解けないか、プロのコードと比較してどうか、など C++ の勉強も含め1問1問丁寧に復習(解き直し)をしました。
結果、STLを多少使える様になったと思います。(そしてSTL大好きになった)
それから競プロの小技コード?みたいなのもこの頃覚え始めました。*4
全く同じコードでAC出来る問題も発見しました。(驚いた)
Problem - 379A - Codeforces / Problem - 460A - Codeforces
yukicoderは「★1 全然解ける問題ない...」って良く呟いていたのですけど、
ある時「あれ、解けるな(?)」みたいな時期が到来して一気に★1を解きました。
この頃、map と set を無駄に使いまくっていて禁止されました(懐かしい)
(配列外参照が起きない為凄く都合が良かった)
それからは vectorファースト な日々を送っています(多分)。
★2も色々な人を巻き込みながら数問解きました。(市バス *5 は楽しかった)
- AtCoder ABC & ARC
- 115
- AOJ
- 17 *
- codeforces
- 52
- yukicoder
- 80
- codechef
- 2
- Topcoder
- 3
AC数を書き出したら凄く少なかった(もっと解いている感あった)
codeforces, yukicoder あたりは解き直しをしていたので結果的に1問に凄く時間をかけていて、AC数には結び付かなかったかも知れません。
技術書:
2016年は C++ の本に加え、競プロの本(アルゴリズム系)も増えました。
本屋の技術書コーナーにも良く足を運びました。
・リーダブルコード
・C++ランゲージ クイックリファレンス
・STL標準講座
・TLE本(アルゴリズムとデータ構造)
・チーター本
・すごいHaskellたのしく学ぼう!
本は昨年結構揃えたので今年はそんなに激増はしませんでしたね。*6
エディタ:
MacなのでずっとXcodeを使っていたのですけど、bits/stdc++.h が使えない為、いつの間にか使わなくなりました。
Visual Studio Code も少し使ってみましたが、結局、Vim を使っています。
結果的にはWandBox + Vim で落ち着きました。
2017年 タスク:
意識低いので目標は決めず、タスクとして列挙します。
・アルゴリズムの基礎学習
・DPを覚えて「カップ麺生活」をACする
・TopCoderのSRM Div2-Easy 埋め
・ABC-C 埋め
・プロのコードを沢山読んで学ぶ
・きちんと考察をする
・計算量を見積もれる様になる
・日本語力向上
・会話のキャッチボール
・論理的文章が書けるようになる
★本を読んで体系的に学ぶ
★専門用語は都度クリアにする
来年末、これを元にまた進捗反省会します!
御礼:
今年も様々な方に大変大変お世話になりました。
競プロのプロの方々、強いC++erの方々にはいつもご助言を賜り、感謝しかありません。
来年も引き続き勉強していく所存ですので、叱咤(激励)宜しくお願いいたします!