naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #418 (Div. 2)

6/7 21:15-23:15 http://codeforces.com/contest/814

今回は配点がイレギュラー(CとDが1500/2000じゃなくて1750/1750)だけど、C→B→Aの順で。 問題が化物語

C. An impassioned circulation of affection (1750) x1642

http://codeforces.com/contest/814/problem/C なでこ&暦お兄ちゃん

色cと塗り回数mごとの最大長を先に全部求めたやつ pre[c][m] を用意して、クエリで参照 ・色cそれぞれについて(例えば ‘o') ・文字列(例えば “koyomi")で o 以外の文字の累積出現回数を数える → [ 0 1 1 2 2 3 4 ] ・塗り回数mそれぞれについて ・開始位置 s を選び(0≦ s<N-m)その開始位置における累積出現回数 + m でどこまで行けるか、累積出現回数表を upper_bound() で探索して見つけて、最遠位置を table[c][m] に記録 計算量O(MN2logN) // Mは色数 // N2logN: (m:[1..N]) x (開始位置:[0..N-m]) x (到達可能位置:log(N-m)) // 26 x 15002 x log(1500) ≒ 6.4e8 クエリO(1) x Q = O(Q) // Q=200000

自前で用意した最悪ケース(N=1500,Q=200000)がローカルで1.48秒 多分行けるっしょ… →AC (0:48; 1414pts)

agwたんとの反省会(ビデオチャット)で、agwたんの解法が O(MN2) で、表を用意するのは一緒なんだけど、開始位置・終了位置の総当りで、文字'o'がその区間に何回出てる(これは累積表で求めてる)ってことはあと何文字埋めればその幅を満たせるかを求め、テーブルのその文字数の箇所を更新していく方式。総当りって言っても N(N-1)/2 ≒1e6だし、mを逐一選ばなくても、〈その文字数〉の最小がmだし、〈その幅〉の最大が最長文字列長になってる。

テーブルなんか作らずに尺取り法で(クエリ時に)やると O(QN) で、これでも間に合うみたい。(200000x1500=3e8)
クエリ1回の計算量を O(1) ないし O(logN) に落としたい、と思って頑張ってたけど。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#include <cassert>

int main(){
    int n; cin >> n;
    string s; cin >> s;
    vector<vector<int>> pre(26, vector<int>(n+1, 0));
    rep(c, 26) { // x26
        vector<int> acc(1+n);
        acc[0] = 0;
        int diff = 0;
        char ch = 0x61 + c;
        rep(i, n) {
            if (s[i] != ch) ++diff;
            acc[1+i] = diff;
        }

        for (int m=1; m<=n; ++m) { // x26x1500
            int maxw = 0;
            for (int start=0; start<=n-m; ++start) { // x26x1500x1500
                int vStart = acc[start];
                int vEnd = vStart + m;
                int w = (int)(upper_bound(acc.begin()+start, acc.end(), vEnd) - (acc.begin()+start))-1;
                if (w > maxw) maxw = w;
            }
            pre[c][m] = maxw;
        }
    }

    int q;
    scanf("%d", &q);
    rep(i,q){
        int mi; char ci;
        scanf("%d %c", &mi, &ci);
        printf("%d\n", pre[ci-'a'][mi]);
    }
    return 0;
}

B. An express train to reveries (1000) x2264

http://codeforces.com/contest/814/problem/B 千石+ららちゃん

数列a, bで違っている箇所を拾い出す。 違うのは1箇所ないし2箇所。(問題文に1箇所以上違うと制約がある+3箇所以上違うとpからそれぞれ1つ違いという制約が満たせない) ・2箇所違いの場合:aとbが共通の部分についてはそのまま使う。違ってる箇所について、(a[場所1], b[場所2]) ないし (b[場所1], a[場所2]) で辻褄のあう方を採用する。(p が1..N のpermutationになるような方。ab共通部分ですでにN-2個の数字を使っているので、使える数字は残り2個のはず。採用できるのはこの2個の数字のpermutationのみ) ・1箇所違いの場合:aとbが共通の部分についてはそのまま使う。違ってる箇所について、使われていないはずの数字(1つ)をそこに埋める。 →AC (1:10, 720pts)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define rep1(var,n)  for(int var=1;var<=(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#include <cassert>

int main(){
    int n; cin >> n; //
    assert(2<=n && n<=1000);
    vector<int> a(n), b(n);
    rep(i,n) { cin >> a[i]; a[i]--; }
    rep(i,n) { cin >> b[i]; b[i]--; }

    vector<int> diff_at;
    rep(i,n) {
        if (a[i] != b[i]) diff_at.push_back(i);
    }
    int D = diff_at.size();
    assert(D == 1 || D == 2);

    vector<bool> used(n, false);
    int used_cnt = 0;

    vector<int> p(all(a));

    if (D == 2) {
        int u = diff_at[0], v = diff_at[1];

        rep(i,n) {
            if (i == u || i == v) continue;
            used[a[i]] = true;
            ++used_cnt;
        }
        assert(used_cnt == n-2);
        set<int> unused;
        rep(i,n){
            if (!used[i]) { unused.insert(i); }
        }
        assert(unused.size() == 2);

        if (a[u] != b[v] && found(unused,a[u]) && found(unused,b[v])) {
            // a[u], b[v]
            p[u] = a[u]; p[v] = b[v];
        }
        else if (b[u] != a[v] && found(unused,b[u]) && found(unused,a[v])) {
            // b[u], a[v]
            p[u] = b[u]; p[v] = a[v];
        }
        else {
            assert(false);
        }
    } else if (D == 1) {
        int u = diff_at[0];

        rep(i,n) {
            if (i == u) continue;
            used[a[i]] = true;
            ++used_cnt;
        }
        assert(used_cnt == n-1);
        int unused = -1;
        rep(i,n){
            if (!used[i]) { unused = i; break; }
        }
        p[u] = unused;
    }

    rep(i, n) {
        if (i>0) putchar(' ');
        printf("%d", 1+p[i]);
    }
    putchar('\n');

    return 0;
}

A. An abandoned sentiment from past (500) x3844

http://codeforces.com/contest/814/problem/A ひたぎ+貝木

貝木数列を降順ソートしたものをひたぎ空欄に左から埋めていって、出来た数列が昇順になっているか見るだけ →AC (1:20, 340pts)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define rep1(var,n)  for(int var=1;var<=(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#include <cassert>

int main(){
    int n, k; cin >> n >> k;

    vector<int> a(n), b(k);
    rep(i,n) { cin >> a[i]; }
    rep(i,k) { cin >> b[i]; }
    bool yn = false;
    sort(all(b), greater<int>());

    for (int i=0,j=0; i<n; ++i) {
        if (a[i] == 0) a[i] = b[j++];
    }
    rep(i, n-1) {
        if (a[i] > a[i+1]) { yn = true; break; }
    }

    printf("%s\n", yn ? "Yes" : "No");
    return 0;
}

D. An overnight dance in discotheque (1750) x590

http://codeforces.com/contest/814/problem/D 月火(白金ディスコ

とりあえず、各円の包含関係を求めて レイヤーの奇数番目偶数番目を交互に分配していけばいい?と思ったけど、サンプルケース1はそれで行けるけど2はダメ どっちの組に入れるか(その円をプラスに使うかマイナスに使うか=奇数レイヤーにするか偶数レイヤーにするか)ってDPで行ける? って辺りまで考えて終わり

以下嘘解法(サンプルケース1しか通らないやつ)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define rep1(var,n)  for(int var=1;var<=(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#include <cassert>

int main(){
    int n; cin >> n;
    assert(1<=n && n<=1000);

    vector<vector<int>> circles(n);
    rep(i,n){
        int x,y,r; cin >>x>>y>>r;
        circles[i] = {x,y,r};
    }

    vector<int> lev(n, 0);

    repC2(i,j,n){
        double d = hypot(circles[i][0]-circles[j][0], circles[i][1]-circles[j][1]);
        int rsum = circles[i][2] + circles[j][2];
        if (rsum < d + 1e-9) {
            // 別々
            printf("%d | %d\n", i, j);
        }
        else if (circles[i][2] > circles[j][2]) {
            // j in i
            printf("%d in %d\n", j, i);
            lev[j]++;
        } else {
            // i in j
            printf("%d in %d\n", i, j);
            lev[i]++;
        }
    }

    cout << lev << endl;
    long double S = 0, pi = 3.141592653589793238462643383;
    rep(i, n) {
        int h = lev[i]/2;
        printf("layer %d is alive\n", i);
        int r = circles[i][2];
        long double s = pi*r*r;
        if (h % 2 == 0) {
            S += s;
        } else {
            S -= s;
        }
    }
    printf("%.8Lf\n", S);

    return 0;
}

E. An unavoidable detour for home x52

開いてない

System Test

all passed (ABC)

rating: 1633 → 1676 (+40)