AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip
解法
koyumeishi さんに教えてもらいました。
@mayoko_ こんな感じでわかるかなぁ…？ 赤がコスト 1 、 黒がコスト 0 の辺で、最後に2で割るようにしました。 人のを見ると中継点に入る辺(出る辺)のみコスト1にする派もいるっぽいです pic.twitter.com/4COTPu4rvY
— koyumeishi (@koyumeishi_) 2016年9月11日
各頂点に新しくノードを追加します(電車を乗り換えるときに必ず通る改札みたいなイメージ)。
おなじ路線を使っている間はコスト 0 ですが, 別の路線を使おうと思ったときはこの改札をコスト 1 で通らなければならない, というようにすると辺の数は O(M), 頂点の数は O(N+M) で抑えられるので, ダイクストラすることで問題を解くことができます。
const int MAXM = 202020; vector<pii> G[3*MAXM]; map<pii, int> sid; int lastId = 0; int P[MAXM], Q[MAXM], C[MAXM]; int getid(int v, int c) { pii p(v, c); if (sid.find(p) != sid.end()) return sid[p]; return sid[p] = lastId++; } void addEdge(int p, int q, int c) { int v = getid(p, c), u = getid(q, c); G[v].emplace_back(u, 0); G[u].emplace_back(v, 0); } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> P[i] >> Q[i] >> C[i]; P[i]--; Q[i]--; addEdge(P[i], Q[i], C[i]); } for (int i = 0; i < M; i++) { G[getid(P[i], C[i])].emplace_back(lastId+P[i], 1); G[getid(Q[i], C[i])].emplace_back(lastId+Q[i], 1); G[lastId + P[i]].emplace_back(getid(P[i], C[i]), 1); G[lastId + Q[i]].emplace_back(getid(Q[i], C[i]), 1); } const int INF = 1e9; vector<int> d(lastId+N, INF); d[lastId] = 0; priority_queue<pii> que; que.push(pii(0, lastId)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second, dist = -p.first; if (dist > d[u]) continue; for (auto e : G[u]) { int v = e.first, c = e.second; if (d[v] > d[u]+c) { d[v] = d[u]+c; que.push(pii(-d[v], v)); } } } int ans = d[lastId+N-1]; if (ans == INF) ans = -1; else ans /= 2; cout << ans << endl; return 0; }
2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2 A. Abstract Picture
JAG 夏合宿最終日に yurahuna さんに投げたら勝手に AC してくれた問題です。
問題
N*N のグリッド上に色を塗りたい。
1 回の操作では行に同じ色をバーっと塗るか列に同じ色をバーッと塗るかしかない。
最終的に塗りたい配色が与えられるので, 塗り方を求めよ(塗り方が存在することは保証される)。
解法
後ろから見ていくと, 最終的にある行/列がある一種類のあるアルファベット c + '?' だけで構成されていれば, その行/列を c で塗れば良いです。そこを後から上塗りすればその行/列は塗れることが保証されるので, その行/列を塗る前を考える際は, そこはすべて '?' だったと考えて, 続けて塗れる場所を探していきます。
これを愚直にやると O(N^3) かかりますが(これで通ってもいいじゃない), queue を使うと O(N^2) に出来ます。
cnt[i][c] = (行 i に 文字列 c がいくつあるのか), というのと done[i] = (行 i にまだ残っている文字の種類) というのを覚えておきます。すると, ある列 C を塗ったとき, 各行について, grid[i][C] に書かれている文字はすべて '?' に置換されるので, cnt[i][grid[i][C]]-- 出来ます。これで cnt の値が 0 になったとき, done[i] として残っている文字が 1 種類しかなかったら, その行を que に追加する, というようにやっていきます。
typedef tuple<int, int, char> IIC; const int MAXN = 3030; string field[MAXN]; int cnt[MAXN][2][26]; int done[MAXN][2]; bool check[MAXN][2]; int main() { cin.tie(0); ios::sync_with_stdio(false); map<int, char> mp; mp[0] = 'a'; for (int i = 0; i < 26; i++) { mp[1<<i] = (char)('a'+i); } int N; cin >> N; for (int i = 0; i < N; i++) cin >> field[i]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (field[i][j] != '?') { int num = field[i][j]-'a'; cnt[i][0][num]++; done[i][0] |= 1<<num; } if (field[j][i] != '?') { int num = field[j][i] - 'a'; cnt[i][1][num]++; done[i][1] |= 1<<num; } } } queue<IIC> que; for (int i = 0; i < N; i++) { if (__builtin_popcount(done[i][0]) <= 1) { que.push(IIC(i, 0, mp[done[i][0]])); check[i][0] = true; } if (__builtin_popcount(done[i][1]) <= 1) { que.push(IIC(i, 1, mp[done[i][1]])); check[i][1] = true; } } vector<string> ans(2*N); int t = 0; while (!que.empty()) { int x, type; char c; tie(x, type, c) = que.front(); que.pop(); if (type==0) ans[t] += "h "; else ans[t] += "v "; ans[t] += to_string(x+1) + " "; ans[t] += c; t++; if (done[x][type]) { for (int i = 0; i < N; i++) { if (type == 0) { char& c = field[x][i]; if (c != '?') { int num = c-'a'; if (--cnt[i][1][num] == 0) { done[i][1] ^= 1<<num; if (!check[i][1] && __builtin_popcount(done[i][1]) <= 1) { check[i][1] = true; que.push(IIC(i, 1, mp[done[i][1]])); } } } c = '?'; } else { char& c = field[i][x]; if (c != '?') { int num = c-'a'; if (--cnt[i][0][num] == 0) { done[i][0] ^= 1<<num; if ((!check[i][0]) && __builtin_popcount(done[i][0]) <= 1) { check[i][0] = true; que.push(IIC(i, 0, mp[done[i][0]])); } } } c = '?'; } } } } reverse(ans.begin(), ans.end()); for (string s : ans) cout << s << endl; return 0; }
JAG 夏合宿 Day3 G - Share the Ruins Preservation
問題
jag2016autumn.contest.atcoder.jp
二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。
解法
蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します。上側の凸包を構成するのは, y 座標の上下を逆転させて下側の凸包を構成するのと同じようにできます。よって, 下側凸包を構成しながらそれぞれの凸包の面積を更新していく, というように計算すれば, O(N log N) で
- X 座標の左から見ていった下側凸包
- X 座標の左から見ていった上側凸包(Y 座標を -1 倍すれば良い)
- X 座標の右から見ていった下側凸包(X 座標を -1 倍すれば良い)
- X 座標の右から見ていった上側凸包(X, Y 座標を -1 倍すれば良い)
の面積をそれぞれ計算できます。これを適当に組み合わせて最小値を求めましょう。
すこし注意なのは, 点をソートすべきタイミングです。X 座標の左側から凸包を考えている際, Y 座標を -1 倍した後にソートしてしまうと, 点の位置関係がずれる可能性があるのでソートしてはいけません。
typedef long long Real; struct P { Real x, y; P() {} P(Real x, Real y) : x(x), y(y) {} P operator-(P p) const {return P(x-p.x, y-p.y);} Real det(P p) const {return x*p.y-y*p.x;} // 外積 bool operator<(const P& rhs) const { if (x != rhs.x) return x < rhs.x; return y < rhs.y; } }; ll triArea(const P& x, const P& y, const P& z) { return abs((y-x).det(z-x)); } // 下側凸包の面積を求める vector<ll> convex_hull(vector<P> ps) { int n = ps.size(); int k = 0; // 凸包の頂点数 vector<P> qs(n); // 構築中の凸包 vector<ll> area(n+1); // 下側凸包の作成 for (int i = 0; i < n; i++) { area[i+1] = area[i]; while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) < 0) { if (k >= 3) area[i+1] -= triArea(qs[0], qs[k-2], qs[k-1]); k--; } if (k >= 2) area[i+1] += triArea(qs[0], qs[k-1], ps[i]); qs[k++] = ps[i]; } return area; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<P> ps(N); for (int i = 0; i < N; i++) { cin >> ps[i].x >> ps[i].y; } sort(ps.begin(), ps.end()); auto lb = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].y *= -1; auto lu = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].x *= -1; sort(ps.begin(), ps.end()); auto ru = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].y *= -1; auto rb = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].x *= -1; sort(ps.begin(), ps.end()); ll ans = lb[N] + lu[N] + ru[0] + rb[0]; for (int i = 1; i < N; i++) { if (ps[i-1].x == ps[i].x) continue; // cout << i << endl; // cout << lb[i] << " " << lu[i] << " " << rb[N-i] << " " << ru[N-i] << endl; ll tmp = lb[i] + lu[i] + ru[N-i] + rb[N-i]; ans = min(ans, tmp); } cout << (ans+1)/2 << endl; return 0; }
JAG 夏合宿 Day3 F - Escape from the Hell
問題文は面白かったんですが実装はつらかったです。
解法
最後に A[i] 登るところ以外は, 明らかに D[j] = A[j] - B[j] が大きい順に使うのが最適です。この j をどこまで使うかで場合分けします。
j の最大値も j < i を満たす場合
あらかじめ sumD[i] = D[0] + D[1] + ... + D[i-1], sumC[i] = C[0] + ... + C[i-1] を計算して, sumD[ok] > sumC[ok] を満たす ok の最大値を覚えておきます。
A[i] + sumD[j] >= L を満たす j の最小値のうち, j <= ok となるものがあれば j+1 は解の候補です。
j の最大値が j > i を満たす場合
こっちが少しめんどくさいです。
この場合の上り方を見ると, 以下のようになっています。
D[0] D[1] D[2] ... D[i-1] D[i+1] ... D[j]
C[0] C[1] C[2] ... C[i-1] C[i] ... C[j-1]
よって, seg[i] = sumD[i] - sumC[i-1] というものを覚えておいて, min(seg[i+1], seg[i+2], ..., seg[j]) - D[i] > 0 でありかつ i-1 <= ok であれば良いです。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, numeric_limits<T>::max()); } inline T merge(T x, T y) { return min(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return numeric_limits<T>::max(); if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int INF = 1e9; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, L; cin >> N >> L; vector<pii> P(N); for (int i = 0; i < N; i++) { cin >> P[i].first >> P[i].second; } sort(P.begin(), P.end(), [](const pii& lhs, const pii& rhs){ if (lhs.first-lhs.second == rhs.first-rhs.second) return lhs.first < rhs.first; return lhs.first-lhs.second > rhs.first-rhs.second; }); vector<int> A(N), B(N), D(N); for (int i = 0; i < N; i++) { A[i] = P[i].first; B[i] = P[i].second; D[i] = A[i] - B[i]; } vector<int> C(N); for (int i = 0; i < N; i++) cin >> C[i]; vector<ll> sumD(N+1), sumC(N+1); for (int i = 0; i < N; i++) { sumD[i+1] = sumD[i] + D[i]; sumC[i+1] = sumC[i] + C[i]; } int ok = -1; for (int i = 1; i <= N; i++) { if (sumD[i] - sumC[i] > 0) { ok = i-1; } else break; } // cout << "A B" << endl; // for (int i = 0; i < N; i++) { // cout << A[i] << " " << B[i] << endl; // } // cout << endl; // cout << "ok" << endl; // cout << ok << endl << endl; int ans = INF; { int maxi = 0; for (int i = N-1; i >= 0; i--) { maxi = max(maxi, A[i]); if (i-1 <= ok && maxi + sumD[i] >= L) ans = min(ans, i+1); } } ST<ll> seg(N+1); for (int i = 1; i <= N; i++) { seg.update(i, sumD[i] - sumC[i-1]); } for (int i = 0; i <= min(ok+1, N-2); i++) { // (low, high] int high = N-1, low = i; while (high - low > 1) { const int med = (high+low) / 2; if (sumD[med+1] + B[i] >= L) high = med; else low = med; } if (sumD[high+1] + B[i] < L) continue; //cout << i << " " << high << endl; //cout << seg.query(i+1, high+2) << endl; if (seg.query(i+1, high+2) > D[i]) ans = min(ans, high+1); } //cout << endl; if (ans == INF) ans = -1; cout << ans << endl; return 0; }
SRM 566 div1 med: PenguinEmperor
解法
入力の名前が長いので, n, m とします。
見た目からして行列累乗っぽい感じがします。
具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i <= n についてやります。任意の i について, i 日目の移動の仕方は, i%n 日目のものと一致するので, これだけ調べれば十分です。
で, それを調べ終わったら m/n 回分の行列の掛け算, それと m%n 回分の移動を合わせて答えに組み込めば OK という感じです。
ただ, 今回は n の制約が大きいので行列累乗して O(n^3 log m) にすると危なそうです。ですが, 今回の問題では i -> i+k に移動するような場合の数は, i の値にかかわらず一定になるので, わざわざ行列を作らなくても良く, O(n^2) で計算できます。具体的には,
vector<ll> mul(vector<ll> a, vector<ll> b) {
int n = a.size();
vector<ll> ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
(ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD;
}
return ret;
}
このようにすれば良いです。
const int MAXN = 355; const int MOD = 1e9+7; ll dp[MAXN][MAXN]; vector<ll> mul(vector<ll> a, vector<ll> b) { int n = a.size(); vector<ll> ret(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { (ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD; } return ret; } class PenguinEmperor { public: int countJourneys(int n, long long m) { memset(dp, 0, sizeof(dp)); // numCities 後 0 から i に行く場合の数を数える dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int cw = (j+i+1)%n; int ccw = (j-i-1+n)%n; (dp[i+1][cw] += dp[i][j]) %= MOD; if (cw != ccw) { (dp[i+1][ccw] += dp[i][j]) %= MOD; } } } ll r = m/n, q = m%n; // r 回は累乗っぽいことをやる vector<ll> t(n), tn(n); for (int i = 0; i < n; i++) { t[i] = dp[q][i]; tn[i] = dp[n][i]; } for (int i = 0; i <= 60; i++) { if ((r>>i)&1) { t = mul(t, tn); } tn = mul(tn, tn); } return t[0]; } };
SRM 566 div1 easy: PenguinSledding
問題
TopCoder Statistics - Problem Statement
n 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。
条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線上に来るようにはしない), 選んだ辺同士で交差しない。
解法
あり得る状況としては,
- 単なる辺
- ある頂点にのみたくさん辺がついた感じ(star graph とか言われる)
- 三角形
の三通りがあります(多分三角形が一番気付きにくい)。
star graph に関しては, ある頂点 v に接続する頂点の数を num として, 2^num - 1 - num を計算すれば良いです。
class PenguinSledding { public: long long countDesigns(int n, vector <int> checkpoint1, vector <int> checkpoint2) { ll cnt = 0; int m = checkpoint2.size(); for (int i = 1; i <= n; i++) { ll S = 0; for (int j = 0; j < m; j++) { if (checkpoint2[j] == i || checkpoint1[j] == i) { int v = (checkpoint1[j] == i ? checkpoint2[j] : checkpoint1[j]); S |= 1ll<<v; } } int num = __builtin_popcountll(S); // 次数が 2 以上になるやつ if (num >= 2) { cnt += 1ll<<num; cnt -= 1 + num; } } ll ret = cnt+m+1; for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) for (int k = j+1; k < m; k++) { set<int> S; S.insert(checkpoint1[i]); S.insert(checkpoint2[i]); S.insert(checkpoint1[j]); S.insert(checkpoint2[j]); S.insert(checkpoint1[k]); S.insert(checkpoint2[k]); if (S.size() == 3) ret++; } return ret; } };
JAG 夏合宿 Day2 A - Parades
問題
jag2016summer-day2.contest.atcoder.jp
N 頂点からなる木がある。各頂点の次数はたかだか 10 である。
このグラフ上でいくつかのパレードを開きたい。パレードの候補は M 個あり, その各パレードは頂点 u から 頂点 v へのパスで構成される。
これらのパレードは同時開催するため, 開くパレードはすべてパスの辺を共有していてはならない。最高でいくつのパレードを開けるかを求めよ。
解法
藤原さんの解答を参考にしました。
基本的には木 DP で, dp[v][s] = (頂点 v から伸びている辺のうち, s で表される集合の辺は使ったときに開催できるパレードの数の最大値) とします。
パレードはパスで表されるので, u, v の lca で特徴づけることができます。u -> lca -> v と移動する場合, lca では u 側に降りるために使う辺と v 側に降りるために使う辺を消費します。この辺が lca にとって x 番目, y 番目の辺であった場合,
dp[lca][s|(1<
ということで工夫をする必要があるわけですが, この木 dp は明らかに葉のほうから先にやっていきます。「末端が u であるようなパス」というのは lca -> u というように書けるわけですが, この lca はこれから先どんどん上に伸びていくだけなので, 「今調べている段階で u を終着点とするようなパスでどれだけのパレードを開けているか」というようなものを考えれば良いことになります。下のコードでこれをやっているのは S[v] というやつです。今までのパスの上に一つ頂点がつくことによってパレードの回数が更新される, という感じです。
あと問題なのは 各頂点に対して, その頂点を lca とするものは最高で O(n) 個考えられ, bitDP やってるときにいちいちやっていると O(n^2 2^10) かかって死ぬ, という問題があります。しかしあらかじめ M[x][y] = (頂点 lca で x 本目, y 本目の辺を使う場合に最大で開けるパレードの数) を前計算しておくとこれは大丈夫になります。
int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; while (T--) { int N; cin >> N; vector<vi> G(N); for (int i = 0; i < N-1; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } // 木についていろいろメモ // 頂点を調べる順番 vector<int> T(N); // 子 vector<vi> chs(N); // 親 vector<int> par(N); // 深さ vector<int> d(N); { d[0] = 1; par[0] = -1; int k = 0; queue<int> que; que.push(0); while (!que.empty()) { int now = que.front(); que.pop(); T[k++] = now; for (int ch : G[now]) { if (!d[ch]) { par[ch] = now; chs[now].push_back(ch); d[ch] = d[now] + 1; que.push(ch); } } } } // anc[v][u] = v, u の LCA vector<vi> anc(N, vi(N)); for (int i = 0; i < N; i++) { int v = T[i]; for (int j = 0; j < N; j++) { int u = T[j]; if (v == u) { anc[v][u] = v; } else if (d[v] > d[u]) { anc[v][u] = anc[par[v]][u]; } else if (d[v] < d[u]) { anc[v][u] = anc[v][par[u]]; } else if (d[v] > 1) { anc[v][u] = anc[par[v]][u]; } else { anc[v][u] = 0; } } } vector<vi> dir(N, vi(N)); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { int v = T[i], u = T[j]; if (v != u && anc[v][u] == v) { for (int x = 0; x < chs[v].size(); x++) { int w = chs[v][x]; if (anc[w][u] == w) { dir[v][u] = x; break; } } } } vector<vector<pii> > V(N); int M; cin >> M; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; int lca = anc[a][b]; V[lca].emplace_back(a, b); } // dp vector<vi> dp(N, vi(1<<10)); vi S(N); for (int t = N-1; t >= 0; t--) { int v = T[t]; vi M1(10); vector<vi> M(10, vi(10)); for (pii des : V[v]) { int a = des.first, b = des.second; if (a == v) { int x = dir[v][b]; M1[x] = max(M1[x], S[b]+1); } else if (b == v) { int x = dir[v][a]; M1[x] = max(M1[x], S[a]+1); } else { int x = dir[v][a], y = dir[v][b]; M[x][y] = max(M[x][y], S[a] + S[b] + 1); } } int G = 0; for (int ch : chs[v]) { G += dp[ch][(1<<chs[ch].size())-1]; } dp[v][0] = G; int sz = chs[v].size(); for (int s = 0; s < 1<<sz; s++) { for (int x = 0; x < sz; x++) { if ((s>>x)&1) continue; dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s]); int ch = chs[v][x]; dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s] + M1[x] - dp[ch][(1<<chs[ch].size())-1]); for (int y = 0; y < sz; y++) if (x != y && ((s>>y)&1) == 0) { int ch2 = chs[v][y]; dp[v][s|(1<<x)|(1<<y)] = max(dp[v][s|(1<<x)|(1<<y)], dp[v][s] + M[x][y] - dp[ch][(1<<chs[ch].size())-1] - dp[ch2][(1<<chs[ch2].size())-1]); } } } int All = (1<<sz)-1; for (int des = 0; des < N; des++) { if (des != v && anc[v][des] == v) { int x = dir[v][des]; int ch = chs[v][x]; S[des] += dp[v][All^(1<<x)] - dp[ch][(1<<chs[ch].size())-1]; } } S[v] = dp[v][(1<<sz)-1]; } cout << dp[0][(1<<chs[0].size())-1] << endl; } return 0; }
