AGC011_A Airport Bus

AtCoder 競技プログラミング
  • 方針
    やるだけなのにやけに時間がかかった。自分はアルゴリズム云々の前に、こういう基本的なプログラムの挙動に対する直感がかけているのかも？
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll n, c, k;
    cin >> n >> c >> k;
    vector<ll> t(n);
    for(int i=0;i<n;i++) cin >> t[i];
    sort(t.begin(), t.end());

    int j = 0, ans = 1;
    for(int i=0;i<n;i++) {
        if(t[i] > t[j] + k || i == j + c) {
            ans++;
            j = i;
        }
    }
    cout << ans << endl;
}

Codeforces #401 C. Alyona and Spreadsheet

  • 概要
    n ✕ mの整数テーブルが与えられる。加えて整数kとk個のl[i],r[i]が与えられる。 テーブルのうち、l[i]からr[i]が単調増加(a[i][j] <= a[i][j+1])ならYes, そうでなければNoを出力する。

  • 方針 a[i][j] <= a[i+1][j] かつi<n-1のとき dp[i] = dp[i+1] + 1 それ以外のとき dp[i] = 1 とする。 列ごとにdp[i]を作成し、ans[i] = max(ans[i], dp[i])とする。 l[i] - r[i] +1 <= ans[l[i]-1] のときYes, そうでないときNoを出力

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    ll a[n][m];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    vector<int> ans(n, 0);
    for(int i=0;i<m;i++) {
        vector<ll> v(n);
        for(int j=n-1;j>=0;j--) {
            if(j == n-1)
                v[j] = 1;
            else if(a[j][i] > a[j+1][i])
                v[j] = 1;
            else
                v[j] = v[j+1] + 1;
            ans[j] = max<ll>(ans[j], v[j]);
        }
    }

    int k;
    cin >> k;
    for(int i=0;i<k;i++) {
        int l, r;
        cin >> l >> r;
        if(ans[l-1] >= r - l + 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

AGC008B Contiguous Repainting

競技プログラミング AtCoder
  • 概要

N個の整数列が与えられる。連続するK(<=N)個を選び、全てを白で塗るか全てを黒で塗る（この操作は何回でもおこなうことができる）。色は上書きされる。 黒く塗られた整数の総和の最大値をもとめよ

  • 方針

操作順を逆に考える。

そのまま）何回かK個を塗る操作をおこなったあと、最後にK個を白or黒で塗る操作を行う。
逆）最後の操作で塗ったK個の色が確定させ、次の最後から二番目の操作で塗った色を確定させる。（色は上書きされない）　　

K区間以外は自由な色に確定させることが可能。のでKの区間を探索し、区間の和が>0なら黒、そうでなければ白とする。それ以外の区間はai > 0なら黒、そうでなければ白とする。

単純にやると計算量がO(N2)でアウト。そこで、単純な累積和(=ai)と、0より大きい要素のみの累積和(=bi)を予め求めておく。すると、Kの区間が決まると、K区間の和はaiを使ってO(1)、それ以外の区間の和もbiを使ってO(1)で求まる。よって計算量O(N)でいける。

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> v(n+1), a(n+1, 0), b(n+1, 0);
    for(int i=1;i<n+1;i++) cin >> v[i];
 
    for(int i=1;i<n+1;i++) {
        a[i] += v[i] + a[i-1];
    }
    for(int i=1;i<n+1;i++) {
        if(v[i] > 0)
            b[i] += v[i] + b[i-1];
        else
            b[i] = b[i-1];
    }
 
    ll ans = -1e15;
    for(int i=1;i <= n - k + 1;i++) {
        ll ans_i = 0;
        ll k_range_sum = a[i+k-1] - a[i-1];
 
        ans_i += max<ll>(k_range_sum, 0);
        ans_i += b[i-1];
        ans_i += (b[n] - b[i+k-1]);
        ans = max<ll>(ans, ans_i);
    }
 
    cout << ans << endl;
}