💻
AtCoderで得たコーディングの発想
はじめに
AtCoderで得た、コーディングの発想、簡潔な書き方、アルゴリズムの考え方をまとめます。
抽象的に書きました。記事としての完成度は低いです。
現在緑レートなので、そのレベルの記事という点に注意してください。
簡潔なコーディング
- while文の使い方
while文を正しく使えると、コードが簡潔になる時がある。
例)xが素数になるまで1ずつ増やす。
簡潔ではない例
while(true){
if(is_prime(x)){
break;
}
x++;
}
簡潔な例
while(!is_prime(x)){
x++;
}
おまけ
while(!is_prime(x++)){
// 処理
}
- if文の使い方
if文を正しく使えると、コードが簡潔になる時がある。
例) x[i]<100の時に処理を実行する。
簡潔ではない例
for(int i=0;i<n;i++){
if(x[i]<100){
// 処理
}
}
簡潔な例
for(int i=0;i<n;i++){
if(x[i]<100) continue;
// 処理
}
- next_permutationを値そのもので使う。
インデックスで使うと、コードが長くなる。
簡潔ではない例
vector<int> x = {1,2,3};
idx = iota(0, (int)x.size(), 0);
do{
// 処理
// x[idx[0]], x[idx[1]], x[idx[2]]で使う。
}while(next_permutation(idx.begin(), idx.end()));
簡潔な例
vector<int> x = {1,2,3};
do{
// 処理
// x[0], x[1], x[2]で使う。
}while(next_permutation(x.begin(), x.end()));
- 単純な二分探索はlower_bound, upper_boundを使うと早い。
vector<int> x = {1,2,3,4,5};
int a = 3;
int idx = lower_bound(x.begin(), x.end(), a) - x.begin(); // 3以上の最小の値のインデックスを取得
// 3以上の最小の値は3なので、idx=2になる。
- 問題を分解して考えすぎると、コードが長くなる時がある。
- 問題の発想、解放が分かったとき、そのままコードに落とし込むのではなく、実装向けに考え直す。
考え方
- [true, ... , true, false, ... , false]に置き換えて、二分探索をする。
これは二分探索で解決可能だが、この形を見抜けるかどうかが重要。
条件を満たす最大のxを求める問題で、単調性があるとき、この形になる。
条件がfの時、f(x)を計算して、その値で二分探索をする。
このfが複雑な処理の時、見抜けにくくなる。
bool f(int x){
//問題の条件を満たすかどうかを判定する関数
}
int l = 0, r = 1e9+1;
while(l+1<r){
int m = (l+r)/2;
if(f(m)){
l = m;
}else{
r = m;
}
}
- 順番を入れ替えても、答えが変わらない場合は、とりあえずソートしてみる。
ソートすることで、見えてくることがある。 - 考える方向を変える。
xが条件を満たすかではなく、条件を満たすようなxを考える。 - 累積和を使う。
累積和を使うことで、単調性が生まれることがある。 - 問題の制約条件から計算量を考えるというメタ的発想。
例えば、nが1000の時、O(n^2)は間に合うので、そのようなアルゴリズムを使いそうだと考える。
nが2×10^6の時、O(n^2)は間に合わないので、O(nlogn)やO(n)のアルゴリズムを考える。
nが10の時、O(n!)が間に合う。など - 一つ次元を上げて考えてみる。
- 分からなくなったとき、いったん今までの考え方を捨てたり、一番最初に思いついた発想に戻ってみる。
最初の考え方から導入して、今の発想を絡めて考えると、解決できることがある。 - ボトルネックを考える。
間違っているときにとりあえず考えること。
- intの範囲を超えてないか。
- データ構造自体が重くないか。特にsetやmapは重い。
Discussion