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

CodeForces 363div2

http://codeforces.com/contest/699/
 最近調子が悪い……。
A: てきとうにupper_boundする

#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

const int INF = 1.0e9 + 10;
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> R, L;
    string s; cin >> s;
    rep(i, N) {
        int k; cin >> k;
        if(s[i] == 'R') R.push_back(k);
        else L.push_back(k);
    }
    L.push_back(INF);
    sort(L.begin(), L.end());
    int ans = INF;
    for(int k : R) {
        int temp =  *upper_bound(L.begin(), L.end(), k);
        if(temp == INF) continue;
        temp = (temp - k) / 2;
        ans = min(ans, temp);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

B : 列ごとの合計を持って全(x, y)について全消し可能か見るだけ。
SRMで疲れていたとはいえ、これに30分使うのはまずいですね……。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int R, C; cin >> R >> C;
    vector<string> fld(R);
    rep(i, R) cin >> fld[i];
    vector<int> tate(C, 0), yoko(R, 0);
    int sum = 0;
    rep(i, R) rep(j, C) if(fld[i][j] == '*') {
        sum++;
        tate[j]++;
        yoko[i]++;
    }
    rep(i, R) rep(j, C) {
        int cosum = tate[j] + yoko[i];
        if(fld[i][j] == '*') cosum--;
        if(cosum == sum) {
            cout << "YES" << endl;
            cout << i + 1 << ' ' << j + 1 << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

C: 簡単なDP。コード汚ないですがまあ仕方ない。
 これに一時間使うのは本当にまずいですね。DP苦手過ぎます。
 N <= 100とかいう余裕過ぎる制約が罠でした。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

vector<int> a; int N;
int dp[110][3];
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N) {
        int k; cin >> k;
        a.push_back(k);
    }
    rep(i, 110) rep(j, 3) dp[i][j] = 1.0e9;
    if(a[0] == 0) dp[0][0] = 1;
    else if(a[0] == 1) dp[0][1] = 0;
    else if(a[0] == 2) dp[0][2] = 0;
    else
      dp[0][1] = dp[0][2] = 0;
    REP(i, 1, N) {
        if(a[i] == 0) {
            rep(j, 3) dp[i][0] = min(dp[i][0], dp[i - 1][j] + 1);
        }else if(a[i] == 1) {
            rep(j, 3) if(j != 1) dp[i][1] = min(dp[i][1], dp[i - 1][j]);
            rep(j, 3) dp[i][0] = min(dp[i][0], dp[i - 1][j] + 1);
        }else if(a[i] == 2) {
            rep(j, 3) if(j != 2) dp[i][2] = min(dp[i][2], dp[i - 1][j]);
            rep(j, 3) dp[i][0] = min(dp[i][0], dp[i - 1][j] + 1);
        }else {
            rep(j, 3) if(j != 1) dp[i][1] = min(dp[i][1], dp[i - 1][j]);
            rep(j, 3) if(j != 2) dp[i][2] = min(dp[i][2], dp[i - 1][j]);
            rep(j, 3) dp[i][0] = min(dp[i][0], dp[i - 1][j] + 1);
        }
    }
    int ans = 1.0e9;
    rep(i, 3) ans = min(ans, dp[N - 1][i]);
    cout << ans << endl;
    return 0;
}

 普段メモ化に頼りすぎているせいかこういう自明DPがびっくりするほど解けません。なんとか通せたのは良かったですけど順位が死んでしまいました。

D:
 UF木で閉路判定するだけジャンと思ったらrootが一つじゃないといけないなんていう謎ルールがあったんですね……(死)。
 ちょっと問題文不親切な気もしますけどこれは入力を見て気づくべきでした。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

struct UnionFind {
    vector<int> data; int group;
    UnionFind(int N) : data(N, -1), group(N) {}
    void init(int N) {
        data.assign(N, -1);
        group = N;
    }
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(x != y){
            data[x] += data[y];
            data[y] = x;
            --group;
        }
    }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]);}
    bool same(int a, int b) { return root(a) == root(b);}
};


int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> p(N);
    int root = -1;
    rep(i, N) {
        cin >> p[i];
        --p[i];
        if(p[i] == i) root = i;
    }
    UnionFind uf(N);
    int ans = 0;
    rep(from, N) {
        int& to = p[from];
        if(from == to) {
            if(from == root) continue;
            ans++;
            to = root;
        } else if(uf.same(from, to)) {
            if(root == -1) root = from;
            ans++;
            to = root;
        }
        uf.unite(from, to);
    }
    
    cout << ans << endl;
    rep(i, N) cout << p[i] + 1 << (i == N - 1 ? '\n' : ' ');
    return 0;
}

 なかなか強くならんという感じですね。