Codeforces 369div2

久しぶりに出ました。
http://codeforces.com/contest/711

A
特に罠はなかったですね。

B
一箇所穴の空いた魔法陣に数字を入れる。
数字がマイナスになることはないと勘違いしており落ちました（悲しすぎる……）。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<vector<i64> > fld(N, vector<i64>(N));
    int aimx = 0, aimy = 0;
    rep(i, N) rep(j, N){
        cin >> fld[i][j];
        if(fld[i][j] == 0) {
            aimx = j;
            aimy = i;
        }
    }
    if(N == 1) {
        cout << 1 << endl;
        return 0;
    }
    int it = (aimy + 1) % N;
    i64 sum = accumulate(fld[it].begin(), fld[it].end(), 0LL);
    i64 tsum = accumulate(fld[aimy].begin(), fld[aimy].end(), 0LL);
    if(sum <= tsum) {
        cout << -1 << endl;
        return 0;
    }
    fld[aimy][aimx] = sum - tsum;
    bool ok = [&](){
        rep(i, N) {
            i64 tsum = accumulate(fld[i].begin(), fld[i].end(), 0LL);
            if(tsum != sum) return false;
            tsum = 0LL;
            rep(j, N) tsum += fld[j][i];
            if(tsum != sum) return false;
        }
        i64 tsum = 0LL;
        rep(i, N) tsum += fld[i][i];
        if(tsum != sum) return false;
        tsum = 0LL;
        rep(i, N) tsum += fld[i][N - i - 1];
        if(tsum != sum) return false;
        return true;
    }();
    if(ok) cout << fld[aimy][aimx] << endl;
    else cout << -1 << endl;
    return 0;
}

本番中もこのくらい冷静なコードが書けると良かったのですが。
変なコード書いたせいでデバッグに時間使いすぎました。

C
わりと典型かな？
dp[i][j][k] := iまで見て、最後が色jで、分割数kのときのコスト
でminをとって計算。
愚直にやるとN*K*M*Mですが、ちょっと工夫してN*M*Kにしました。ですが定数倍が軽いからか愚直でも通るようです。

#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)
typedef long long int i64;
typedef pair<i64, i64> pint;

const i64 INF = 1.0e18;
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M, K; cin >> N >> M >> K;
    vector<int> c(N);
    rep(i, N) cin >> c[i];
    vector<vector<i64>> p(N, vector<i64>(M + 1, INF));
    rep(i, N) REP(j, 1, M + 1) cin >> p[i][j];
    vector<vector<i64>> dp(M + 1, vector<i64>(K + 1, INF));
    auto dp_ = dp;
    dp[0][0] = 0LL;
    rep(i, N) {
        dp_.assign(M + 1, vector<i64>(K + 1, INF));
        if(c[i] == 0) {
            //同じ色
            vector<pint> mi(K + 1, pint(INF, INF));
            rep(k, M + 1) rep(j, K + 1) {
                dp_[k][j] = min(dp_[k][j], dp[k][j] + p[i][k]);
                if(mi[j].first > dp[k][j]) {
                    mi[j].second = mi[j].first;
                    mi[j].first = dp[k][j];
                }
                else if(mi[j].second > dp[k][j])
                  mi[j].second = dp[k][j];
            }
            //違う色
            rep(k, M + 1) rep(j, K) {
                i64 plus = mi[j].first;
                if(plus == dp[k][j]) plus = mi[j].second;
                dp_[k][j + 1] = min(dp_[k][j + 1], plus + p[i][k]);
            }
        }
        else {
            int col = c[i];
            rep(k, M + 1) rep(j, K + 1) {
                int j_ = k == col ? j : j + 1;
                if(j_ > K) continue;
                dp_[col][j_] = min(dp_[col][j_], dp[k][j]);
            }
        }
        dp = dp_;
    }
   // rep(i, M + 1) rep(j, K + 1) cout << dp[i][j] << endl;
    i64 ans = INF;
    REP(i, 1, M + 1) ans = min(ans, dp[i][K]);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

これは通ったのはまあ良かったけど時間かかりすぎました。
なんか使わない色の処理とか面倒だと思うんですがみんな速い……。

D
無向グラフに変換してサイクルを検出。
閉路のところは2パターンだけサイクルになるからそれを引いて、残りの辺はどうでもいいので掛け算、という感じ。
解法はすぐにわかったのですが無向グラフの閉路検出ができず。
ところがこのグラフよく見ると（よく見なくても）全頂点の出次数が１ですから、「今サイクルじゃないけど、向きを変えるとサイクル」というのがないわけです。だから有向グラフのまま閉路検出してもOK。

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

const i64 MOD = 1.0e9 + 7;
int p[200000], vis[200000];
i64 power[200001];
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    rep(i, N) {
        cin >> p[i];
        --p[i];
    }
    {
        power[0] = 1LL;
        rep(i, N) power[i + 1] = (power[i] << 1LL) % MOD;
    }
    memset(vis, -1, sizeof(vis));
    i64 ans = 1LL; int sum = N;
    rep(i, N) if(vis[i] == -1) {
        int x = i;
        while(true) {
            vis[x] = i;
            x = p[x];
            if(vis[x] != -1) break;
        }
        if(vis[x] != i) continue;
        int cyc = 0, y = x;
        while(true) {
            y = p[y]; ++cyc; --sum;
            if(y == x) break;
        }
        ans = ans * (power[cyc] - 2LL) % MOD;
    }
    ans = (ans * power[sum]) % MOD;
    cout << ans << endl;
    return 0;
}

レートは微増で1605。
今回は割りとクソ問感あるのが多かったですが（初心者なのでCの典型DPは嫌いじゃないです）、自分なりに頭使ったのでまあ良かったかな。Bを落としたのはアレですが。