読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #331 (Div. 2) A~C

virtual。

結果

f:id:pakapa104:20160312194205p:plain

2完。Aは場合分けをややこしく考えていてバグらせた。Bの方が簡単。Cはひたすら実装がしんどかったが考え方から違った感じ。

A. Wilbur and Swimming Pool

座礁軸に平行な辺を持つ長方形の頂点の4つのうち、いくつかが失われた。もとの長方形は一意に定まるか。定まる場合、その面積を答えよ。という問題。

x座標とy座標にそれぞれ異なる2つの値があれば、差を掛け算したものが答えとなる。そこさえ気づけば場合分けなんて要らなかった。

n = int(input())
p = []
for i in range(n):
    x, y = map(int, input().split())
    p.append([x, y])

if n == 1:
    print(-1)
elif n == 2:
    if p[0][0] != p[1][0] and p[0][1] != p[1][1]:
        print(abs(p[0][0] - p[1][0]) * abs(p[0][1] - p[1][1]))
    else:
        print(-1)
else:
    x1 = p[0][0]
    x2 = 0
    for i in range(1, n):
        if x1 != p[i][0]:
            x2 = p[i][0]
            break
    y1 = p[0][1]
    y2 = 0
    for i in range(1, n):
        if y1 != p[i][1]:
            y2 = p[i][1]
            break
    print(abs(x2 - x1) * abs(y2 - y1))

B. Wilbur and Array

前から順に揃えていけばよい。

n = int(input())
b = list(map(int, input().split()))
t = 0
ans = 0
for bx in b:
    ans += abs(t - bx)
    t = bx
print(ans)

C. Wilbur and Points

wが等しい頂点は右上がりの直線上にある。この直線上にある点について、番号は左下にあるものほど小さくなければならない。よってwを左から走査し、wの直線上で使われていない最も左下の頂点に番号を振ることを繰り返す。最後に番号が題意を満たすか判定すればよい。( n(i, j) = 点(i, j)に振られた番号 とすると、 n(i - 1, j) <= n(i, j) かつ n(i, j - 1) <= n(i, j) であるかを調べればよい)

本番はBFSでシミュレーションしようとしていたが実装が難しすぎて詰んだ。下の解答もほとんどWriter解の写経なので、また今度自分で書けるか復習しよう……。

const int MAX_N = 100010;

int N;
map<int, vector<P>> weights;
map<int, vi> cnt;   //  (w, indices)
P ans[MAX_N];
vi diag[MAX_N];

signed main() {
    cin >> N;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        while (diag[x].size() <= y) diag[x].emplace_back(0);
        weights[y - x].emplace_back(P(x, y));
    }
    for (auto& v : weights) {
        sort(all(v.second));
    }
    rep(i, N) {
        int w;
        cin >> w;
        cnt[w].emplace_back(i);
    }
    for (auto v : cnt) {
        if (weights.count(v.first) == 0 || weights[v.first].size() != v.second.size()) {
            cout << "NO" << endl;
            return 0;
        }
        rep(i, v.second.size()) {
            ans[v.second[i]] = weights[v.first][i];
            diag[weights[v.first][i].first][weights[v.first][i].second] = v.second[i];
        }
    }
    rep(i, MAX_N) {
        rep(j, (int)diag[i].size()) {
            if ((int)diag[i+1].size() > j && diag[i+1][j] < diag[i][j]) {
                cout << "NO" << endl;
                return 0;
            }
            if (j + 1 < (int)diag[i].size() && diag[i][j] > diag[i][j+1]) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
    rep(i, N) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}

3完!3完がほしいんじゃ!!