トップ > Codeforces > Codeforces Round #416 (Div. 2)

Codeforces Round #416 (Div. 2)

Codeforces

実力不足が出てきているので、ちゃんとブログ活用して精進しなくては…

A - Vladik and Courtesy

問題概要

VladikさんとValeraさんが交互に渡す数を1ずつ増やしながらアメを渡していく。先に渡せなくなるのはどちらか。
※渡されたアメを返すことは出来ない

http://codeforces.com/contest/811/problem/A

解説

普通にシミュレーションすればOKです。渡す数は1,3,5,…と増えていき、累計n2個渡すことになるので、O(√n)で解けます。

int main() {
    int a, b;  cin >> a >> b;
    int give = 1;
    while (true) {
        if (give & 1) {
            a -= give;
            if (a < 0) {
                cout << "Vladik" << endl;
                return 0;
            }
        }
        else {
            b -= give;
            if (b < 0) {
                cout << "Valera" << endl;
                return 0;
            }
        }
        give++;
    }
    return 0;
}

B - Vladik and Complicated Book

問題概要

数列{p}の[l,r]区間をソートしたとき、x番目の要素は移動するか求めよ。

http://codeforces.com/contest/811/problem/B

解説

n,m≦104なので、O(nm)で十分間に合う。
毎回[l,r]区間をソートして大丈夫かと適当に実験して提出したらシステムテストで落とされて辛い目に遭ったので、素直に[l,r]の中でa[x]は何番目に大きいのか調べました。

int main() {
    int n, m;  cin >> n >> m;
    vint a(n);
    rep(i, n)   cin >> a[i];
    while (m--) {
        int l, r, x;   cin >> l >> r >> x;
        l--;    x--;
        int add = 0;
        srep(i, l, r) {
            if (a[i] < a[x])   add++;
        }
        if (x == l + add) cout << "Yes" << endl;
        else  cout << "No" << endl;
    }
    return 0;
}

C - Vladik and Memorable Trip

問題概要

n人が行きたい場所を1か所ずつ用意しながら列になっている。適当な区間で区切って、その中の人たち皆で旅行に行く。ただし、同じ場所に行きたい人たちは全員同じ区間内に居なくてはならないことに注意。区間内の人たちの行きたい場所のxorの総和の最大値を求めよ。

http://codeforces.com/contest/811/problem/C

解説

考察不足だったので猛省しなくてはならない問題でした。

まず、区間を2つに分けられるとき、必ず分けます（その方が総和は大きくなるので）
区間内にある数字の種類を集めていきます（その際に新しく入る数字が初めて出てきたものなら区間を広げる）。で、最後にxorを取って足すDPです。自分はset使いましたが、入れるのは最初だけなので普通にxor使ってよかったと解き終えてから気付きました。

int firstpos[5050];
int lastpos[5050];
int dp[5050];//i番目までを見た時の最大値

int main() {
    int n; cin >> n;
    vint a(n);
    rep(i, n)   cin >> a[i];
    REP(i, 5000) {
        firstpos[i] = 0;
        lastpos[i] = n - 1;
    }
    rep(i, n)   lastpos[a[i]] = i;
    rrep(i, n)  firstpos[a[i]] = i;
    REP(i, n)   dp[i] = 0;
    rep(i, n) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        if (firstpos[a[i]] == i) {
            set<int> ls;
            ls.insert(a[i]);
            int end = lastpos[a[i]];
            int cur = i + 1;
            while (cur <= end) {
                if (cur == firstpos[a[cur]]) {
                    ls.insert(a[cur]);
                    end = max(lastpos[a[cur]], end);
                }
                else if (firstpos[a[cur]]<i) {
                    goto skip;
                }
                cur++;
            }
            int add = 0;
            for (int i : ls) add ^= i;
            dp[cur] = max(dp[cur], dp[i] + add);
        }skip:;
    }
    cout << dp[n] << endl;
    return 0;
}

使ってはいけないgotoを使ってしまっているのはごめんなさいとしか言えません。コンテスト中は最初に出てきた数字を取り逃した状態で2番目以降の数字のみをカウントにいれてしまってWAしたので考察不足と猛省しなくてはなりません。

D - Vladik and Favorite Game

問題概要

迷路を脱出してください。ただし、左右の動き、上下の動きがそれぞれ逆になっているかもしれません。

http://codeforces.com/contest/811/problem/D

解説

これは「インタラクティブ形式」という点を除けばCより簡単なのではないでしょうか。
まず、ゴールからBFSでスタート地点からゴールまでの距離を求めることでルートを確定させます。その後、向かいたい方向へ進み、座標が変化しなければ入れ替わっているので、そのことを記録し、以降逆向きに進むようにすればOKです。正直実装が重いだけでした。

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
string moving = "LDRU";
bool swaped[2];
bool known[2];

int main() {
    int h, w;  cin >> h >> w;
    vector<string> a(h);
    rep(i, h)   cin >> a[i];
    vector<vint> dist(h, vint(w, mod));
    rep(i, h)   rep(j, w) {
        if (a[i][j] == 'F') {
            dist[i][j] = 0;
            queue<pii> q;
            q.push(mp(i, j));
            while (!q.empty()) {
                auto cur = q.front();  q.pop();
                rep(k, 4) {
                    int toy = cur.fst + dy[k];
                    int tox = cur.scn + dx[k];
                    if (toy < 0 || h <= toy)   continue;
                    if (tox < 0 || w <= tox)   continue;
                    if (a[toy][tox] == '.'&&dist[toy][tox] > dist[cur.fst][cur.scn] + 1) {
                        dist[toy][tox] = dist[cur.fst][cur.scn] + 1;
                        q.push(mp(toy, tox));
                    }
                }
            }
            break;
        }
    }
    int by = -1, bx = -1;
    bool start = false;
    while (true) {
        int y=1, x=1;
        if(start) scanf("%d %d", &y, &x);
        start = true;
        if (x == -1) return 0;
        y--;    x--;
        if (dist[y][x] == 0) return 0;
        int next = 0;
        rep(i, 4) {
            if (y + dy[i] < 0 || h <= y + dy[i])   continue;
            if (x + dx[i] < 0 || w <= x + dx[i])   continue;
            if (dist[y][x] == dist[y + dy[i]][x + dx[i]] + 1) {
                next = i;
                break;
            }
        }
        if (next & 1) {
            if (by == y&&bx == x) swaped[1] = true;
            if (known[1] && swaped[1])  next ^= 2;
            else if (!known[1])    known[1] = true;
            printf("%c\n", moving[next]);
            fflush(stdout);
        }
        else {
            if (by == y&&bx == x) swaped[0] = true;
            if (known[0] && swaped[0])  next ^= 2;
            else if (!known[0])    known[0] = true;
            printf("%c\n", moving[next]);
            fflush(stdout);
        }
        by = y; bx = x;
    }
}

感想

システムテストで落とされまくって全然ダメでしたね…（この後問題解きますがAGCもダメでした）
余裕を作って問題をもっと解かなくてはなりません。