Codeforces Round #368 (Div. 2) D. Persistent Bookcase
これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ…
問題
最初すべてのセルが塗られていないグリッドが与えられる。以下の Q 個クエリを処理し, グリッドで黒色のセルの数を出力せよ。
- i 行 j 列目のセルが白なら黒くする。
- i 行 j 列目のセルが黒なら白くする。
- i 行目の白黒を反転させる。
- クエリの q 個目の状態に戻す。
解法
あらかじめどういうクエリが来るかはわかっているので, 「クエリの q 個目の状態に戻す」というのが来たときどこに戻れば良いかを覚えておけば, 基本的にはクエリの木構造ができています。木構造に合わせて, 素直にクエリを処理していけば O(NQ) 程度でできます。
const int MAXQ = 100100; int N, M, Q; int T[MAXQ], I[MAXQ], J[MAXQ]; int ans[MAXQ]; int reff[MAXQ]; vector<int> G[MAXQ]; bool board[1010][1010]; int S; void dfs(int v) { ans[v] = S; for (int ch : G[v]) { if (T[ch] == 1) { bool prv = board[I[ch]][J[ch]]; if (!board[I[ch]][J[ch]]) { S++; } board[I[ch]][J[ch]] = true; dfs(ch); board[I[ch]][J[ch]] = prv; if (!prv) S--; } else if (T[ch] == 2) { bool prv = board[I[ch]][J[ch]]; if (board[I[ch]][J[ch]]) { S--; } board[I[ch]][J[ch]] = false; dfs(ch); board[I[ch]][J[ch]] = prv; if (prv) S++; } else if (T[ch] == 3) { for (int i = 0; i < M; i++) { if (board[I[ch]][i]) { S--; board[I[ch]][i] = false; } else { S++; board[I[ch]][i] = true; } } dfs(ch); for (int i = 0; i < M; i++) { if (board[I[ch]][i]) { S--; board[I[ch]][i] = false; } else { S++; board[I[ch]][i] = true; } } } else { assert(0); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> Q; for (int i = 1; i <= Q; i++) { cin >> T[i] >> I[i]; if (T[i] <= 2) cin >> J[i]; if (T[i] <= 3) I[i]--; J[i]--; } int now = 0; for (int i = 1; i <= Q; i++) { if (T[i] <= 3) { G[now].emplace_back(i); now = i; reff[i] = i; } else { now = reff[I[i]]; reff[i] = now; } } dfs(0); for (int i = 1; i <= Q; i++) cout << ans[reff[i]] << endl; return 0; }
AtCoder Regular Contest 061 F - 3人でカードゲーム / Card Game for Three
解法
まず普通に解法を考えます。一度それぞれのカードを決めたらすでにゲームの勝敗は決まっていることを考えるとなんか dp ではないような気がします。で, 問題の性質をよく考えると A さんが勝つには A さんに N 回ターンが回ってくれば良いことに気付きます。また, B, C が勝たないためには, B, C さんにそれぞれ M+1 回, K+1 回, ターンが回ってきてはいけないことに気付きます。つまり, 解法としては,
- 'b' が M+1 回, 'c' が K+1 回出る前に 'a' が N 回出るような N+M+K 枚のカードの並べ方は何通りあるか？
という問題に帰着します。
まず部分点のほうを考えましょう(下のコードでコメントアウトされているのがそれです)。
'b', 'c' の出る回数をそれぞれ m, k とします。この場合は, 'b' が m 回, 'c' が k 回, 'a' が N-1 回出たのちに 'a' が 1 回出る, で後はどうなっていても良い, という感じになるので,
comb[N-1+m+k][N-1] * comb[m+k][m] * 3^(M+K-m-k)
通りあります。これを m, k 全ての場合について数えれば良いです。
次に満点解法のほうを考えます。上の式をよく見ると, 「m+k」というのがいろんなところに出ていて, comb[m+k][m] の m, k に対する和さえ求められれば後は m+k に関する式になっているので m+k について全探索するだけで行けることに気付きます。
ということで comb[m+k][m] の m に関する和を求める方法を考えます。M=2, K=4 の場合について和を求める場所を考えると下の図のようになています。
i 行目から i+1 行目の和を考える際には, 漸化式 comb[n+1][r] = comb[n][r] + comb[n][r-1] を考えると, i+1 行目に移るときほとんど和が 2 倍になっていることが分かります。端っこのところだけ微妙にずれることがありますが, そこは適当にうまくやります。
ll mod_pow(ll x, ll p, ll MOD) {
ll a = 1;
while (p) {
if (p%2) a = a*x%MOD;
x = x*x%MOD;
p/=2;
}
return a;
}
// mod_inverse
ll mod_inverse(ll a, ll m) {
return mod_pow(a, m-2, m);
}
const int MOD = 1e9+7;
const int MAX = 1000000;
ll fact[MAX], rfact[MAX];
ll p3[MAX];
ll nCr(int n, int r) {
return fact[n]*rfact[r]%MOD*rfact[n-r]%MOD;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
fact[0] = rfact[0] = 1;
for (int i = 1; i < MAX; i++) {
fact[i] = i*fact[i-1]%MOD;
rfact[i] = mod_inverse(fact[i], MOD);
}
p3[0] = 1;
for (int i = 1; i < MAX; i++) {
p3[i] = p3[i-1]*3%MOD;
}
int N, M, K;
cin >> N >> M >> K;
ll ans = 0;
// for (int m = 0; m <= M; m++) {
// for (int k = 0; k <= K; k++) {
// ll tmp = fact[N-1+m+k];
// (tmp *= rfact[N-1])%=MOD;
// (tmp *= rfact[m])%=MOD;
// (tmp *= rfact[k])%=MOD;
// (tmp *= p3[M+K-m-k])%=MOD;
// (ans += tmp) %= MOD;
// }
// }
ll sum = 1;
int low = 0, high = 0;
for (int i = 0; i <= M+K; i++) {
ans += nCr(N-1+i, N-1)*sum%MOD*p3[M+K-i]%MOD;
int nh = min(i+1, M);
int nl = max(0, i+1-K);
sum = 2*sum;
if (low < nl) sum -= nCr(i, low);
if (high == nh) sum -= nCr(i, high);
sum = (sum%MOD+MOD)%MOD;
high = nh;
low = nl;
}
ans %= MOD;
cout << ans << endl;
return 0;
}
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]; } };
