441 文字
1 分
アルゴリズム学習：ビット演算・離散化・区間マージ
1. ビット演算
1.1 背景
ビット演算を行う際には、数を二進数としてみなし、ビット演算は数の特定の位置にある値に対して演算を行うものです。
1.2 練習問題
数の中の1を探すときには、主に2つの方法があります。
- 当
1<<i & x = 1のとき、第iビットには1が存在します lowbit(x) = x & -xを用いて末尾の1を見つける
参考コード：
int lowbit(int x){ return x & -x;}void solve(){ for(int i=0;i<n;i++){ cin>>t; int cnt = 0; for(;t;t -= lowbit(t)) cnt++; cout<<cnt<<' '; }}2. 離散化
2.1 背景
取得したデータが長い範囲にわたって疎に分布している場合、使用するメモリを節約しデータを検索する速度を高めるために、データを離散化して処理します。
2.2 練習問題
クエリ問題については、累積和を用いることで O(1) 内に求められるため、この問題の焦点はデータの離散化にあります。
数軸上で使用するべき数は挿入位置x、左右の範囲を表すl,rの3つであり、これら3つの数を離散化後の配列に格納し、それぞれの位置を元の配列の位置と対応づけておけばよい。
参考コード：
void solve(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>x>>c; if(a[x]) a[x] += c; else a[x] = c; all.push_back(x); } while(m--){ cin>>l>>r; q.push_back({l,r}); all.push_back(l); all.push_back(r); } sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end());
for(int i=1;i<=all.size();i++){ int t = a[all[i-1]]; s[i] = t + s[i-1]; } for(auto i:q){ l = lower_bound(all.begin(),all.end(),i.first)-all.begin(); r = lower_bound(all.begin(),all.end(),i.second)-all.begin(); cout<<s[r+1] - s[l]<<endl; }}3. 区間合併
3.1 背景
複数の区間を高速にマージするには、区間を開始点でソートし、被覆しているかどうかを判断すればよい。
3.2 練習問題
参考コード：
void solve(){ for(int i=0;i<n;i++){ cin>>l>>r; a.push_back({l,r}); } sort(a.begin(),a.end(),[](PII t1,PII t2){ return t1.first < t2.first; }); int al = -2e9,ar = -2e9; for(auto i : a){ int ml = i.first,mr = i.second; if(ml > ar){ ans ++; al = ml;ar = mr; }else if(mr > ar){ ar = mr; } }cout<<(ans ? ans : 1)<<endl;} 共有
この記事が役に立ったときは、ぜひ他の人に共有してください!
アルゴリズム学習：ビット演算・離散化・区間マージ
https://dreaife.tokyo/jp/posts/bitwise-algorithm/ 一部の情報は古い可能性があります
関連した投稿 スマート
1
アルゴリズム学習：前計算和・差分・双方向ポインタ
algorithm 前計算和（prefix sum）、差分配列、双方向ポインタ法（two pointers）の原理と応用を紹介します。前計算和は配列区間和を高速に計算し、差分配列は区間更新を効率化し、双方向ポインタ法はポインタを維持することでクエリ効率を最適化します。理解と応用を助けるため、関連例題と参考コードも掲載しています。
2
高精度演算の学習記録
algorithm 高精度演算には加算、減算、乗算、除算が含まれ、通常のデータ型の範囲を超える大きな数を扱う際に用いられます。加算と減算は筆算のシミュレーションで実装し、乗算と除算は各桁を順に処理しつつ先頭のゼロ除去に注意します。理解と実装に役立つ例題と参考コードも掲載しています。
3
ソートと二分探索の学習
algorithm クイックソートとマージソートの原理と実装を、時間計算量や関連問題とあわせて紹介します。クイックソートは中間値を基準に数列を2つに分割して整列し、マージソートは整列済み部分列を統合していきます。整数・浮動小数点数に対する二分探索アルゴリズムとその実装方法についても解説します。
4
面接アルゴリズム学習1
algorithm 蛇行行列の埋め込み、単方向連結リストの高速ソート、ピーク値や極小値の探索、卵の硬度問題、最小値取得をサポートするスタック、連結リストの循環開始ノード探索など、複数のアルゴリズム面接問題とその解法をまとめています。各問題には詳細な説明、入出力形式、サンプルコードが付いています。
5
新時代における第一回の選抜
life AI技術の発展に伴い、高度なモデルを利用するコストが社会の階層化を招き、経済力のある人だけがこれらのモデルを使えるようになる可能性がある。現在の価格はまだ許容範囲だが、将来的な値上がりにより大多数が負担できなくなり、第一のふるい分けが生じるかもしれない。筆者はこの現象に不安を覚えつつ、AIの応用がすでにプログラミング領域を超え、より広範な産業へと広がっていることも実感している。新しい世界の課題と機会に向き合いながら、個人は時代の推進力に押されつつ探索を続けている。