AtCoder Beginner Contest 041 D - 徒競走
問題概要
略
解法
コメント
#define MAX_N 16 int N,M; ll dp[1 << MAX_N]; bool edge[MAX_N][MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M; REP(i, M) { int x, y; cin >> x >> y;x--;y--; edge[x][y] = true; } // dp[mask]:=mask (2進数) が1のノードだけの並び替えパターン数 // 上記の並び替えの一番後ろにまだ使用してないノードを加えることができるかを考える dp[0] = 1; REP (i, 1 << N) { // j+1 bit目が0の時 REP(j,N) if (!( (i >> j) & 1)) { bool isOk = true; // k+1 bit目が1の時 j → k というノードが存在するならアウト REP(k, N) if ( (i >> k) & 1) if (edge[j][k]) isOk = false; // j+1 bit目 を立てた場合の数にプラス if (isOk) dp[i + (1 << j)] += dp[i]; } } cout << dp[int(1 << N)-1] << endl; return 0; }
POJ 3280 Cheapest Palindrome
POJは制約が多すぎる (unordered_mapが使えなかった)
問題概要
- N種類の文字で構成された長さMの文字列Sが与えられる
- この文字列にいくつかの文字を追加、あるいは削除して回文にする
- i番目の文字を追加するには、a_iのコスト、削除するにはb_iのコストがかかる
解法
- abbbbを回分にする時aを追加して、abbbbaとする方法と、aを削除してbbbbとする方法どちらでも可である
- 従って、追加 or 削除はコストの低い方を用いる
- dp[i][j]:=区間[i,j)を回文にするコストとすると
- ある、長さlenの区間について
- dp[i][j+1] = max(dp[i][j+1], dp[i][j]+S[j]のコスト)
- dp[i-1][j] = max(dp[i-1][j], dp[i][j]+S[i-1]のコスト)
- if (S[i-1]==S[j]) dp[i-1][j+1] = max(dp[i-1][j+1],dp[i][j])
- 以上のdpを区間lenが0 ~ M-1の間繰り返す
参考
AtCoder Regular Contest 056 B - 駐車場
問題概要
略
解法
- ある車xに着目する時、あるエッジの両端u,vについて、min(u,v) >= xの時、その道にまだ車が止まっていないため通行可能である
- 通行可能な道をUnion Findでマージし、same(S, x)がtrueとなれば到達可能である
- この制約はxが大きくなるほど厳しくなるため、エッジをmin(u, v)が大きい順にソートし、大きい車から順番に見ていく
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007LL #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; struct UnionFind{ vector<int> parents; vector<int> rank; UnionFind(int n){ parents.resize(n); rank.assign(n, 1); REP(i, n){ parents[i] = i; } } int find(int x){ if(parents[x] == x) return x; return parents[x] = find(parents[x]); } int unite(int x, int y){ x = find(x); y = find(y); if(x == y) return -1; if(rank[x] > rank[y]) parents[y] = x; else{ parents[x] = y; if(rank[x]==rank[y]) rank[y]++; } return 0; } bool same(int x, int y){ return find(x) == find(y); } }; #define MAX_N 200010 int N, M, S; p t[MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M >> S; S--; REP(i,M) { int u,v; cin >> u >> v; u--;v--; t[i].first=min(u,v); t[i].second=max(u,v); } sort(t,t+M,greater<p>()); UnionFind uf(N); int cur=0; vector<int> ans; for (int i = N-1; i >= 0; i--) { while(cur<M) { if(t[cur].first>=i) { uf.unite(t[cur].first, t[cur].second); cur++; } else break; } if (uf.same(S,i)) ans.pb(i); } reverse(all(ans)); for(auto x: ans) { cout << ++x << endl; } return 0; }
POJ 2229 Sumsets
蟻本章末問題
問題概要
- ある数字Nが与えられる
- Nを2の累乗の数の和で表す
- 例えば4なら
- 4
- 2 + 2
- 2 + 1 + 1
- 1 + 1 + 1 + 1
- そのような組み合わせは何通りか
解法
- dp[i] := N=iの時の組み合わせの数
- dp[i] = dp[i/2] + dp[i-1] then i mod 2=0
dp[i] = dp[i-1] other
POJ 3176 Cow Bowling
蟻本章末問題
問題概要
- ボーリングのピンが並んでる
- 一番前のピンを倒す
- その後ろのピンのうち左右どちらかのピンを倒すことができる
- さらに、その後ろのピンのうち左右どちらかのピンを倒すことができる
- 以上の作業を繰り返し一番後ろのピンまで倒す
- ピンには点数がついていて、倒すピンの点数の合計を最大化する
解法
- 動的計画法
- L[i][j] := 前からi番目, 向かって右からj番目のピンの点数
- dp[i][j] := 前からi番目, 向かって右からj番目のピンを倒し、一番後ろまで最適なピンを倒した時に得られる得点
- dp[i][j] := L[i][j] + max(dp[i+1][j], dp[i+1][j+1])
AtCoder Regular Contest 045 C - エックスオア多橋君
問題概要
- 木
- ノードとノードの単純パスの距離は通ったエッジのXOR和
- XOR和がXになるのは何通りか
解法
あるノードを根とした時、aとbの単純パスはa-LCA(a,b)-bである。
※LCAはLowest Common Ancestor
すなわちその距離L(a,b)は、
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b)
ここで、
A^X^X = A
であることを考えると
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b)
= L(a,LCA(a,b))^L(LCA(a,b),root)^L(root,LCA(a,b))^L(LCA(a,b),b) ※rootは根
= L(a,root)^L(root,B)
である。
つまり、a-root-bと辿った場合に等しい。
したがって、適当なノードを根とし、全探索で距離を求めたあと、a-root-bの距離がXとなる組み合わせを数えればよい。
AtCoder Regular Contest 048 C - 足の多い高橋君
問題概要
(リンク)http://arc048.contest.atcoder.jp/tasks/arc048_c
- 高橋君はN本の足がある
- N本の足はLi本のパーツに分かれている
- Li本の足に0か1を書き込む
- 任意の2本の足A,Bを選んだ時、Aのつま先-胴体-Bのつま先と辿った時、0、1は回文となっていなければいけない。
解法
公式スライド参照
