Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum
解法
偶数じゃなくて奇数だったら簡単です。というのも, xor は 2 回同じ数をかけられれば自動的に 0 になるので [l, r] の区間の xor を累積和で適当にやれば良いだけだからです。
ですが, これは偶数の場合を聞いているので, 答えるべきものとしては [l, r] の累積xor から, [l, r] に存在する数の xor の和を取ったもの, になります。
累積和は簡単なので, 区間 [l, r] におけるユニークな数の xor 和を考えます。
クエリを R の順番に並べます。で, ある数がすでに表れていた場合には前回現れたところはすべて無効化するような感じにします。具体的には
last[num] = (num が最後に出てくる index) というようにすると, i 番目に num が出てきた場合, A[last[num]] ^= num とやることによって解決します。こういう風にすれば bit なりセグメント木なりで区間 xor の問題に落とせます。
// 0-based Binary Indexed Tree template<typename T> struct BIT { int max; vector<T> bit; BIT(int max) : max(max) {bit.resize(max+1);} // [0, i) T sum(int i) { T s = 0; while (i > 0) { (s ^= bit[i]); i ^= i&-i; } return s; } // 0-basedな座標iに値xを追加する void add(int i, T x) { ++i; while (i <= max) { (bit[i] ^= x); i += i&-i; } } // [a, b) T sum(int a, int b) { return sum(b)^sum(a); } }; const int MAXN = 1001000; int A[MAXN], S[MAXN], L[MAXN], R[MAXN]; int ans[MAXN]; vector<int> G[MAXN]; int main() { int N, M; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", A+i); for (int i = 1; i <= N; i++) S[i] = S[i-1]^A[i-1]; cin >> M; for (int i = 0; i < M; i++) { scanf("%d %d", L+i, R+i); L[i]--; ans[i] = S[R[i]]^S[L[i]]; G[R[i]].push_back(i); } BIT<int> bit(MAXN); map<int, int> last; for (int i = 0; i < N; i++) { bit.add(i, A[i]); if (last.find(A[i]) != last.end()) { bit.add(last[A[i]], A[i]); } for (int j : G[i+1]) { ans[j] ^= bit.sum(L[j], i+1); } last[A[i]] = i; } for (int i = 0; i < M; i++) printf("%d\n", ans[i]); return 0; }
Codeforces Round #372 (Div. 1) B. Complete The Graph
いやなんか時間とってゆっくり競プロやりたいんですけど…
問題
コスト付きの無向グラフが与えられる。いくつかの辺のコストは好きに選べるので, s から t への最短経路の大きさを L にしたい。このようなことが可能であれば, そのうちの 1 つを答えよ。
解法
まず自明に解がない場合を省きます。というのは, いじれるすべての辺のコストを INF にしても最短経路が L 未満の場合と, いじれるすべての辺のコストを 1 にしても最短経路が L より大きい場合です。
逆に, これ以外の場合は, 解が存在することが示せます。これは
- いじれるすべての辺のコストを 1 にすると最短経路は L 未満, 全て INF にすると L より大きい
- いじれる辺のいずれかのコストを 1 増やすと最短経路は 1 増えるかそのまま
から言えます。
で, どう具体的にアルゴリズムに落とすかというと,
- いじれる辺のすべてのコストを 1 にセット
- 以下を繰り返す
- dijkstra して t までの距離を求める。L なら終了
- そうでない場合, s から t までの最短経路にいじれる辺があるはず。その辺のコストを L-d[t]+1 にする。
というようにやれば, いじる辺は M 本しかないので O(M^2 log N) になります(これでギリギリ通った)。さらに, 最初にすべてのコストを 1 にしたときの最短経路上の辺のみを使うようにすると O(NMlog N) になって高速になります。
struct edge { int v; ll w; int id; edge() {} edge(int v, ll w, int id) : v(v), w(w), id(id) {}; }; vector<edge> G[1010]; vector<ll> dijkstra(int n, int s, int t) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; if (u == t) return d; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } void no() { cout << "NO" << endl; exit(0); } const int MAXM = 10101; int U[MAXM], V[MAXM], W[MAXM]; bool use[MAXM]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, L, s, t; cin >> N >> M >> L >> s >> t; const ll INF = 1e9; for (int i = 0; i < M; i++) cin >> U[i] >> V[i] >> W[i]; for (int i = 0; i < M; i++) if (W[i]) { G[U[i]].emplace_back(V[i], W[i], i); G[V[i]].emplace_back(U[i], W[i], i); } auto d = dijkstra(N, s, t); if (d[t] < L) no(); if (d[t] == L) { cout << "YES" << endl; for (int i = 0; i < M; i++) { ll w = (W[i]==0) ? INF : W[i]; cout << U[i] << " " << V[i] << " " << w << endl; } return 0; } for (int i = 0; i < M; i++) if (!W[i]) { G[U[i]].emplace_back(V[i], 1, i); G[V[i]].emplace_back(U[i], 1, i); } d = dijkstra(N, s, t); if (d[t] > L) no(); { int now = t; while (now != s) { for (edge e : G[now]) { if (d[e.v] + e.w == d[now]) { use[e.id] = true; now = e.v; break; } } } } while (1) { for (int i = 0; i < N; i++) G[i].clear(); for (int i = 0; i < M; i++) { ll w = INF; if (W[i] == 0 && use[i]) w = 1; if (W[i]) w = W[i]; G[U[i]].emplace_back(V[i], w, i); G[V[i]].emplace_back(U[i], w, i); } auto d = dijkstra(N, s, t); if (d[t] == L) break; int now = t; while (now != s) { int id = -1; for (edge e : G[now]) { if (d[e.v]+e.w == d[now]) { id = e.id; now = e.v; break; } } if (W[id] == 0) { W[id] = L-d[t]+1; break; } } } cout << "YES" << endl; for (int i = 0; i < M; i++) { ll w = INF; if (W[i] == 0 && use[i]) w = 1; if (W[i]) w = W[i]; cout << U[i] << " " << V[i] << " " << w << endl; } return 0; }
Codeforces Round #367 (Div. 2) E. Working routine
問題
N*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。
全てのクエリを処理した後の最終的なグリッドの状態を求めよ。
解法
リストの考え方を応用すると解けます。
各ノードに「左隣, 右隣, 上隣, 下隣」のノードを覚えてもらうと, 領域内のほとんどのセルは隣接するセルが変化せず, 領域の周りのセルだけ隣接関係が変わっていることに注意すると, 各クエリは O(N+M) で処理できます。下の図を見ると多少イメージがわくと思います。
隣接関係の更新の仕方(というか順番)は工夫しないと簡単にバグるので注意です。
const int MAX = 1010; struct Node { Node() {init();} Node(int r, int c) : r(r), c(c) {init();} void init() { right = NULL; left = NULL; top = NULL; bottom = NULL; } int r; int c; Node* right; Node* left; Node* top; Node* bottom; }; Node* nodes[MAX][MAX]; int board[MAX][MAX]; int N, M, Q; // node1 <-> node2, node3 <-> node4 void changeNode1(Node* node1, Node* node2, Node* node3, Node* node4) { node1->right = node4; node3->right = node2; node2->left = node3; node4->left = node1; } // node1, node3 // node2, node4 void changeNode2(Node* node1, Node* node2, Node* node3, Node* node4) { node1->bottom = node4; node3->bottom = node2; node2->top = node3; node4->top = node1; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> Q; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> board[i][j]; for (int i = 0; i <= N+2; i++) for (int j = 0; j <= M+2; j++) nodes[i][j] = new Node(i, j); for (int i = 0; i <= N+1; i++) { for (int j = 0; j <= M+1; j++) { if (i) nodes[i][j]->top = nodes[i-1][j]; if (j) nodes[i][j]->left = nodes[i][j-1]; nodes[i][j]->right = nodes[i][j+1]; nodes[i][j]->bottom = nodes[i+1][j]; } } while (Q--) { int a, b, c, d, h, w; cin >> a >> b >> c >> d >> h >> w; Node* root1 = nodes[a][0]; Node* root2 = nodes[c][0]; for (int i = 0; i < b; i++) root1 = root1->right; for (int i = 0; i < d; i++) root2 = root2->right; // 上辺, 右辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } } // 左辺, 下辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } } } for (int i = 1; i <= N; i++) { Node* root = nodes[i][0]; for (int j = 0; j < M; j++) { root = root->right; int r = root->r, c = root->c; r--; c--; cout << board[r][c] ; if (j < M-1) cout << " "; } cout << endl; } return 0; }
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; }