前回の続き

全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索

灰コーダーが学ぶいもす法

ここまで学習した記事を読むと分かってもらえますが、
aojのitp1とitp2、全探索と二分探索、dfsとbfsでは茶色コーダーに慣れません。
少し苦手な問題で灰色パフォーマンスをとると茶色へいけないのです。
多分、いもす法とdp、ALDS1、NTL、GRL、CGL、DTLいる...。

いもす法とは

@imosさんが京都大学院？で提出した修論である。
ふぁっ！
この人、天才じゃないか。

解説記事

いもす研

ふむふむ、私のようなザコーダーにも分かりやすい記事。
さすが京都大。
つまり累積和を応用するアルゴリズムだと理解。
便利なのは多配列に応用できる。
MAP系に使えるのは便利ですね。

その前に累積和とは？

累積和を何も考えずに書けるようにする！

適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようになる手法

累積和

A - Abundant Resources

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<queue>
# include<stack>
# include<cmath>
# include<cstdio>
# include<cctype>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n;
    cin >> n;
    
    vector<ll> A(n+1);
    for(int i=1; i<n+1; i++){
        cin >> A[i];
        if(i>0) A[i] += A[i-1];
    }
    
    rep(i, n+1){
        ll max_a=0;
        rep(j, n+1){
            if(j-i<0) continue;
            if(max_a<A[j]-A[j-i]) max_a = A[j]-A[j-i];
        }
        if(i>0) cout << max_a << endl;
    }
    
    return 0;
}

D - Sum of difference

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
void solve(int n, vector<ll> &A){
    vector<ll> dp(n+1, 0);
 
    rep(i, n){
        dp[i+1] = dp[i] + A[i];
    }
    reverse(A.begin(), A.end());
    reverse(dp.begin(), dp.end());
 
    ll res =0;
    rep(i, n){
        ll v = n - (i+1);
        ll sum = A[i] * v;
        res += sum - dp[i+1];
    }
    cout << res << endl;
}
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
 
    vector<ll> A(n);
    rep(i, n) cin >> A[i];
    sort(A.begin(), A.end());
    solve(n, A);
 
    return 0;
}

二次元累積和

D - AtCoder Express 2

2次元配列での累積和。
R軸で累積和を行い範囲内でqー（p−１）、再度L軸で合計を取ってます。
まだ良くわかってないです。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<queue>
# include<stack>
# include<cmath>
# include<cstdio>
# include<cctype>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, m, q;
    cin >> n >> m >> q;
    
    int field[501][501]={0};
    int ans[501][501]={0};
    for(int i=1; i<=m; i++){
        int l, r;
        cin >> l >> r;
        field[l][r]++;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ans[i][j] = ans[i][j-1] + field[i][j];
        }
    }
    
    rep(i, q){
        int p, q;
        cin >> p >> q;
        
        int sum=0;
        for(int j=p; j<=q; j++){
            sum += ans[j][q] - ans[j][p-1];
        }
        cout << sum << endl;
    }
    
    return 0;
}

いもす法

D - Water Heater

計算量をN(C＋T）にできるってことなのでこんな感じだと思います。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<queue>
# include<stack>
# include<cmath>
# include<cstdio>
# include<cctype>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, w;
    cin >> n >> w;
    
    ll times[200001]={0};
    rep(i, n){
        int s, t, p;
        cin >> s >> t >> p;
        
        times[s]+=p;
        times[t]-=p;
    }
    
    ll M = 0;
    for (int i = 0; i < 200001; i++) {
        if (0 < i) times[i] += times[i-1];
        if (M < times[i]) M = times[i];
    }

    if(w>=M) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

AC通った。
いもすさん天才！

C - AtColor

基本問題っぽいです。
D - Water Heaterをほぼ同じ問題です。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<queue>
# include<stack>
# include<cmath>
# include<cstdio>
# include<cctype>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n;
    cin >> n;
    
    ll color[1000007]={0};
    for(int i=0; i<n; i++){
        int a, b;
        cin >> a >> b;
        color[a+1]++;
        color[b+2]--;
    }
    
    ll max_buyer=0;
    for(int i=1; i<1000003; i++){
        color[i] = color[i] + color[i-1];
        max_buyer = max(max_buyer, color[i]);
    }
    cout << max_buyer << endl;

    return 0;
}

イベントソート

D - Snuke Prime

いもす法では解答できない10^9などの数に対応する為のアルゴリズム。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
int main() {
	ll n,c;
	cin >> n >> c;
	vector<P> event;
	for(int i=0;i<n;i++){
	    int s,t,p;
		cin >> s >> t >> p;
		event.push_back(make_pair(s,p));
		event.push_back(make_pair(t+1,-p));
	}
	sort(event.begin(), event.end());
	ll res=0;
    ll value=0;
    int day=0;
	for(int i=0; i<event.size(); i++){
        P p = event[i];
 
	if(value>c) res += (ll)(event[i].first - day) * c;
        else res += (ll)(event[i].first - day) * value;
 
        value+=p.second;
        day = event[i].first;
	}
    cout << res << endl;
 
    return 0;
}