algoNote

プログラミング関連

CSA精進記録2

引き続き解いていきます。

Jeans and Shirts

https://csacademy.com/contest/archive/task/jeans-and-shirts/

色ごとの個数を配列に入れておいて,例えばジーンズの色を固定する(cとする)と,シャツの方は[1,c-K],[c+K,1000]の範囲から選ぶことが出来るので累積和をとっておけば求まります。 と思ったんですが,制約的にO(K2)が間に合うので本当にやるだけでした。(制約を読みましょう)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> jeans(1001, 0), shirt(1001, 0);
    REP(i, N) {
        int c;
        cin >> c;
        jeans[c]++;
    }
    REP(i, M) {
        int c;
        cin >> c;
        shirt[c]++;
    }
    REP(i, 1000) shirt[i + 1] += shirt[i];
    
    int ans = 0;
    REP(c, 1001) {
        int l = c - K;
        int r = c + K - 1;
        int sum = 0;
        if (c + K <= 1000) sum += shirt[1000] - shirt[r];
        if (l >= 0) sum += shirt[l];
        ans += jeans[c] * sum;
    }
    cout << ans << endl;
    return 0;
}

Connect the Graph

https://csacademy.com/contest/archive/task/connect-the-graph/

操作の前後でグラフ上の辺の本数は変わりません。よって操作を繰り返して連結にするためには少くともN-1本の辺が必要です。 逆にN-1本以上ある場合,操作を繰り返すことで連結にすることが出来ます。

まず,最小全域木を求めるクラスカル法の要領で不要な辺を列挙しておきます。 最終的なグラフは連結であれば何でもよいので,ある頂点から1番の頂点への辺を追加することにします。 不要な辺を列挙するときに作ったUnionFind森があるので,これを使って1番の頂点と別の連結成分に属する頂点を探します。 その頂点から1への辺を加えます。このときに不要な辺を1つ取り出してペアにします。
これを繰り返すことで最小な操作を求めることが出来ます。

提出コードを表示

using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct DisjointSet {
    vector<int> data;
    DisjointSet(int n) : data(n, -1) {}
    int root(int x) {
        return data[x] < 0 ? x : (data[x] = root(data[x]));
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x != y) {
            if (size(x) > size(y)) swap(x, y);
            data[y] += data[x];
            data[x] = y;
        }
    }
};
signed main() {
    int n, m;
    cin >> n >> m;
    if (m < n - 1) {
        cout << -1 << endl;
        return 0;
    }
    DisjointSet uf(n);
    queue<vector<int>> e;
    REP(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (uf.same(a, b)) e.push({a, b});
        else uf.unite(a, b);
    }
    
    vector<vector<int>> ans;
    REP(i, n) {
        if (uf.same(0, i)) continue;
        uf.unite(i, 0);
        auto tmp = e.front(); e.pop();
        ans.push_back({tmp[0] + 1, tmp[1] + 1, i + 1, 1});
    }
    
    cout << SZ(ans) << endl;
    REP(i, SZ(ans)) {
        cout << ans[i] << endl;
    }
    return 0;
}

Football Tournament

https://csacademy.com/contest/archive/task/football-tournament/

やるだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<vi> a(n, vi(n));
    cin >> a;
    int mx = 0;
    int ans = 0;
    REP(i, n) {
        int c = 0;
        REP(j, n) if (a[i][j] == 1) c++;
        REP(j, n) if (a[j][i] == 2) c++;
        chmax(mx, c) && (ans = i + 1);
    }
    cout << ans << endl;
    return 0;
}

Strictly Increasing Array

https://csacademy.com/contest/archive/task/strictly-increasing-array/statement/

editorial見ました。十分性については納得しましたが、これが最小になるの?という感じです。

hamayanhamayanさんの解説が参考になりました。 hamayanhamayan.hatenablog.jp

狭義単調増加列になるためには、V[i] + (j - i) <= V[j]がすべてのi<jについて成り立つ必要があります。 これはV'[i] = V[i] - iという変換後の列V'が非減少列であることと同値なので、 V'を非減少列にするために必要な操作回数がもとの問題の答えに一致します。

ある列を非減少列にするために必要な操作回数は簡単で、まず、最長非減少列の長さを求めて、全体の長さ(N)から引いた値です。 最長非減少列以外の値を左右の値に適当に合わせればよいからです。 最長非減少列を求めるのはLISの要領で出来ます。(提出コードで使ったのは蟻本のLISのコードを変えたものです。)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

int LNDS(vector<int> a) {
    int n = SZ(a);
    vector<int> dp(n, INF);
    REP(i, n) {
        *upper_bound(ALL(dp), a[i]) = a[i];
    }
    return lower_bound(ALL(dp), INF) - begin(dp);
}
signed main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    
    REP(i, n) a[i] -= i;
    cout << n - LNDS(a) << endl;
    return 0;
}

Right Triangles

https://csacademy.com/contest/archive/task/right-triangles/

点(X,Y)のright triangleの中に含まれる点は、「偏角が(X,Y)よりも小さく、x座標がXより小さい」という条件を満たす点です。 よって、偏角でソートした順に処理を行います。今までに処理した点のX座標が1、それ以外が0になっている配列を考えると、点(X,Y)の答えは配列の[0,X]の和です。 これはBITを使ってO(log N)で求まるので、全体でO(N log N)で解けます。

105だしlong doubleで傾きを持っても大丈夫だろうと思って書いたら通りましたが、座標が整数なので整数のまま計算するべきですね。(editorialのコードでは比較関数を定義して整数で比較しています。)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct BIT {
    vi d;
    int n;
    BIT(int s) : n(s), d(s, 0) {}
    void add(int i, int x) {
        while (i < n) {
            d[i] += x;
            i += i & -i;
        }
    }
    int sum(int i) {
        int ret = 0;
        while (i > 0) {
            ret += d[i];
            i -= i & -i;
        }
        return ret;
    }
};
signed main() {
    int n;
    cin >> n;
    using myp = pair<long double, vi>;
    vector<myp> p(n);
    REP(i, n) {
        int x, y;
        cin >> x >> y;
        long double arg = y / (long double)x;
        p[i] = {arg, {x, i}};
    }
    sort(ALL(p));
    
    BIT bit(100005);
    vector<int> ans(n);
    REP(i, n) {
        int x = p[i].second[0];
        int idx = p[i].second[1];
        int cnt = bit.sum(x);
        ans[idx] = cnt;
        bit.add(x, 1);
    }
    
    REP(i, n) cout << ans[i] << endl;
    return 0;
}

Squarish Rectangle

https://csacademy.com/contest/archive/task/squarish-rectangle/

全探索します。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int H, W;
    cin >> H >> W;
    int A = H * W;
    int ans = INF;
    REPF(i, 1, 1000006)
        if (A % i == 0) chmin(ans, abs(i - A / i));
    cout << ans << endl;
    return 0;
}

Spring Cleaning

https://csacademy.com/contest/archive/task/sprint-cleaning/

出来上がるグラフは、いくつかの連結成分から成りますが、それぞれの連結成分は、1つのサイクルか、 サイクルの頂点に木(葉から根の向きに辺がある)がくっついたようなグラフになります。(functional graphというらしい?) サイクルの場合は、1つの頂点だけ残してそれ以外は消すことが出来ます。functional graphの場合はくっついている木の葉の部分以外の頂点を全て消すことが出来ます。 よって、頂点の入次数をカウントして、小さい順にDFSを行なえばよいことが分かります。

適当にDFSするだけなんですが、結構時間が掛かってしまいました。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const ll INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vi p(n);
    vector<vi> deg(n, vi(2, 0));
    REP(i, n) {
        cin >> p[i];
        p[i]--;
        deg[p[i]][0]++;
        deg[i][1] = i;
    }
    sort(ALL(deg));
    
    vector<vi> ans;
    vector<bool> used(n, false);
    REP(k, n) {
        int i = deg[k][1];
        if (used[i]) continue;
        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            int w = p[v];
            if (!used[w]) {
                dfs(w);
                ans.push_back({v + 1, p[v] + 1});
            }
        };
        dfs(i);
    }
    
    REP(i, SZ(ans)) cout << ans[i] << endl;
    return 0;
}

Numbers Tournament

https://csacademy.com/contest/archive/task/numbers-tournament/

やるだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    REP(i, n) {
        cin >> a[i];
        sort(ALL(a[i]));
    }
    
    vector<array<int, 2>> score(n);
    REP(i, n) {
        score[i][1] = i;
        REPF(j, i+1, n) {
            vi common;
            REP(k, n) {
                if (find(ALL(a[j]), a[i][k]) != end(a[j]))
                    common.push_back(a[i][k]);
            }
            sort(ALL(common));
            
            if (common.empty()) {
                score[i][0]--, score[j][0]--;
                continue;
            }
            
            int c1 = 0, c2 = 0;
            REP(k, n) {
                if (a[i][k] < common.front() || common.back() < a[i][k]) c1++;
                if (a[j][k] < common.front() || common.back() < a[j][k]) c2++;
            }
            if (c1 == c2) score[i][0]--, score[j][0]--;
            else if (c1 > c2) score[i][0] -= 2;
            else score[j][0] -= 2;
        }
    }
    sort(ALL(score));
    
    REP(i, n) cout << score[i][1] + 1 << endl;
    return 0;
}

Max Or Subarray

https://csacademy.com/contest/archive/task/max-or-subarray/

ORの最大値は自明に列全てを取ったときの値です。整数の集合に対してすべてのORを取った結果は、あるビットについて、立っているビットが1つ以上存在すれば1、そうでなければ0という数になります。 よって、列を左から見ていったときに、各ビット毎にそこまでに現れた1の個数をカウントしておいて(累積和などで)、カウントを整数に直した値が初めに求めたmaxに一致する範囲でしゃくとり法を行えばよいです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    
    if (*max_element(ALL(a)) == *min_element(ALL(a))) {
        cout << 1 << endl;
        return 0;
    }
    
    int mx_or = 0;
    FORE(x, a) mx_or |= x;
    
    using bit = array<int, 31>;
    vector<bit> sum(n);
    REP(i, n) REP(j, 31) sum[i][j] = (a[i] >> j) & 1;
    REP(i, n - 1) REP(j, 31) sum[i+1][j] += sum[i][j];
    
    auto check = [&](bit&& b) {
        int r = 0;
        REP(j, 31) if (b[j]) r |= (1 << j);
        return mx_or == (r & mx_or);
    };
    auto sub = [](bit a, bit& b) {
        REP(j, 31) a[j] -= b[j];
        return a;
    };
    
    int r = 0;
    bit tmp;
    int ans = INF;
    REP(l, n) {
        while (r < n && !check(sub(sum[r], tmp))) {
            r++;
        }
        if (r < n) chmin(ans, r - l + 1);
        tmp = sum[l];
    }
    cout << ans << endl;
    return 0;
}

Count Squares

https://csacademy.com/contest/archive/task/count-squares/

軸に平行な正方形の個数は簡単に求まります。一辺の幅がxの正方形の個数をf(x)とするとf(x) = (N - x + 1) × (M - x + 1)です。

傾いている正方形の個数を考えます。次の図のように、赤い点の左側に出来る直角三角形の横をx縦をyとします。すると三角形の相似から、正方形を囲む軸に平行な正方形の一辺の幅はx + yと表せます。 選んだ4点のうちy座標の最大値はM以下である必要があり、x座標の最大はN以下である必要があるわけなので、結局この傾き方の正方形の個数は一辺x + yの正方形の個数に一致するはずです。 f(x)はO(1)ですが、(x, y)を全て試そうとするとO(min(N, M)2)かかり通りません。

そこでx + yの値それぞれについていくつあるかを考えます。s = x + yとするとこれを満たす(x, y)の組はs + 1通りありますが、(0, s)と(s, 0)は同じ正方形を表すので、これは取り除きます。よって、s = x + yとなる(x, y)はs通りあります。 従って答えは\sum_{s \leq \min(N, M)} s \cdot f(s)のMODを取ったものです。

f:id:algon_320:20180716191830p:plain

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M;
    cin >> N >> M;
    int mn = min(N, M);
    auto f = [&](int x) { return (N - x + 1) * (M - x + 1); };
    int ans = 0;
    const int MOD = 1000000007;
    REPF(x, 1, mn + 1) {
        ans += x * f(x) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

K Inversions

https://csacademy.com/contest/archive/task/k-inversions/

1...nまでが順に並んだ順列の要素をスワップしていくことで転倒数Kの列を構成します。 まず、辞書順最小の転倒数Kの列を作りたいわけなので、列の後ろの方をスワップして転倒数Kを実現するべきです。 末尾i文字の位置を変えることで出来る最大の転倒数はi * (i - 1) / 2(末尾i文字が逆順になる状態)なので、 これを使えば末尾から何文字の位置を変える必要があるかを求めることが出来ます。提出コードではO(N)かけて求めています。

転倒数Kを作るために末尾m文字の変更が必要だったとします。末尾m - 1文字で出来る最大の転倒数はm * (m - 1) / 2でした。これをTとおいておきます。 転倒数Tの状態からスワップを繰り返し、転倒数Kまで変化させることを考えます。

以下、簡単のために末尾m文字の小さい方から順に1~mを振り直した列で説明します。
初めの状態は、{1, m, (m-1), ... , 3, 2}です。この状態から辞書順最小になるように転倒数を1増やすにはどうしたらよいでしょうか。
左端が1になる列は転倒数Tが最大なので、これ以上大きく出来ません。
2と1を交換して左端が2になっている列を考えます。{2, m, (m-1), ... , 3, 1}という状態です。この転倒数はT+1になっていることが分かります。
(T - (交換前の2の左側の3以上の数の個数) + (交換後の1の左側の2以上の数の個数) = T - (m - 2) + (m - 1) = T + 1)
実はこれが辞書順最小になっていることが示せます。が、書くのが疲れてきたので読者への課題とします。(オイ) T+1→T+2の操作は2と3をスワップします。{3, m, (m-1), ... , 4, 2, 1}という状態になります。以下同様に先頭の値と先頭の値+1を交換します。 これをKになるまで繰り返すことで答えが得られます。この交換は高々m回しか起こらないので、全体でO(N)で求まります。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    REPF(i, 1, N + 2) {
        if (i * (i - 1) / 2 > K) {
            K -= (i - 1) * (i - 2) / 2;
            vector<int> ans(N);
            REP(j, N) ans[j] = j + 1;
            int tmp = N;
            REPF(j, N - i + 1, N) ans[j] = tmp--;
            REP(j, K) swap(ans[N - j - 1], ans[N - i]);
            cout << ans << endl;
            break;
        }
    }
    return 0;
}

Flip the Matrix

https://csacademy.com/contest/archive/task/flip-the-matrix/

やるだけ。実際に調べればいいです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<vi> a(n, vi(n)), b(n, vi(n));
    cin >> a >> b;
    
    bool same = true;
    REP(i, n) REP(j, n) if (a[n-i-1][j] != b[i][j]) same = false;
    if (same) { cout << 1 << endl; return 0; }
    same = true;
    REP(i, n) REP(j, n) if (a[i][n-j-1] != b[i][j]) same = false;
    if (same) { cout << 1 << endl; return 0; }
    cout << 0 << endl;
    return 0;
}

X Distance

https://csacademy.com/contest/archive/task/x-distance/

ペア(a, b)の最小コストは、aからbへのパスのコストのうち最小のものです。パスのコストはパスに含まれる辺のうち最大の重みです。 これを言い換えると最小コストXのペア(a, b)について、ab間のパスのうちコストがXより小さいものは存在しません。つまりコストX以上のパスしか存在しない状態です。 このとき、重みXの辺をすべて取り除いたとすると、(a, b)の最小コストはXより大きくなります。さらに言うと、重みX以上の辺をすべて取り除いたとするとab間にパスが存在しなくなります。

このことから

  • 重みX以上の辺をすべて取り除いたグラフでab間にパスが存在するならば、(a, b)の最小コストはX未満
  • 重みX+1以上辺をすべて取り除いたグラフでab間にパスが存在するならば、(a, b)の最小コストはX+1未満

ということが言えます。従って「重みX以上の辺をすべて取り除いたグラフ上にab間のパスが存在するような(a, b)の組の数」をS、 「重みX+1以上の辺をすべて取り除いたグラフ上にab間のパスが存在するような(a, b)の組の数」をTとおくと、この問題の答えはT - Sとなります。

パスが存在するような組の数は各連結成分の個数を a_iとすると \sum {}_{a_i}C_2 = \sum \frac{1}{2} a_i (a_i - 1)なので、連結成分の頂点数をDFSで数えることでO(N)で求めることが出来ます。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<vi> g(N);
    vector<vi> e;
    REP(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c > X) continue;
        a--, b--;
        if (c == X) {
            e.push_back({a, b});
            continue;
        }
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    auto count_num_pair = [](vector<vi>& g) {
        int N = SZ(g);
        vector<bool> vis(N, false);
        int ret = 0;
        REP(i, N) {
            if (vis[i]) continue;
            int comp = 0;
            function<void(int)> dfs = [&](int v) {
                vis[v] = true;
                comp++;
                FORE(w, g[v]) {
                    if (vis[w]) continue;
                    dfs(w);
                }
            };
            dfs(i);
            ret += comp * (comp - 1) / 2;
        }
        return ret;
    };
    
    int s = count_num_pair(g);
    FORE(edge, e) {
        g[edge[0]].push_back(edge[1]);
        g[edge[1]].push_back(edge[0]);
    }
    int t = count_num_pair(g);
    cout << t - s << endl;
    return 0;
}

Set Subtraction

https://csacademy.com/contest/archive/task/set-subtraction/

Xになり得るのは、Aの2要素の差なので、これをすべて試します。Xが正であるという制約より、減算した後の値は元の値よりも小さくなります。 よって、列をソートして小さい順にA[i]+Xが存在するかを確認し、存在する場合はその要素を削除するという操作をN回繰り返します。存在しない要素があるならXを選び直します。削除した要素の値が答えの集合となります。

multisetを使って実装しました。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vi A(N * 2);
    cin >> A;
    sort(ALL(A));
    REPF(i, 1, N * 2) {
        int X = A[i] - A[0];
        if (X <= 0) continue;
        
        bool ok = true;
        vi ans;
        multiset<int> ms(ALL(A));
        REP(j, N) {
            int t = *begin(ms);
            auto itr = ms.find(t + X);
            if (itr == end(ms)) {
                ok = false;
                continue;
            }
            ans.push_back(*itr);
            ms.erase(itr);
            ms.erase(begin(ms));
        }
        if (ok) {
            cout << X << endl;
            cout << ans << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Independent Rectangles

https://csacademy.com/contest/archive/task/independent-rectangles/

(-w, h)を昇順にソートした順に見ていきます。既に見た部分にhより大きい物が無い場合にカウントします。

思考停止でBITを書きに行ってしまいましたが、setでいいじゃんとなり、最終的にmaxの値を持っておくだけでいいじゃんとなりました(ア)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vector<vi> boxes(N, vi(2));
    REP(i, N) {
        int w, h;
        cin >> w >> h;
        boxes[i] = {-w, h};
    }
    sort(ALL(boxes));
    
    int ans = 0;
    int mx = 0;
    REP(i, N) {
        if (mx <= boxes[i][1]) ans++;
        chmax(mx, boxes[i][1]);
    }
    cout << ans << endl;
    return 0;
}

Huge Matrix

https://csacademy.com/contest/archive/task/huge-matrix/

imos法でやります。0に注意。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M;
    cin >> N >> M;
    vector<vi> s(10, vi(M + 1, 0));
    REP(i, N) {
        int l, r, a;
        cin >> l >> r >> a;
        l--, r--, a--;
        s[a][l]++;
        s[a][r+1]--;
    }
    REP(i, 10) REP(j, M) s[i][j + 1] += s[i][j];
    int ans = 0;
    REP(i, M) {
        int cnt = 0;
        int sum = 0;
        REP(j, 10) {
            if (s[j][i] > 0) cnt++;
            sum += s[j][i];
        }
        if (sum < N) cnt++;
        chmax(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Consecutive Subsequence

https://csacademy.com/contest/archive/task/consecutive-subsequence/

RMQでLISのDPをやるときの要領でやるのですが、そこまでに足りない値を使ったか使っていないかという状態も持たせます。

  • dp[x][0] := 左から見ていって値xを見ているとき足りない値を使っていない状態で最長でいくつ連続しているか
  • dp[x][1] := 左から見ていって値xを見ているとき足りない値を使っている状態で最長でいくつ連続しているか

と定義します。遷移は

  • dp[x][0] = max(dp[x][0], dp[x-1][0] + 1);
  • dp[x][1] = max(dp[x][1], dp[x-1][1] + 1);
  • dp[x][1] = max(dp[x][1], dp[x-2][0] + 2);

で、答えはmax{max(dp[x][0] + 1, dp[x][1])}です。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<array<int, 2>> dp(1000006, {0, 0});
    REP(i, n) {
        int a;
        cin >> a;
        chmax(dp[a + 2][0], dp[a - 1 + 2][0] + 1);
        chmax(dp[a + 2][1], dp[a - 1 + 2][1] + 1);
        chmax(dp[a + 2][1], dp[a - 2 + 2][0] + 2);
    }
    int ans = 0;
    REP(i, 1000006) chmax(ans, max(dp[i][0] + 1, dp[i][1]));
    cout << ans << endl;
    return 0;
}

Manhattan Distances

https://csacademy.com/contest/archive/task/manhattan-distances/

解説見ました。Standingsを見たら結構解かれていて悲しくなりました。典型問題なんでしょうか。

まず、整数座標なので3点のうちの異なる2点間のマンハッタン距離の和は必ず偶数になります。

f:id:algon_320:20180730225851p:plain

よって和が奇数ならNGです。偶数のときは、(0, 0), (0, a), (c - (a + c - b) / 2, (a + c - b) / 2)などとすればいいです。(どれか一辺を軸と平行に取るようにおいて連立方程式を解くと出ます。)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int T;
    cin >> T;
    while (T--) {
        vi dist(3);
        cin >> dist;
        sort(ALL(dist));
        int a = dist[0], b = dist[1], c = dist[2];
        if (a + b < c || (a + b + c) % 2 == 1) {
            printf("-1\n");
            continue;
        }
        int y = (a + c - b) / 2;
        int x = c - y;
        printf("0 0 0 %lld %lld %lld\n", a, x, y);
    }
    return 0;
}

Previous Divisors

https://csacademy.com/contest/archive/task/previous-divisors/

やるだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define pb push_back
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        //#define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> a;
    REP(i, n) {
        int x;
        cin >> x;
        int ans = 0;
        FORE(y, a) {
            if ((y != 0 && x % y == 0) || x == 0)
                ans++;
        }
        cout << ans << endl;
        a.pb(x);
    }
    return 0;
}

Best Array Cut

https://csacademy.com/contest/archive/task/best-array-cut/

累積和で全探索するだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    vi s(n);
    s[0] = a[0];
    REP(i, n - 1) s[i + 1] += s[i] + a[i + 1];
    int ans = INF;
    REP(i, n - 1) {
        int a = s[n - 1] - s[i];
        int b = s[i];
        chmin(ans, abs(a - b));
    }
    cout << ans << endl;
    return 0;
}

Alphabet Rotation

https://csacademy.com/contest/archive/task/alphabet-rotation/

差分を比較してカウントします。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

vector<int> get_diff(string& s) {
    vector<int> ret;
    int n = SZ(s);
    REP(i, n - 1) ret.push_back((s[i + 1] - s[i] + 26) % 26);
    return ret;
}
signed main() {
    int n;
    cin >> n;
    map<vi, int> cnt;
    vector<string> str(n);
    vector<vi> diff(n);
    REP(i, n) {
        cin >> str[i];
        diff[i] = get_diff(str[i]);
        cnt[diff[i]]++;
    }
    REP(i, n) {
        cnt[diff[i]]--;
        if (cnt[diff[i]] > 0) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
        cnt[diff[i]]++;
    }
    return 0;
}

Final Index

https://csacademy.com/contest/archive/task/final-index/

シミュレーションするだけですね。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
#define pb push_back
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M, K;
    cin >> N >> M >> K;
    int idx = K - 1;
    REP(i, M) {
        int ps, l;
        cin >> ps >> l;
        if (ps == 1 && N - l <= idx) {
            int t = idx - (N - l);
            idx = (N - 1) - t;
        } else if (ps == 0 && idx <= l - 1) {
            idx = (l - 1) - idx;
        }
    }
    cout << idx + 1 << endl;
    return 0;
}

Constant Sum

https://csacademy.com/contest/archive/task/constant-sum/

思考停止BITをやろうとしてバグらせました。一様に引かれた分を別に持っておいて、printクエリのときに引けばいいです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
#define pb push_back
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, Q;
    cin >> N >> Q;
    vector<long double> A(N);
    cin >> A;
    long double sum = 0;
    REP(i, Q) {
        int com;
        cin >> com;
        if (com == 0) {
            int idx, s;
            cin >> idx >> s;
            idx--;
            sum += s / (long double)(N - 1);
            A[idx] += s + s / (long double)(N - 1);
        } else {
            int idx;
            cin >> idx;
            idx--;
            cout << A[idx] - sum << endl;
        }
    }
}

Balanced Min Pairing

https://csacademy.com/contest/archive/task/balanced-min-pairing/

それぞれの配列からmininumになる値(代表と呼ぶことにする)をN/2個ずつ取り出すわけですが、小さい方からN/2個取るべきです。よってソートして先頭N/2個を代表にして、残った要素は小さい方から反対側の配列の代表とペアにしていきます。このときに条件を満たさない場合は解なしです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
#define pb push_back
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int T;
    cin >> T;
    REP(t, T) {
        int N;
        cin >> N;
        vector<pii> a(N), b(N);
        REP(i, N) {
            int x;
            cin >> x;
            a[i] = {x, i};
        }
        REP(i, N) {
            int x;
            cin >> x;
            b[i] = {x, i};
        }
        sort(ALL(a)), sort(ALL(b));

        vector<int> ans(N);
        bool ng = false;
        REP(i, N / 2) {
            if (a[i].first >= b[N / 2 + i].first) {
                ng = true;
                break;
            }
            ans[a[i].second] = b[N / 2 + i].second + 1;
        }
        if (ng) {
            cout << -1 << endl;
            continue;
        }
        REP(i, N / 2) {
            if (a[N / 2 + i].first <= b[i].first) {
                ng = true;
                break;
            }
            ans[a[N / 2 + i].second] = b[i].second + 1;
        }
        if (ng) {
            cout << -1 << endl;
            continue;
        }
        cout << ans << endl;
    }
}

Max Wave Array

https://csacademy.com/contest/archive/task/max-wave-array/

大きい順にソートして (位置) 1 3 2 5 4 ... となるようにすればいいです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
#define pb push_back
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    sort(RALL(a));
    REPF(i, 1, n - 1) {
        swap(a[i], a[i + 1]);
        i++;
    }
    cout << a << endl;
}


長くなったのでこのへんで切ります。

CSA精進記録

最近,CSAの過去問を埋めるのにハマっています。Solved数順に並べて500人以上くらいのところから始めました。(かなりやるだけ率が高いです。400人くらいから始めれば良かったかも) せっかくなので解いた記録を残しておこうと思います。

Array Removal

https://csacademy.com/contest/archive/task/array-removal/

列から要素を削除していき,繋がっている部分の値の和の最大値を毎回答える問題。

初め,残っている区間をpairで管理して,削除する毎に区間を2つに分けて追加して…みたいにやろうとしましたが,この方針では大変です。操作を逆に考えると,「全て削除された状態から要素を追加していくとき,連続した部分の和の最大値はいくらか」という問題になります。UnionFindを用いて,値を追加する毎に隣の値が存在するなら繋げるという操作を行なうことで連結を管理することが出来ます。UnionFindに値の和を持たせることで連結部分の和は求まります。和の最大値は単調増加するので適当に更新して終わりです。

提出コードを表示

struct DisjointSet {
    vector<int> par;
    vector<int> sum;
    DisjointSet(vi a) {
        int n = a.size();
        par.resize(n, -1);
        sum = a;
    }
    int root(int x) {
        return par[x] < 0 ? x : (par[x] = root(par[x]));
    }
    int size(int x) {
        return -par[root(x)];
    }
    int get_sum(int x) {
        return sum[root(x)];
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (size(x) > size(y)) swap(x, y);
            par[y] += par[x];
            par[x] = y;
            sum[y] += sum[x];
        }
    }
};

signed main() {
    int N;
    cin >> N;
    vi A(N), B(N);
    cin >> A >> B;
    reverse(ALL(B));
    
    DisjointSet s(A);
    vector<bool> v(N, false);
    vector<int> ans(N, 0);
    int mx = 0;
    REP(i, N) {
        int j = B[i] - 1;
        v[j] = true;
        if (j - 1 >= 0 && v[j - 1]) s.unite(j - 1, j);
        if (j + 1 <  N && v[j + 1]) s.unite(j, j + 1);
        chmax(mx, s.get_sum(j));
        ans[i] = mx;
    }
    
    reverse(ALL(ans));
    REP(i, N) cout << ans[i] << endl;
    return 0;
}

Karaoke Group

https://csacademy.com/contest/archive/task/karaoke-group/

友達を選ぶとき,全ての友達が共通して好きな曲の数を最大化したいので,選ぶ友達は少ない方が有利です。よって,最適は2人選ぶときなので,2重ループで全て調べれば終わりです。これは簡単でした。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M;
    cin >> N >> M;
    vector<set<int>> f(N);
    REP(i, N) {
        int l;
        cin >> l;
        REP(j, l) {
            int x;
            cin >> x;
            f[i].insert(x);
        }
    }
    int ans = 0;
    REP(i, N) {
        REP(j, N) {
            if (j == i) continue;
            int tmp = 0;
            REPF(k, 1, M + 1) if (CONTAIN(f[i], k) && CONTAIN(f[j], k)) tmp++;
            chmax(ans, tmp);
        }
    }
    cout << ans << endl;
    return 0;
}

Long Pressed Name

https://csacademy.com/contest/archive/task/long-pressed-name/

適当にやればOKですが,次のようにやりました。

  • uniqueをとった文字列が一致していなければ0
  • Bの部分列にAが現れるなら1
  • それ以外0

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    string A, B;
    cin >> A >> B;
    string a = A;
    string b = B;
    a.erase(unique(ALL(a)), end(a));
    b.erase(unique(ALL(b)), end(b));
    if (a != b) {
        cout << 0 << endl;
        return 0;
    }
    int i = 0;
    REP(j, SZ(B)) {
        if (B[j] == A[i]) {
            i++;
            if (i == SZ(A)) {
                cout << 1 << endl;
                return 0;
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

Bottle Recycling

https://csacademy.com/contest/archive/task/bottle-recycling/

毎回の操作でK分の1くらいの個数になるので,O(\log_{K} N)で実際にシミュレーション出来ます。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    int ans = N;
    while (N >= K) {
        ans += N / K;
        N = N / K + N % K;
    }
    cout << ans << endl;
    return 0;
}

Suspect Interval

https://csacademy.com/contest/archive/task/suspect-interval/

まず,列をソートしておきます。A[i]が含まれるような範囲のうち最大の長さのものは[A[i-1]+1, A[i+1]-1]なので,これを実装します。 値0と値100001を追加しておくと実装が楽になります。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vi A(N + 2);
    A[0] = 0; A[N + 1] = 100001;
    REP(i, N) cin >> A[i + 1];
    sort(ALL(A));
    N = SZ(A);
    
    int ans = 0;
    REPF(i, 1, N - 1) {
        int a = A[i - 1] + 1;
        int b = A[i + 1] - 1;
        chmax(ans, b - a + 1);
    }
    cout << ans << endl;
    return 0;
}

Triangle Count

https://csacademy.com/contest/archive/task/triangle-count/

やるだけです。全探索で三角形の成立条件を満たす組を探します。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    int ans = 0;
    REP(i, n) {
        REPF(j, i + 1, n) {
            REPF(k, j + 1, n) {
                vi e = {a[i], a[j], a[k]};
                sort(ALL(e));
                if (e[0] + e[1] > e[2]) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

ちょっと古いRoundの問題はsolved数が少くなる傾向があるのでやるだけ問題が結構ありますね…

Triangular Matrix

https://csacademy.com/contest/archive/task/triangular-matrix/

辞書順なので,なるべく小さい文字を取るように辿ればOKですが,prefixが同じで分岐するようなケースがあるのでうまくやる必要があります。 1段下がる毎に,最小の文字への遷移だけを残し残りは捨てるという処理を行なって,BFSっぽく進めていく方針で実装しました。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<string> s(n);
    cin >> s;
    
    string ans = "";
    queue<int> q;
    q.push(0);
    ans += s[0][0];
    REP(r, n - 1) {
        queue<pair<char, int>> q2;
        char mn = 'z' + 1;
        vector<bool> checked(n, false);
        while (!q.empty()) {
            int c = q.front(); q.pop();
            if (!checked[c]) q2.push({s[r + 1][c], c}), checked[c] = true;
            if (!checked[c + 1]) q2.push({s[r + 1][c + 1], c + 1}), checked[c + 1] = true;
            chmin(mn, min(s[r + 1][c], s[r + 1][c + 1]));
        }
        ans += mn;
        while (!q2.empty()) {
            char x = q2.front().first;
            int c = q2.front().second; q2.pop();
            if (mn == x) {
                q.push(c);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Numbers Game

https://csacademy.com/contest/archive/task/numbers-game/

やるだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<string> a(n);
    cin >> a;
    int ans = 0;
    REP(i, n - 1) {
        if (a[i][1] != a[i + 1][0]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Shifted Diagonal Sum

https://csacademy.com/contest/archive/task/shifted-diagonal-sum/

行列を縦横に好きなだけローテートするときの対角成分の和(トレース)の値の最大値を求める問題。 こういう問題は行列を拡大して出来る行列の部分行列を考えると見通しがよくなりますね。 具体的には与えられる行列を4倍に拡大(縦横2倍)した行列を考えて,この行列のNxNの部分行列を考えます。 あとは,NxN個ある部分行列のトレースの最大値を計算するだけですが,3重ループで書くとTLEしました。 斜めに累積和をとって,和の計算をO(1)にすると通ります。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<vector<int>> A(n * 2, vector<int>(n * 2));
    REP(i, n) {
        REP(j, n) {
            int x;
            cin >> x;
            A[i][j] = A[i + n][j] = A[i][j + n] = A[i + n][j + n] = x;
        }
    }
    
    REP(i, 2 * n - 1) {
        REP(j, 2 * n - 1) {
            A[i + 1][j + 1] += A[i][j];
        }
    }
    int ans = -INF;
    REP(i, n) {
        REP(j, n) {
            int s = A[i + n - 1][j + n - 1];
            if (i > 0 && j > 0) s -= A[i - 1][j - 1];
            chmax(ans, s);
        }
    }
    cout << ans << endl;
    return 0;
}

Two Guards

https://csacademy.com/contest/archive/task/two-guards/

やるだけ。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int A, B;
    cin >> A >> B;
    int ans = 0;
    REPF(i, A, B + 1) {
        if ((i - 1) % 2 != 0 && (i - 1) % 3 != 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Food Pairing

https://csacademy.com/contest/archive/task/food-pairing/statement/

全然分からなくて解説を見たら「Brute force it」と書いてあって,不可能でしょとなったのですが,問題文を誤読していました。 「2つ選んでそれぞれ独立な個数作って最大でいくつ作れるか」という問題だと思っていました。

ペアを決めたら同じ個数ずつ作るので,\displaystyle \max_{i,j} \min_k A_k / (D_{i,k} + D_{j,k})を愚直に計算するだけです。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    int m;
    cin >> m;
    vector<vector<int>> d(m, vector<int>(n));
    cin >> d;
    
    int ans = 0;
    REP(i, m) {
        REPF(j, i + 1, m) {
            int mn = INF;
            REP(k, n) {
                if (d[i][k] + d[j][k] == 0) continue;
                chmin(mn, a[k] / (d[i][k] + d[j][k]));
            }
            chmax(ans, mn);
        }
    }
    cout << ans << endl;
    return 0;
}

Find Edge List

https://csacademy.com/contest/archive/task/find-edge-list/statement/

やることは割とすぐに分かるのすが,実装が結構大変でした。

辺を追加する順番が重要で,隣接リスト内で辺同士が交差するような場合は-1です。 これは辺を頂点として見たグラフをトポロジカルソートすればいいことが分かります。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    int M = 0;
    map<pii, int> edge_id;
    map<int, pii> edge_inv;
    REP(i, N) {
        int l; cin >> l;
        REP(j, l) {
            int x;
            cin >> x;
            x--;
            g[i].push_back(x);
            if (i < x) {
                edge_id[{i, x}] = edge_id[{x, i}] = M;
                edge_inv[M] = {i, x};
                M++;
            }
        }
    }
    
    vector<vector<int>> eg(M);
    vector<int> deg(M, 0);
    REP(v, N) {
        REP(i, SZ(g[v]) - 1) {
            int w = g[v][i], nw = g[v][i + 1];
            eg[edge_id[{v, w}]].push_back(edge_id[{v, nw}]);
            deg[edge_id[{v, nw}]]++;
        }
    }
    stack<int> st;
    REP(i, M) if (deg[i] == 0) st.push(i);
    vector<int> tpsorted;
    while (!st.empty()) {
        int v = st.top(); st.pop();
        tpsorted.push_back(v);
        FORE(w, eg[v]) {
            deg[w]--;
            if (deg[w] == 0) st.push(w);
        }
    }
    if (SZ(tpsorted) != M) {
        cout << -1 << endl;
        return 0;
    }
    FORE(x, tpsorted) {
        auto e = edge_inv[x];
        cout << e.first + 1 << " " << e.second + 1 << endl;
    }
    return 0;
}

Dominoes

https://csacademy.com/contest/archive/task/dominoes/

範囲の左端を全探索して,右端を二分探索で求めます。区間の個数をsumとして,(sum + K >= len)ならOKという感じで二分探索します。sumは累積和を前計算しておくことでO(1)で求まります。

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    vector<int> s(1000006, 0);
    REP(i, N) {
        int x;
        cin >> x;
        s[x]++;
    }
    REPF(i, 1, 1000006) s[i] += s[i - 1];
    
    int ans = 0;
    REPF(l, 1, 1000001) {
        int ok = l, ng = 1000000;
        while (ng - ok > 1) {
            int r = (ok + ng) / 2;
            int len = r - l + 1;
            int sum = s[r] - s[l - 1];
            if (sum + K < len) {
                ng = r;
            } else {
                ok = r;
            }
        }
        chmax(ans, ok - l + 1);
    }
    cout << ans << endl;
    return 0;
}

Increasing Pair

https://csacademy.com/contest/archive/task/increasing-pair/

ぱっと見RMQのセグ木があれば終了という感じです。考えているとstackを使う解法を思いつきました。

editorial見ました。値が小さい順に見るだけで十分でしたね。(頭が悪い)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    stack<int> st;
    vector<int> b(n, INF);
    REP(i, n) {
        a[i]--;
        if (st.empty() || st.top() > a[i]) {
            st.push(a[i]);
            b[a[i]] = i;
        }
    }
    REPF(i, 1, n) chmin(b[i], b[i - 1]);
    
    int ans = 0;
    REP(i, n) {
        chmax(ans, i - b[a[i]]);
    }
    if (ans == 0) ans--;
    cout << ans << endl;
    return 0;
}

セグ木パンチ解

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

template<typename Monoid>
struct SegmentTree {
    using T = typename Monoid::T;
    size_t n;
    vector<T> t;

    void prop_to(std::size_t i) { t[i] = Monoid::op(t[i << 1], t[i << 1 | 1]); }
    SegmentTree(size_t size, const T& v = Monoid::identity()) {
        n = 1;
        while (n < size) n <<= 1;
        t.resize(n << 1, v);
    }
    template <class InputIt>
    SegmentTree(InputIt first, InputIt last) : n(distance(first, last)), t(n << 1, Monoid::identity()) {
        copy(first, last, begin(t) + n);
        for (size_t i = n; i > 0; i--) prop_to(i);
    }
    static T modify_update(const T& a, const T& b) { return b; }
    static T modify_add(const T& a, const T& b) { return a + b; }
    void update(size_t i, const T& v, const function<T(T, T)>& func = modify_update) {
        i += n;
        t[i] = func(t[i], v);
        while (i >>= 1) prop_to(i);
    }
    T query(size_t l, size_t r) {
        T res = Monoid::identity();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = Monoid::op(res, t[l++]);
            if (r & 1) res = Monoid::op(res, t[--r]);
        }
        return res;
    }
    T get(size_t i) { return t[i + n]; }
};

struct RMQ {
    using T = int;
    static T op(T a, T b) { return min(a, b); }
    static constexpr T identity() { return INF; }
};

signed main() {
    int n;
    cin >> n;
    SegmentTree<RMQ> seg(n);
    int ans = 0;
    REP(i, n) {
        int a;
        cin >> a;
        a--;
        chmax(ans, i - seg.query(0, a));
        seg.update(a, i);
    }
    if (ans == 0) ans--;
    cout << ans << endl;
    return 0;
}

Diesel Train

https://csacademy.com/contest/archive/task/diesel-train/statement/

電車の端がある地点xにあるときに移動する量をf(x)とすると,移動量の期待値EはE = \int f(x) \cdot \frac{1}{D}になります。(xが連続一様分布に従うので)

f:id:algon_320:20180712201845p:plain

f(x)は一次関数になるので,積分は三角形の面積で求まります。(実際には同じ大きさの直角二等辺三角形が2つなので正方形の面積) あとは全ての点の間について積分値を合計して最後にDで割れば答えです。

2ケースだけWAするのでどうしたものかと思いましたが,long doubleにしたら通りました。 (値自体が大きくなるから10^{-6}の誤差でも桁数が必要という感じですかね。)

提出コードを表示

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int D, N;
    long double L;
    cin >> D >> L >> N;
    
    vector<int> gas(N + 2);
    gas[0] = 0; gas[N + 1] = D;
    REP(i, N) cin >> gas[i + 1];
    sort(ALL(gas));
    N += 2;
    
    long double ans = 0;
    REPF(i, 1, N) {
        if (gas[i] - gas[i - 1] - L <= 0) continue;
        long double l = (gas[i] - gas[i - 1]) - L;
        ans += l * l / 4.0;
    }
    cout << ans / D << endl;
    return 0;
}


solved数400代まで来たので一旦ここまで。

みんなのプロコン 2018 C - 駆引取引

コンテスト終了間際にACする解法が思いついたのですが、コンテスト中に通すことが出来ませんでした。 無駄の多い解法(考察)ですが、考えたことを順に書いてみようと思います。

問題

C - 駆引取引

考えたこと

Nが18以下と小さいので商品の集合をビットで管理出来そうです。

まず答えを求めるために必要そうな情報を考えました。

  • 高橋君の所持金
  • 高橋君が持っている商品の一覧
  • 青木君が持っている商品の一覧

これくらいの情報があれば充分そうです。

高橋君が購入する操作を行なうとき、 「高橋君はK円持っている。青木君が持っている商品の集合をSとするとき、最大で得ることの出来る得点はいくらか。」 という問題を解ければよさそうです。

少し考えると、

  • 高橋君は商品を前から順に売っていくので、所持金は高々N通りしかない
  • これは累積和で前計算出来る
  • 高橋君が持っている商品の一覧は重要ではない

ということが分かります。よって、

  • 高橋君の所持金
  • 高橋君が持っている商品の一覧
  • 高橋君が何個の商品を売ったか
  • 青木君が持っている商品の一覧

が分かれば良さそうです。

また、高橋君の行える行動は「いくつの商品を売るか」を決めることで、 青木君の行動の自由は「各ターンどの商品を捨てるか」を決めることです。

さらに言うと高橋君の行える行動は「毎ターン(次の商品を売るか、青木君から商品を購入して取引を終了するか)」を決めること、なのですが僕はここまで詰められずに嘘解法に行ってしまいました...

ここで、嘘解法を書き始めます。

sum[i] := x[0]からx[i]までの和
ans = 0
S = (全ての商品)  // 青木君が持っている商品 

// 高橋君がi個売る場合 (所持金はsum[i]円)
repeat(i | 0 to N-1) {
    tmp = (無限大)  // 得点

    // 青木君が商品jを捨てる場合
    repeat(j | 0 to N-1) {
        if (Sにjが残っている場合) {
            (Sから商品jを捨てたと仮定)

            // 高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値を求める

            tmp2 = 0  // 得点
            foreach(k | Sの部分集合) {
                // 高橋君がkに属する商品をすべて購入する場合
                yen = 0  // kに属する商品全ての値段の合計
                val = 0  // kに属する商品全ての価値の合計
                repeat(l | 0 to N-1) {
                    if (l番目がkに含まれる場合) {
                        yen += y[l]
                        val += v[l]
                    }
                }
                if (y <= sum[i]) {
                    tmp2 = max(tmp2, val)  // 高橋君は得点が最大になるように購入する
                }
            }
            tmp = min(tmp, tmp2)

            (Sに商品jを戻す)
        }
    }

    (tmpが最小値をとる商品をSから捨てる)
    ans = max(ans, tmp)
}

ansを出力

まず、計算量が{O(N^3 \cdot 2^N)}なのでTLEしますね。(僕はこの嘘解法を高速化した時点でコンテストが終了してしまいました。) この嘘解法はサンプルの1から3までは通りますが、サンプル4で落ちます。 これは、「高橋君は得点を最大化するように動き、青木君は得点を最小化するように動く」に反しているためです。 青木君の動きに着目すると、次のターンで終了する場合しか考えられていません。

高速化について書きます。 高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値を求めるの部分を前計算しておければよさそうです。

  • 高橋君の所持金(N通り)
  • 青木君が残している商品(2^N通り)

なので、状態数は{O(N \cdot 2^N)}個です。

dp[i][S]:=高橋君の所持金がsum[i]円で青木君が残している商品がSのときの得点の最大値

というDPを考えます。Sはビットで管理します。このDPがスムーズに書けなくて悩みましたが、最終的に次のようにDPしました。

//////////////// これらを適当に前計算 O(N*2^N) ////////////////
yen[S] := Sに含まれる商品を全て購入するときに必要な金額
value[S] := S含まれる商品を全て購入するときに得られる価値(得点)
dp[i][j] := 0  // すべて0で初期化
////////////////////////////////////////////////////////////////

repeat (s | 0 to (2^N)-1) {
    repeat (i | 0 to N-1) {
        if (sum[i] >= yen[s]) {
            // 商品集合sを全て購入したときの得点
            dp[i][s] = max(dp[j][s], value[s])
        }
    }
}

// ビットDPの要領で、dp[i][s]の状態からsに含まれていない商品を追加した状態へ遷移する
// (これから追加する商品を買わなければよいので、少くともdp[i][s]得られる。)
repeat (s | 0 to (2^N)-1) {
    repeat (i | 0 to N-1) {
        if (sにiが含まれていないとき) {
            repeat(j | 0 to N-1) {
                dp[j][s|(1<<i)] = max(dp[j][s|(1<<i)], dp[j][s]) // 少くともdp[j][s]得られる
            }
        }
    }
}

これで高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値の部分を求めることが出来ました。

あとは「高橋君は得点を最大化するように動き、青木君は得点を最小化するように動く」の部分を修正すればOKです。 これはゲームの問題でよくあるDPを行うことで解決できます。といっても愚直に実装してメモ化するだけです。

// 高橋君が既にi個売った、p(0:青木君,1:高橋君)が操作を行なう、青木君が残している商品はS、の状態の得点(の最大)
int rec(int i, int p, int S) {
    if (i >= N) return 0;
    if (p == 1) {
        // 高橋君の操作
        int ret = 0;
        ret = max(ret, rec(i+1, p^1, S));  // 売却する
        ret = max(ret, dp[i][S]);  // 購入して終了
    } else {
        // 青木君の操作
        int ret = 無限大
        repeat (j | 0 to N-1) {
            if (Sのjビット目が1) {
                ret = min(ret, rec(i, p^1, S^(1<<j)));  // 商品jを捨てる
            }
        }
        return ret;
    }
}

これをメモ化すれば終了です。

配列に余裕をもたせていたらMLEしてしまいましたが、少し削ったらACしました。

コード

https://beta.atcoder.jp/contests/yahoo-procon2018-qual/submissions/2083300

Codeforces Round #448 (Div. 2) C - Square Subsets

コンテスト中にAC出来ませんでしたが、解けたので好きな問題です(オイ)

問題

codeforces.com

N 個の要素から成る数列 {a_i} が与えられます。
要素の積が k^{2} の形で表せるような部分集合の取り出し方は何通り存在しますか。109 + 7で割った余りを求めてください。

制約

  • {1 \leq N \leq 10^{5}}
  • {1 \leq a_i \leq 70}
続きを読む