ホームに戻る
TopCoder の傾向と対策(C++編:基礎)
0、はじめに
TopCoder では C++ を使っておけば間違いないと思います。
いちばん使われている言語であるし、
そもそも java や C# よりも実行速度が高速です。
STL といったライブラリが使用できますし、
参考にするコードがいちばん多いのも C++ だと思います。
まず、ヘッダはたくさんインクルードしておいたほうがいいので、
テンプレを書いておきます。
コードの先頭は以下のように書きました。
実行時間には影響しないので使わないなら消すとかしなくてOK。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
1、時間測定
clock_t start, end;
start = clock();
// 時間を計る処理
end = clock();
printf("%.2f秒かかりました\n", ((double)(end-start)/CLOCKS_PER_SEC));
2、数字の最大値に対する対策
int 型は32ビット値で最大値は INT_MAX で定義されています。
C++ は unsigned が使えます。その場合の最大値は UINT_MAX です。
64ビット値は long long で扱えます。最大値は LLONG_MAX です。
java を使っていると long が 64 ビット値と考えてしまいがちですが、
C++ では long は32ビット値なので間違えないように注意しましょう。
3、総当り
与えられた配列から2つの数を選んだ和が7の倍数であるものはいくつか、
という問題があるときに。
int count = 0;
int array[] = {1,4,3,6,5,3,2,1};
int len = sizeof(array)/sizeof(array[0]);
for(int i = 0; i < len - 1; i++){
for(int j = i + 1; j < len; j++){
if((array[i] + array[j]) % 7 == 0){
count++;
}
}
}
と書くことができる。
深さ優先探索は、
与えられた配列内のいくつかを足して解が偶数になる場合の最大値を返せ、
という問題があるときに。
int ans = 0;
int array[] = {1,4,3,6,5,3,2,1};
int len = sizeof(array)/sizeof(array[0]);
void dfs(int index, int sum){
if(index == len){
if(sum % 2 == 0){
ans = max(ans, sum);
}
return;
}
dfs(index + 1, sum);
dfs(index + 1, sum + array[index]);
}
幅優先探索は、
配列の中から5つの数字を選んだ和が偶数になる場合の最大値を返せ、
という問題があるときに。
int ans = 0;
int array[] = {1,4,3,6,5,3,2,1};
int len = sizeof(array)/sizeof(array[0]);
queue<int> q1, q2;
for(int i = 0; i < len; i++){
q1.push(1);
q2.push(1 << i);
}
while(!q1.empty()){
int index = q1.front();
int mask = q2.front();
q1.pop();
q2.pop();
if(index == 5){
int res = 0;
for(int i = 0; i < len; i++){
if(((mask >> i) & 1) == 1){
res += array[i];
}
}
ans = max(ans, res);
continue;
}
for(int i = 0; i < len; i++){
if(((mask >> i) & 1) != 1){
q1.push(index + 1);
q2.push(mask | (1 << i));
}
}
}
全探索するのであれば深さ優先でも幅優先でも違いは無い。
ただし、最短を求めるような問題では幅優先のほうが早い。
深さ優先探索で最短を求めるためには全探索が必要である。
逆に最初から深い探索が必要な場合には幅優先探索は向かない。
場合によって使い分けが必要になる。
4、データの記録と操作1 配列
size() でサイズが取得できないので注意する。
int a[10];
int len = sizeof(a)/sizeof(a[0]);
初期化
int a[3] = {1, 3, 5}; // 初期値を入れる場合
int d[10][10][10]; // 多次元配列の場合
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
fill((int*)d, (int*)(d + lengthof(d)), -1); // すべての要素を -1 で初期化
memset(d, 0, sizeof(d)); // memset は 0 か -1 でしか初期化できないので注意
昇順ソート
sort(d, d + len);
降順ソート
sort(d, d + len, greater<int>());
最大値、最小値
*max_element(d, d + len)、*min_element(d, d + len)
最大値、最小値のインデックスを得る。(複数ある場合は最初のもの)
引数の順番を逆にすると結果がマイナスになるので注意。
distance(d, max_element(d, d + len))
distance(d, min_element(d, d + len))
vector への変換
vector<int> v(d, d + len);
関数に引数として渡した場合は参照渡し扱いになります。(重要)
5、データの記録と操作2 vector
5つの要素を確保する。
vector<int> v(5);
5つの要素を確保しすべて0で初期化する。
vector<int> v(5, 0);
アクセス
v[3] のようにアクセスできる。
要素数を得る。
v.size();
特定の要素を数える。
count(v.begin(), v.end(), 0);
要素の追加
v.push_back(3); // 3 を追加
要素の挿入
vector<int>::iterator itr = v.begin();
v.insert(itr + 3, 1 ,4); // インデックス 3 に 1 つの 4 を挿入
要素の結合
v.insert(v.end(), v2.begin(), v2.end()); // v の末尾に v2 を結合
要素の削除
v.erase(v.begin() + 1); // インデックス 1 の要素を削除
要素の削除の注意:
インデックス 0 と 1 の要素を削除したいとき
v.erase(v.begin() + 0);
v.erase(v.begin() + 1);
とすると最初から見た場合、インデックス 0 と 2 の要素が消える。
これは見た目は合っていそうで意図しない動作になるので注意する。
よって、
v.erase(v.begin() + 1);
v.erase(v.begin() + 0);
とするか
v.erase(v.begin() + 0);
v.erase(v.begin() + 0);
とすべきである。
また、要素が無いところを erase するとエラーになるので注意する。
昇順ソート
sort(v.begin(), v.end());
降順ソート
sort(v.begin(), v.end(), greater<int>());
最大値、最小値
*max_element(v.begin(), v.end())、*min_element(v.begin(), v.end())
最大値、最小値のインデックスを得る。(複数ある場合は最初のもの)
引数の順番を逆にすると結果がマイナスになるので注意。
distance(v.begin(), max_element(v.begin(), v.end()))
distance(v.begin(), min_element(v.begin(), v.end()))
2次元配列
vector<vector<int> > d2(N, vector<int>(M, 0)); // すべての要素を 0 で初期化
3次元配列
vector<vector<vector<int> > > d3(X, vector<int>(Y, vector<int>(Z, 0)));
2次元配列のソート
2行3列の次のような2次元配列があった場合
2, 5, 6
2, 3, 7
まず 2 と 2 を比べる、次に 5 と 3 を比べる 5 と 3 を評価して次のように入れ替わる
2, 3, 7
2, 5, 6
コピー
vector<int> v2(v1); // v1 を v2 にコピー
関数に引数として渡した場合はコピーを作ります。(重要)
6、データの記録と操作3 set
重複を許さないデータ構造。
また、データ挿入時に自動的に昇順ソートされます。
set<int> s;
追加
s.insert(3);
要素数を得る。
s.size();
要素があるかどうかを調べる。
s.count(4); // あれば 1 無ければ 0 を返す 性質上 2 以上はありえない
探索
set<int>::iterator itr = s.begin();
while(itr != s.end()){
cout << *itr << endl;
itr++;
}
逆順探索
set<int>::reverse_iterator itr = si.rbegin();
while(itr != si.rend()){
cout << *itr << endl;
itr++;
}
7、データの記録と操作4 multiset
set と違って重複を許す。
ms.count(4);
の挙動が異なる。
8、データの記録と操作5 map
キーと値のセット。
キーの重複を許さない。
挿入時にキーでの昇順ソートを自動で行う。
値でのソートはできない。
重複を許す場合は multimap を使う。
map<string, int> m;
値の追加。
m.insert(make_pair("abc", 100)); // 重複すると上書きできない。
値の追加。
map<string, int> m; // 初期値は 0
m["a"]++; // いきなりこのように書いても良い
m["b"]++;
アクセス
m["abc"] = 100; // この場合は上書きする。(重要)
キーがあるかどうかを調べる。
m.count("abc"); // 値ではない キーを調べる
探索
map<int, string>::iterator itr = m.begin();
while(itr != m.end()){
cout << (*itr).first << ":" << (*itr).second << endl;
itr++;
}
キーを使って値を扱うのは得意だが、値を使ってキーを扱うのは苦手。
値を使ってキーを扱うのであれば vector<pair> を使うと良いかもしれない。
9、データの記録と操作6 vector<pair>
初期化
vector<pair<int, int> > v(50, pair<int, int>(0, 0)); // すべての要素を (0, 0) で初期化
1番目の値でのソート(1番目の値が同じであれば、2番目の値でソートされる)
sort(v.begin(), v.end());
2番目の値のみでのソート
struct sort_pred{
bool operator() (const pair<int, int>& left, const pair<int, int>& right){
return left.second < right.second;
}
};
vector<pair<int, int> > v;
v.push_back(make_pair(10, 2));
v.push_back(make_pair(30, 1));
v.push_back(make_pair(20, 3));
sort(v.begin(), v.end(), sort_pred());
10、構造体
構造体で独自のデータ構造を作るとソートなどで楽できる。
struct Data{
int a;
int b;
int c;
Data(int a, int b, int c):a(a), b(b), c(c){};
bool operator <(const Data &p) const {
return ((c > p.c)
|| (c == p.c && b > p.b)
|| (b == p.b && a > p.a));
}
};
Data md(int a, int b, int c){
return (Data(a, b, c));
}
例えば、上の構造体は a b c の値を持ち、ソートすると、
c が大きい順、同じなら b が大きい順 同じなら a が大きい順でソートする。
vector<Data> v;
v.push_back(md(3, 2, 2));
v.push_back(md(3, 1, 3));
v.push_back(md(2, 3, 2));
sort(v.begin(), v.end());
11、グラフ
vector<vector<int> > vvi(4);
vvi[0].push_back(1);
vvi[0].push_back(3);
vvi[1].push_back(0);
vvi[1].push_back(2);
vvi[2].push_back(1);
vvi[2].push_back(3);
vvi[3].push_back(0);
vvi[3].push_back(2);
グラフを使ったサンプル(ダイクストラ法)
#define N 10
int d[N] = {4, 1, 3, 6, 3, 5, 2, 4, 1, 7};
int flag[N];
int ans[N];
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
fill((int*)flag, (int*)(flag + lengthof(d)), 0);
fill((int*)ans, (int*)(ans + lengthof(d)), INT_MAX);
vector<vector<int> > vvi(N);
// グラフを作る
for(int i = 0; i < N; i++){
if(i > 0){
vvi[i].push_back(i - 1);
}
if(i < N - 1){
vvi[i].push_back(i + 1);
}
if(i < N - d[i]){
vvi[i].push_back(i + d[i]);
}
}
ans[0] = 0;
while(true){
int r = -1;
for(int i = 0; i < N; i++){
if(flag[i] == 0 && ((r == -1) || (ans[i] < ans[r]))){
r = i;
}
}
if(r == -1)break;
flag[r] = 1;
for(int i = 0; i < vvi[r].size(); i++){
ans[vvi[r][i]] = min(ans[vvi[r][i]], ans[r] + 1);
}
}
cout << ans[N - 1] << endl;
12、文字列対策 string
string s(4, 'a'); // "aaaa" を作る
stirng s = "abc";
char c = s[0];
string s1 = s + "aa";
長さは
s.length() でも s.size() でもどちらでも良い。
比較
if(s == "abc"){
// s が "abc" である
}
切り出し
string s("0123456789");
s.substr(5); // "56789"
s.substr(5, 3); // "567"
分離
// 文字列 s を文字 c で分離
vector<string> split(string s, char c){
vector<string> ret;
string s1;
for(int i = 0; i <= s.size(); i++){
if(i == s.size()){
ret.push_back(s1);
return ret;
}
if(s[i] == c){
ret.push_back(s1);
s1 = "";
}
else{
s1 += s[i];
}
}
}
char * のポインタを渡したい場合は、
char *c = s.c_str();
検索
s.find("bc"); // ある場合はインデックス 無い場合は -1 を返す。
数字から文字列への変換
string s;
stringstream ss;
ss << s;
ss >> a; // double のときには + 1e-9 などをするのを忘れずに
文字列から数字への変換
sscanf(s.c_str(), "%d", &num);
文字列の反転
// 文字列の反転
reverse(s.begin(), s.end());
これを応用すれば上から読んでも下から読んでも同じか?という判定もできる。
ソート
vector<string> v;
v.push_back("cde");
v.push_back("abc");
sort(v.begin(), v.end());
文字列内でソートを行うこともよくある。
string s = "bca";
sort(s.begin(), s.end());
13、数学問題の対策
// 最大値
max(a, b);
// 最小値
min(a, b);
// 3つの値の中間値
vector に入れて sort した2番目の要素
// 素数であるかを判定
int isPrime(int n){
int i;
if(n < 2){
return 0;
}
else if(n == 2){
return 1;
}
if(n % 2 == 0){
return 0;
}
for(i = 3; i * i <= n; i += 2){
if(n % i == 0){
return 0;
}
}
return 1;
}
// 最大公約数
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
// 最小公倍数
int lcm(int a, int b){
return a * b / gcd(a, b);
}
/* 素因数分解
vector<int> v;
int m = 15;
while(m % 2 == 0){
v.push_back(2);
m /= 2;
}
for(int i = 3; i * i <= m; i += 2){
while(m % i == 0){
v.push_back(i);
m /= i;
}
}
if(m > 1){
v.push_back(m);
}
vector<int>::iterator itr = v.begin();
while(itr!= v.end()){
cout << (*itr++) << endl;
}
// 順列の作成
next_purmutation は次の順列を返すので、
全探索なら最初の配列を昇順にソートする必要あり。
const int n = 3;
vector<int> v;
for(int i=0; i < n; i++){
v.push_back(i);
}
do{
cout << "[ " << v[0];
for(unsigned int i = 1; i < v.size(); i++){
cout << ", " << v[i];
}
cout << " ]" << std::endl;
}while(next_permutation(v.begin(), v.end()));