naoya_t@hatenablog

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

Codeforces Round #416 (Div. 2)

前回 (#415) に引き続いての出場(通算4回目)。
今日はC→B→Aの順で解く、と決めてスタート。

C. Vladik and Memorable Trip

Problem - C - Codeforces
・ある数字(目的地ID)が最初に現れる位置と最後に現れる位置が取れて、
・その町に行きたい客を全部含むグループがあるか、どのグループにも含まれないかで、
・XORして最大になるように、恣意的にある町行きの客を除外することもできて

うーん分からない
どうせDPか何かで解けるんだろ?という前提で、端から1つずつ考え始めた
(30分しても方針が立たなかったら諦めるつもりだったけど何とか。1問も通せてないまま時間が過ぎていくのは焦る。)

ある位置で前と後ろに分割する場合、その両方に含まれる数字(目的地ID)はどちらのグループにも入れ(ることができ)ない、という条件の元に、それぞれ独立に計算できる。

ある位置までの合計の最大値を配列に取ってDP(1次元)、か。

左から、その数字が初出の場合に限り、その数字で始まるグループを考える。その数字、またはそのグループに含まれる数字が全部現れ切る所まで。そのグループの開始以前に既に現れている数字が含まれていたらそのグループは成立しない。
そのグループが成立する場合、(グループ開始以前の最大スコア + グループメンバーの行き先のXOR値)でグループの終端の最大スコアを更新する。
成立しない場合、その数字は使わないものとして、単に1つ前の最大スコアを現在位置に持ち越して最大スコアを更新する。

最大ケース作ってローカルで試して問題なさそうだったので提出
→Runtime errorとな
ああ、a_i は 0-5000 の範囲を取るから vector<vector<int>>(n) じゃなくて vector<vector<int>>(5001) で確保しないとダメだ
そこだけ直して再提出→pretest passed(→AC) 0:54 -再提出△50pts; 1126pts

//(略)
using namespace std;
#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())

int main(){
    int n; cin >> n; // 1-5000
    vector<int> a(n);
    rep(i, n) cin >> a[i]; // 0-5000

    vector<vector<int> > u(5001);
    rep(i,n) {
        u[a[i]].pb(i);
    }

    vector<int> b(n+1, 0); // iで終わる最大
    for (int i=0; i<n; ++i) {
        int x = a[i];
        b[1+i] = max(b[1+i], b[i]);
        if (u[x][0] == i) {
            // first appearance
            int end = u[x].back();
            set<int> used;
            int ok = 1;
            for (int j=i; j<=end; ++j) {
                int y = a[j];
                if (found(used, y)) continue;
                used.insert(y);
                if (u[y][0] == j) {
                    int yend = u[y].back();
                    if (yend > end) end = yend;
                } else {
                    // can't use this
                    ok = 0; break;
                }
            }
            if (ok) {
                int sm = 0;
                tr(it, used) sm ^= (*it);
                b[1+end] = max(b[1+end], b[1+i-1] + sm);
            }
        } else {
            // ignore
        }
    }

    cout << b.back() << endl;
    return 0;
}

B. Vladik and Complicated Book

Problem - B - Codeforces
実際にソートしてたけど(ローカルで作った大型ケースは大丈夫だったけど)最悪ケースでTLEなのね…
→pretest passed(→TLE) 1:18, 688pts→0pt

//(略)
using namespace std;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

int main(){
    int n, m; cin >> n >> m; // 1-1e4
    vector<int> p(n);
    rep(i, n) { // 1e4
        cin >> p[i]; // 1-n
        --p[i];
    }
    rep(i, m) { // 1e4
        int l, r, x; cin >> l >> r >> x; // 1 <= l <= x <= r <= n
        --l; --r; --x;
        bool changed = false;

        vector<int> q(p.begin()+l, p.begin()+r+1);
        int last = q[x-l];
        sort(all(q));
        changed = (q[x-l] != last);

        cout << (changed ? "No" : "Yes") << endl;
    }

    return 0;
}

A. Vladik and Courtesy

Problem - A - Codeforces
aは1,3,5,...と、bは2,4,6,...と何回まで出せるか。出せなくなるターンが同じならaの方が先に出せなくなる。
1+3+5+...(2k-1) = k^2
2+4+6+...(2k) = k(k+1)
からどこまで行けるか計算
// 2人ともVで始まる名前とか辛い。AliceとBobでいいじゃん(ロシアだって言うならアレクセイとボリスとか)
→pretest passed(→AC) 1:39, 302pts

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

int main(){
    int a, b; cin >> a >> b;

    int aalive = (int)sqrt(a);
    int balive = (int)(sqrt(0.25+b) - 0.5);

    int adie = (aalive+1)*2-1;
    int bdie = (balive+1)*2;

    cout << (adie < bdie ? "Vladik" : "Valera") << endl;

    return 0;
}

D.

Problem - D - Codeforces
問題ちらっと見たけど残り20分。今日はおなかいっぱいだしいいや

E.

Problem - E - Codeforces
問題見てない

終了後

agwたんとビデオチャットしてた。
(二人ともB落とされてるし)
Cの解法について。それぞれの解法を説明したり、agwたんのコードに具体的に何を食わせたら落とせるか考えたり。(僕のAC解では考慮に入れられていて、agwたんのコードで考慮に入れられていないポイントは何か)
32bit intを3fで埋めると1e9+αぐらいのちょうどいい値になる、みたいな技をagwたんは当たり前に使ってるし競プロっぽくて格好いいなあ
あと、テストコードを生成するpythonスクリプトの話とか。(CLIを簡単に書けるclickを紹介したりとか)

結果

AxC-- (302 - 1126 - -)
// BはTLE
1428pts 624th
1601→1633 (+32)
レーティングちょっと増えた
f:id:n4_t:20170528000224p:plain