AtCoderチャレンジまとめ(0)
やりたいこと
そんなわけでAtCoderにチャレンジ ! の前の準備笑
教科書
けんちょんさんわかりやすい記事ありがとうございますm( )m
A問題の学び
問題分をよく読んで出力形式には注意すること。ex: cout << a << " " << b << endl;の" "を書き忘れる etc ...。
(プロコンの場合)変数名はシンプル。タイピング速度重視。
一行でかけるときはまとめる。 ex: if (c % 2 == 0) cout << "Even" << endl;
stringを受けて文字にアクセスするときはこう↓
string s; cin >> s; int counter = 0; if (s[0] == '1') ++counter;
++iとi++について↓
・ ++i の作用は式の値として、i + 1 の値を返す事、副作用は i に i + 1 の結果が代入される。
・ i++ の作用は式の値として、i の値を返す事、副作用はその後 i に i + 1 の結果が代入される。
B問題の学び
boolの真偽は小文字でtrue, false。大文字で書いちゃダメ。
計算量が少なく、考える時間を短縮したいときはfor分での全探索が有効なケースあり。
n進数の考え方やbit演算ができると良い。
sort大事。
#include <algorithm> int N; int a[100]; // a[0:N] を大きい順にソート sort(a, a + N, greater<int>());
バケット法よく使う。
setが便利。
#include <set> ... set<int> values; // insert するときに重複を取り除いてくれます for (int i = 0; i < N; ++i) { values.insert(d[i]); // 挿入します }
- 最大最小もよく使う。
const int lower = max(A,C); const int upper = min(B,D);
計算の工夫として、N!のSで割った余りを求めたい時は、オーバーフローを防ぐため、N! % Sより、(N%S) * ((N-1)%S)* ・・・としたりする。
a以上b以下の整数のうち条件を満たすものの個数を求める問題ではf(n) := 0以上n以下の整数のうち条件を満たすものの個数のように関数定義するとf(b)-f(a-1)で求めることができる。
C問題の学び
計算量オーダーの考え方が大事。
解き始める前にどのように解くかを計算量やタイプ量、便利関数などを加味してしっかり考えることが大事。ex: 後ろからGreedyした方が簡単 etc...
探索方法大事。
パリティ(「偶数」と「奇数」に関する性質)の考え方大事。
グリッドの作り方例: char c[55][55]; string board[50];
上下左右斜め移動の表し方例 ↓
const int dx[8]={1,0,-1,0,1,-1,-1,1}; const int dy[8]={0,1,0,-1,1,1,-1,-1};
感想
めっちゃ楽しい :D