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パターンだけサイクルになるからそれを引いて、残りの辺はどうでもいいので掛け算、という感じ。
解法はすぐにわかったのですが無向グラフの閉路検出ができず。
ところがこのグラフよく見ると(よく見なくても)全頂点の出次数が1ですから、「今サイクルじゃないけど、向きを変えるとサイクル」というのがないわけです。だから有向グラフのまま閉路検出しても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を落としたのはアレですが。