ホームに戻る
N=100000問題の例題
０、はじめに
N=100000問題とは入力が100000個〜500000個程度の問題です。
CodeforcesやAtCoderでよく出題される傾向があります。
TopCoderではなぜかほとんど出ません。
N=100000である理由はいくつかあります。
・どの言語でも入力の時点でTLEすることがない。
・O(N^2)の解法をTLEさせるには十分な量である。
・O(NlogN)の解法に無理がない。
１つめの理由はN=1000000とかにしてしまうと、
入力処理が遅い言語が入力を読むだけでTLEするケースがあります。
最初から入力できなくて解けないというのはかわいそうです。
ちなみにN=1000000の場合はC++でもcinの入力でTLEすることがあります。
この場合はscanfを使うと間に合うようです。
２つめの理由はN^2が10000000000なので十分TLEすることです。
O(N^2)をしてしまうとTLEで落ちる問題が作りやすいです。
これはC++などの高速な言語でもTLEする十分な計算量です。
３つめはO(NlogN)の処理に余裕があることです。
どの言語でも例えばソートなどのO(NlogN)の処理に余裕が持てます。
単なるソートができないためにTLEは嫌ですよね。
O(N^2)だとTLEだがO(NlogN)だと通る問題が作りやすい。
不安であればN=200000などへ増やせば良い。
もしこれがO(N^3)とO(N^2logN)だと差が微妙で調整が難しい。
このように言語間の処理速度の差を解消する問題が作りやすいのです。
多くの言語をサポートするコンテストほどこの傾向は強いでしょう。
よって、競技プログラミングではN=100000が多用されます。
１、よくあるアルゴリズム
N=100000の制約の場合の解法はほとんどの場合O(NlogN)かO(N)です。
たまにO(NN^(1/2))があるかもしれませんがこれも無理がなければ通ります。
O(N)の場合、全探索、しゃくとり法、imos法などがあると思います。
O(NlogN)の場合、ソート、priority_queue、２分探索、LIS、セグメント木、BITなどがあります。
O(NN^(1/2))の場合、平方分割があります。
動的計画法の場合はO(NM)やO(NlogN)になると思います。
動的計画法の場合もO(NlogN)のときにはどこかでO(logN)のアルゴリズムが必要です。
数え上げであればnCrの計算を使って計算することになると思います。
この場合、nCrが100000C50000のような計算でもO(1)で計算する必要性があります。
これは前準備さえできていれば可能です。
グラフだと使えるのがダイクストラ法や最小全域木を求めるやLCAです。
最大流や最小費用流などはこの制約ではまず使えないと考えて良いです。
文字列問題の場合はSuffix ArrayやKMP、manachar、Z algorithmなどがあります。
ローリングハッシュなども使えると思います。
条件が動いて固定できない場合などは包除原理で解ける可能性があります。
以下でどのような問題が出題されてどのような解法があるかを書きました。
各アルゴリズムに関する説明は他で探してください。
２、例題１
N人の生徒がいます。(1<=N<=200000)
i番目の生徒のテストAの順位はAi位です。(1<=Ai<=N)
i番目の生徒のテストBの順位はBi位です。(1<=Bi<=N)
それぞれのテストで順位が同じ人はいません。
これからK人の合格者を決めていきます。(1<=K<=N)
まずテストAの最上位の生徒を合格とします、
次にテストBの最上位の生徒を合格とします。
これをテストA、テストB、テストA・・・とK人まで繰り返します。
K人の合格者の番号を昇順に列挙しなさい。
1行目にN、Kが与えられる。
続いてN行でi番目の生徒のテストA、テストBの点数が与えられる。
・サンプル入力
3 2
3 2
2 3
1 1
・サンプル出力
0
2
・サンプルの説明
N=3、K=2のときを考えます。
まずテストAで1位の2番目の生徒が合格します。
次にテストBの上位者が合格するのですが、
テストBの1位はすでに合格しています。
よって、テストBが2位の0番目の生徒が合格します。
以上で2名の合格者が決まりました。
・解法
それぞれのテストで上位者を取り出していけば良いです。
ただしソートをN回やってはいけません。
ソートの計算量はO(NlogN)なのでN回のソートでO(N^2logN)になります。
それぞれのテストでの順位表を作って上から消せるのであれば消していけば良いです。
なおvectorのeraceも計算量がO(N)なので避けないといけません。
この場合、実際にeraceを使わなくても消したことにすることで十分です。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
long long d[100100];
int main() {
long long n,k;
cin>>n>>k;
vector<pair<long long,long long> > v1;
vector<pair<long long,long long> > v2;
for(long long i = 0; i < n; i++){
long long a,b;
cin>>a>>b;
v1.pb(make_pair(a,i));
v2.pb(make_pair(b,i));
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
memset(d,0,sizeof(d));
vector<long long> ans;
long long t = 0;
long long c = 0;
long long index1 = 0;
long long index2 = 0;
while(1){
if(c==k)break;
if(t==0){
if(d[v1[index1].second]==0){
ans.push_back(v1[index1].second);
d[v1[index1].second]=1;
t = 1;
c++;
}
else{
index1++;
}
}
else{
if(d[v2[index2].second]==0){
ans.push_back(v2[index2].second);
d[v2[index2].second]=1;
t = 0;
c++;
}
else{
index2++;
}
}
}
sort(ans.begin(),ans.end());
for(long long i = 0; i < k; i++){
cout << ans[i] << endl;
}
return 0;
}
３、例題２
N個の連続した休暇をもらうことができます。(1<=N<=100000)
i番目の休暇はAi日目からBi日目までです。(1<=Ai<=Bi<=400000)
それぞれの休暇は日が重複することがあります。
すべての休暇をつなぎ合わせた最長の連続した休暇は何日間か？
1行目にNが与えられる。
続いてN行でi番目のAi、Biが与えられる。
・サンプル入力
4
1 5
6 7
1 1
9 10
・サンプル出力
7
・サンプルの説明
1日目から7日目まで7日間の休暇が最長です。
9日目から10日目まで2日間の休暇がありますが最長ではありません。
・解法
imos法としゃくとり法を使います。
imos法は典型的なやり方で使います。
連続した休暇の数を数えるのにしゃくとり法を使います。
両方ともよく使うので使い方は覚えておくと良いです。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
long long d[500000];
int main() {
long long n;
cin >> n;
memset(d,0,sizeof(d));
for(long long i = 0; i < n; i++){
long long a, b;
cin >> a >> b;
d[a]++;
d[b + 1]--;
}
for(long long i = 1; i < 450000; i++){
d[i] += d[i - 1];
}
long long mx = 0;
long long index1 = 1;
long long index2 = 1;
while (1) {
if (index1 == 450000)break;
if (index2 == 450000)break;
if (!(d[index1-1]==0&&d[index1]>0)){
index1++;
}
else if(!(d[index2-1]>0&&d[index2]==0)){
index2++;
}
else {
mx = max(mx, index2 - index1);
index2++;
index1 = index2;
}
}
cout << mx << endl;
return 0;
}
４、例題３
N本の木を植えます。（1<=N<=100000）
木は植えるときに実は１つもなっていません。
i番目の木はAi日目に植えます。（1<=Ai<=1000000000）
木は１日たつごとに１つの実がなります。
i番目の木は植えた日からBi日後になくなります。（1<=Bi<=1000000000）
なくなる日を含めそれ以降は実は収穫できません。
あなたはある１日を決めて今ある木のすべての実の収穫をします。
最適な日を選んだとき実は最大で何個収穫できるでしょうか？
1行目にNが与えられる。
続いてN行でi番目のAi、Biが与えられる。
・サンプル入力
2
2 4
3 5
・サンプル出力
5
・サンプルの説明
2日目に0番目の木を植えます。
木には3日目には実が1個、4日目には実が2個、5日目には実が3個あります。
6日目には木がなくなってしまうので実は0個です。
3日目に1番目の木を植えます。
木には4日目には実が1個、5日目には実が2個、6日目には実が3個、7日目には実が4個あります。
7日目には木がなくなってしまうので実は0個です。
この場合は5日目に全ての実を取れば5個の実を収穫できます。
・解法
imos法と座標圧縮を使います。
imos法の使い方は少し変則的です。
この手の問題は範囲が1<=Ai,Bi<=1000000000であっても、
座標圧縮で結局1<=Ai,Bi<=100000程度までに圧縮できる場合がほとんどです。
座標圧縮はバグが出やすいので注意しましょう。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
long long d[400000];
long long dd[400000];
int main() {
long long n;
cin>>n;
vector<pair<long long,long long> > v;
set<long long> se;
for(ll i = 0; i < n; i++){
long long a,b;
cin>>a>>b;
b = a+b-1;
v.push_back(make_pair(a,b));
se.insert(a);
se.insert(b);
se.insert(b+1);
}
vector<long long> vse(se.begin(),se.end());
map<long long,long long> ma;
for(ll i = 0; i < vse.size(); i++){
ma[vse[i]] = i+1;
}
memset(d,0,sizeof(d));
memset(dd,0,sizeof(dd));
for(ll i = 0; i < v.size(); i++){
d[ma[v[i].first]]++;
d[ma[v[i].second]+1]--;
dd[ma[v[i].second]+1]-=v[i].second-v[i].first+1;
}
long long mx = 0;
long long p = 0;
long long q = 0;
for(ll i = 0; i < vse.size(); i++){
if(i!=0){
q+=p*(vse[i]-vse[i-1]);
}
p += d[ma[vse[i]]];
q += dd[ma[vse[i]]];
mx = max(mx,q);
}
printf("%lld\n",mx);
return 0;
}
５、例題４
N人の生徒がいます。（2<=N<=100000）。
i番目の生徒の身長はHiです。（1<=Hi<=1000000000）
i番目の生徒の体重はWiです。（1<=Wi<=1000000000）
N人の生徒から異なるi番目の生徒とj番目の生徒を選びます。
Hi>HjかつWi<Wj、もしくはHi<HjかつWi>Wjとなる組み合わせは何通りか？
1行目にNが与えられる。
続いてN行でi番目のHi、Wiが与えられる。
・サンプル入力
3
1 3
2 2
3 2
・サンプル出力
2
・サンプルの説明
(1,3)と(2,2)、(1,3)と(3,2)の2つは有効な組み合わせです。
(2,2)と(3,2)はHi<HjですがWi=Wjなので含みません。
・解法
ソート、座標圧縮、BITを使います。
まず体重を座標圧縮します。
体重は比較に使うだけなので圧縮しても結果には影響しません。
身長でソートします。
身長の低い順からみていきます。
体重をBITに入れていきます。
BITを使うことである体重より体重が大きい人の人数をO(logN)で数えることができます。
この工夫は典型なので覚えておくと良いです。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
#define N_MAX 100100
long long bit[N_MAX + 1];
long long sum(long long i){
long long s = 0;
while(i > 0){
s += bit[i];
i -= i & -i;
}
return s;
}
void add(long long i, long long x){
while(i <= N_MAX){
bit[i] += x;
i += i & -i;
}
}
vector<pair<long long,long long> > v;
int main() {
ll n;
cin>>n;
set<long long> se1;
set<long long> se2;
for(long long i = 0; i < n; i++){
long long a,b;
cin>>a>>b;
v.push_back(make_pair(a,b));
se1.insert(a);
se2.insert(b);
}
vector<long long> vse1(se1.begin(),se1.end());
vector<long long> vse2(se2.begin(),se2.end());
map<long long,long long> ma;
for(long long i = 0; i < vse2.size(); i++){
ma[vse2[i]] = i+1;
}
memset(bit,0,sizeof(bit));
sort(v.begin(),v.end());
for(long long i = 0; i < v.size(); i++){
v[i].second = ma[v[i].second];
}
long long ans = 0;
long long index = 0;
for(long long i = 0; i < vse1.size(); i++){
long long p = vse1[i];
vector<long long> v1;
while(1){
if(index==v.size())break;
if(v[index].first!=p)break;
v1.push_back(v[index].second);
index++;
}
for(long long j = 0; j < v1.size(); j++){
ans += sum(100050)-sum(v1[j]);
}
for(long long j = 0; j < v1.size(); j++){
add(v1[j],1);
}
}
printf("%lld\n", ans);
return 0;
}
６、例題５
１列に並んだN個のマスがあります。（2<=N<=100000）
各マスには正の整数Aiが書き込まれています。（1<=Ai<=100000）
左から1番目、2番目のマスに1つずつ石が置かれています。
3番目のマス、4番目のマス・・・と順に右方向へいずれかの石を移動します。
石を移動するコストは移動元と移動先のマスの数値の差の絶対値です。
最終的に左からN番目のマスにどちらかの石を1つ移動させる。
(もうひとつの石は最後はどの位置でも構いません。)
最適な移動をした場合の最小のコストを求めよ。
1行目にNが与えられる。
続いてN個の値が0からN-1番まで順に空白を挟んで与えられる。
・サンプル入力
4
5 3 5 7
・サンプル出力
2
・サンプルの説明
例えば、
左から2番目の石を3番目に移動するコストは2です。
次に左から1番目の石を4番目に移動するコストは2です。
この場合は合計4のコストがかかってしまい最小ではありません。
左から1番目の石を3番目に移動するコストは0です。
次に左から3番目の石を4番目に移動するコストは2です。
この2つの操作で移動するとコストは合計2で最小です。
・解法
動的計画法を使うがdp[100000][100000]はできない。
よってdp[100000]でなんとかする方法を考える。
状態は現在の石の位置とdp[もう1個の石の位置]での移動コストの最小値とする。
さて、最適な石の移動は2通りある。
現在の石を1つ進めるかもう1個の石を現在の石の前に進めるか？
もう1個の石を進める場合は、もう1個の石のある複数の場所から最小値を求める。
しかし、このときマスに書かれた数は異なるため最小値は一律に求まらない。
よって、記録する値を「最小値-書かれた数」と「最小値+書かれた数」とする。
このようにすれば与えられた区間で一律に最小値を求めることができる。
移動先の数>移動元の数のとき移動先の数+(最小値-書かれた数)とでき、
移動先の数<移動元の数のとき(最小値+書かれた数)-移動先の数とできる。
複数の場所から最小値を求めるのはセグメント木で行う。
また、もう1個の石を進める場合は現在の石を1つ進めるコストを引いておく。
最後に現在の石を1つ進める全てのコストと最適な移動コストを加算すれば良い。
動的計画法でもセグメント木を使ってO(NlogN)にすることができる。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
#define N_MAX (1<<17)
#define INF 1000000000000LL
int nn_mn1;
int nn_mn2;
long long dat_mn1[(2 * N_MAX) - 1];
long long dat_mn2[(2 * N_MAX) - 1];
void init_mn1(int n1){
nn_mn1 = 1;
while(nn_mn1 < n1)nn_mn1 *= 2;
for(int i = 0; i < 2 * nn_mn1 - 1; i++){
dat_mn1[i] = INF;
}
}
void init_mn2(int n1){
nn_mn2 = 1;
while(nn_mn2 < n1)nn_mn2 *= 2;
for(int i = 0; i < 2 * nn_mn2 - 1; i++){
dat_mn2[i] = INF;
}
}
void update_mn1(int k, long long a){
k += nn_mn1 - 1;
dat_mn1[k] = a;
while(k > 0){
k = (k - 1) / 2;
dat_mn1[k] = min(dat_mn1[k * 2 + 1], dat_mn1[k * 2 + 2]);
}
}
void update_mn2(int k, long long a){
k += nn_mn2 - 1;
dat_mn2[k] = a;
while(k > 0){
k = (k - 1) / 2;
dat_mn2[k] = min(dat_mn2[k * 2 + 1], dat_mn2[k * 2 + 2]);
}
}
long long query_mn1(int a, int b, int k, int l, int r){
if(r <= a || b <= l)return INF;
if(a <= l && r <= b){
return dat_mn1[k];
}
else{
long long vl = query_mn1(a, b, k * 2 + 1, l, (l + r) / 2);
long long vr = query_mn1(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
long long query_mn2(int a, int b, int k, int l, int r){
if(r <= a || b <= l)return INF;
if(a <= l && r <= b){
return dat_mn2[k];
}
else{
long long vl = query_mn2(a, b, k * 2 + 1, l, (l + r) / 2);
long long vr = query_mn2(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
int main() {
long long n;
cin>>n;
vector<long long> v;
for(long long i = 0; i < n; i++){
long long a;
cin>>a;
v.push_back(a);
}
long long total = 0;
init_mn1(100100);
init_mn2(100100);
update_mn1(v[0],0-v[0]);
update_mn2(v[0],0+v[0]);
for(long long i = 2; i < n; i++){
long long a1 = query_mn1(0,v[i]+1,0,0,nn_mn1) + v[i] - abs(v[i]-v[i-1]);
long long b1 = query_mn2(v[i],100050,0,0,nn_mn2) - v[i] - abs(v[i]-v[i-1]);
long long c1 = query_mn1(v[i-1],v[i-1]+1,0,0,nn_mn1);
long long d1 = query_mn2(v[i-1],v[i-1]+1,0,0,nn_mn2);
if(min(a1,b1)-v[i-1]<c1){
update_mn1(v[i-1],min(a1,b1)-v[i-1]);
}
if(min(a1,b1)+v[i-1]<d1){
update_mn2(v[i-1],min(a1,b1)+v[i-1]);
}
total += abs(v[i]-v[i-1]);
}
long long mn = INF;
for(long long i = 0; i < 100050; i++){
mn = min(mn,query_mn1(i,i+1,0,0,nn_mn1)+i);
mn = min(mn,query_mn2(i,i+1,0,0,nn_mn2)-i);
}
printf("%lld\n", mn + total);
return 0;
}
６、例題６
1列になったN個の区画からなる土地がある。（1<=N<=1000000000）
それぞれ1個の区画に1つの家を建てることができる。
ただし、条件があり隣り合った区画には家を建てることができない。
家はKつまで建てることができるとして何通りの家の建て方があるか？（0<=K<=100000）
1000000007で割った余りを答えよ。
なお、家が1つも建っていない場合も答えに含む。
1行目にN、Kが与えられる。
・サンプル入力
3 3
・サンプル出力
5
・サンプルの説明
全く家を建てない方法が1通り。
3つの区画のいずれか1つに家を建てる方法が3通り。
3つの区画の両端に1つずつ家を建てる方法が1通り。
隣あってしまうので3つの区画すべてに家を建てることはできない。
よって、合計5通りの家の建て方がある。
・解法
Nが1000000000のことを考えると動的計画法は使えません。
この場合、nCrを使った数え上げをしてやります。
方法はKについてすべて全探索します。
例えば家が3つの時、最初に「家、空き地、家、空き地、家」と配置してしまいます。
その後、残った空き地を適当なところに挿入する方法を数え上げます。
このようにするとかならず家同士が隣りあうことはありません。
さて、このように0からKまでを全探索すれば良いのですが、
n=1000000000、k=100000のようなときにnCrを毎回計算するわけにはいきません。
よって、いくつかを先に計算しておいて、実際にはnCrの計算をO(1)で行うことを考えます。
このようにすると前処理O(NlogN)、全探索をO(N)で行うことができます。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
#define MOD 1000000007
#define N_MAX 600000
long long mn;
long long fact1[N_MAX];
long long rfact1[N_MAX];
long long rfact2[N_MAX];
long long modpow(long long a, long long b){
long long r = 1LL;
while(b){
if(b & 1LL)r *= a;
if(r >= MOD)r %= MOD;
a *= a;
if(a >= MOD)a %= MOD;
b >>= 1LL;
}
return r;
}
long long nCr(long long n, long long r){
long long ret = 1LL;
ret *= fact1[n-mn];
ret %= MOD;
ret *= rfact1[n-mn-r+1];
ret %= MOD;
ret *= rfact2[r];
ret %= MOD;
return ret;
}
int main() {
long long n,k;
cin>>n>>k;
mn = max(1LL,n-300000LL);
memset(fact1,0,sizeof(fact1));
fact1[0]=mn;
for(int i = 1; i < N_MAX; i++){
fact1[i] = fact1[i-1]*(mn+i);
fact1[i] %= MOD;
}
memset(rfact1,0,sizeof(rfact1));
rfact1[0]= 1LL;
for(int i = 1; i < N_MAX; i++){
rfact1[i] = rfact1[i-1]*modpow(mn+i-1,MOD-2);
rfact1[i] %= MOD;
}
memset(rfact2,0,sizeof(rfact2));
rfact2[0]=1LL;
for(int i = 1; i < N_MAX; i++){
rfact2[i] = rfact2[i-1]*modpow(i,MOD-2);
rfact2[i] %= MOD;
}
long long ans = 0;
for(int i = 0; i < k+1; i++){
if(n-i+1>0&&n-i+1>=i){
ans += nCr(n-i+1,i);
ans %= MOD;
}
}
cout << ans << endl;
return 0;
}
