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の方々にはいつもご助言を賜り、感謝しかありません。
来年も引き続き勉強していく所存ですので、叱咤(激励)宜しくお願いいたします!
SRM 602 Div2 Level-1 250:TypoCoderDiv2
SRM 602 div2 250:TypoCoderDiv2 を解きました。
題意:
TypoCoderには2種類の Rating がある。
Brown ➡︎ 1200以上
Ciel ➡︎ 1200以下
ただし新しい参加者は Rating 500 スタート。
N回分のコンテスト参加後の Rating が与えられるので何回色が変わったかを出力する。
解法:
初期値 500 からの変動もカウントに入る為、初期値 500 を 配列の先頭( rating[ 0 ] ) に加えてから1200以上と以下の変動で場合分けをする。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; struct TypoCoderDiv2 { vector<int> rating; int count( vector<int> rating ) { int cnt{}; rating.insert( begin( rating ), 500 ); REP( i, (int)rating.size() - 1 ) { if( rating[ i ] >= 1200 && rating[ i + 1 ] < 1200 ) cnt++; if( rating[ i ] < 1200 && rating[ i + 1 ] >= 1200 ) cnt++; } return cnt; } };
C++で素数列挙!エラトステネスの篩 編
C++で素数列挙!O( N√N )編 を書きましたが、
今度はもっと高速な エラトステネスの篩(ふるい)編 *1 を書いたのでコードを残します。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; #include <vector> std::vector<int> Eratosthenes( const int N ) { std::vector<bool> is_prime( N + 1 ); for( int i = 0; i <= N; i++ ) { is_prime[ i ] = true; } std::vector<int> P; for( int i = 2; i <= N; i++ ) { if( is_prime[ i ] ) { for( int j = 2 * i; j <= N; j += i ) { is_prime[ j ] = false; } P.emplace_back( i ); } } return P; } int main() { int N; cin >> N; for( const auto &x: Eratosthenes( N ) ) { cout << x << " "; } return 0; }
ベースは 蟻本 P112 の「素数の個数」を求めるというコードです。
上記コードは、素数を pick upして vector に格納すると云うものです。
計算量はO( N log log N )だそうです。(蟻本 P112より)
C++で素数列挙!O( N √N )編
以前、C++で素数判定!を書いたのですが、
今回は C++で素数列挙!O( N √N ) のコードを書いたのでメモとして残します。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int N; vector<int> P; void prime( const 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 ); } } } int main() { cin >> N; prime( N ); for( const auto &x: P ) { cout << x << " "; } return 0; }
N - 1個の自然数の中から素数だけ Pick upして vector に格納後、main関数内で出力しています。*1
計算量は、O( N )個の数に対して O( √N ) 時間かけて探索するので O( N √N ) です。
Sum of Integers|AOJ|深さ優先探索(DFS)
深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、
整数の和 | Aizu Online Judge を解きました。
<題意>
0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; // i --> 0 - 9までの数字 // sum --> 合計値 // cnt --> 和がSとなる組み合わせの数 // total --> 足す数(N個まで足す) int N, S, cnt; void dfs( int i, int sum, int total ) { //N回を満たしている 且つ 合計がSに達したものをcountする if( total == N && sum == S ) { cnt++; return; } //0-9まで探索したら or 足す回数がN回に達したら 終わり if( i == 10 || total == N ) return; //合計に i を足す場合 -> 足す回数を +1 する dfs( i + 1, sum + i, total + 1 ); //合計に i を足さない場合 dfs( i + 1, sum, total ); } int main() { while( cin >> N >> S ) { if( N == 0 && S == 0 ) break; //合計値の初期化 cnt = 0; //dfs( 数字の0から, 合計値0から, 足す数字0から) dfs( 0, 0, 0 ); cout << cnt << endl; } return 0; }
DFSを本で勉強したのですが、さっぱり実装出来る気がしなくて、
処理をいくつかに分割して書いてやっとまとまりました。
手順としては下記の工程を経ています。
1)足し算部分の再帰を書く
2)合計を取る部分を書く
3)合計がSとなったものをcountする部分を書く
4)合計に足す場合と、足さない場合を書く
5)N個だけ選んで和を取る部分を書く
個々の処理がどうなっているか良く解ったので理解が進みました。
この問題を解く際、グローバル変数に count と云う変数名を使ったら gccに怒られました。
std::count と区別がつかないよって事らしいです。
それから、returnで何も返さない関数はvoidで宣言する様で、そこも新たに覚えました。
(何も返さない関数を初めて書きました...!)
次はstack編も覚えなくてはみたいな感じです。