cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM468 の成績・ソース (要ログイン) : AC/MLE/- : この過ちは二度と繰り返さぬ…
3F ・ ・ ・ ＼｜ ＼ 2F ・ ・ ｜ ／｜／ ｜ ←1Fと最上階を繋ぐスーパーエスカレータ 1F ・ ・－－－＋
あとで | |
DPテンプレート改を投入
typedef long long LL; template<typename T> struct DP3x { int N1, N2, N3; vector<T> data; DP3x(int, int N2, int N3, const T& t = T()) : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); } T& operator()(int i1, int i2, int i3) { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } void swap(DP3x& rhs) { data.swap(rhs.data); } }; static const LL inf = (1LL << 60); class RoadOrFlightHard { public: long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K) { vector<LL> rt(N), ft(N); { rt[0] = roadFirst % roadMod; for(int i=1; i<N; ++i) rt[i] = (rt[i-1]*roadProd + roadAdd) % roadMod; ft[0] = flightFirst % flightMod; for(int i=1; i<N; ++i) ft[i] = (ft[i-1]*flightProd + flightAdd) % flightMod; } DP3x<LL> dp(N+1, K+1, 2); for(int n=0; n<=N; ++n) for(int k=0; k<=K; ++k) if( n == 0 ) { dp(n,k,0) = 0; dp(n,k,1) = inf; // ※追記：この行抜けてた。酷い。MLE以前の問題だ… } else { dp(n,k,0) = min(dp(n-1,k,0), dp(n-1,k,1)) + rt[n-1]; if( k == 0 ) dp(n,k,1) = inf; else dp(n,k,1) = min(dp(n-1,k,1), dp(n-1,k-1,0)) + ft[n-1]; } LL ans = inf; for(int k=0; k<=K; ++k) ans = min(ans, min(dp(N,k,0), dp(N,k,1))); return ans; } };
あとで | |
上に書いた方針で。結構長くなってしまった。
typedef int vert; typedef vert edge; typedef vector<edge> edges; typedef vector<edges> graph; bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) { for(int i=0; i<G[v].size(); ++i) { vert u = G[v][i]; if( visited[u] ) continue; visited[u] = true; if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) { matchTo[v]=u, matchTo[u]=v; return true; } } return false; } template<int NV> int biMatch( graph& G, int L ) // [0,L):left, [L,?):right { vector<vert> matchTo(G.size(), -1); int ans = 0; for(vert v=0; v<L; ++v) { bool visited[NV] = {}; if( augment(G, v, matchTo, visited) ) ++ans; } return ans; } int bitcnt(LL x) { int c = 0; for(; x; x>>=1) c += x&1; return c; } class MallSecurity { public: pair<graph, int> generateBipartiteGraph( const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds, const vector<int>& Ks, int msf, int mask ) { // construct a bipartite graph representation, in which // - "even"-floor stations go to the left // - "odd"-floor stations go to the right // here floor number is normalized by rotating the msf-th floor to zero #define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2) // assign interger-ID for each "choosable" station, i.e., // a station which is not at msf and is not connected to a 'mask'ed station on msf map<pair<int,int>,int> ID; int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors { for(int f=0; f<Ks.size(); ++f) if( f != msf ) for(int i=0; i<Ks[f]; ++i) { bool can_use = true; for(int j=0; j<As.size(); ++j) if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j]) || Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) ) can_use = false; if( can_use ) ID[make_pair(f,i)] = nextID[LR(f)]++; } } // then create the graph graph G( nextID[0] + nextID[1] ); for(int j=0; j<As.size(); ++j) { pair<int,int> p(Cs[j], As[j]); pair<int,int> q(Ds[j], Bs[j]); if( ID.count(p) && ID.count(q) ) { int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0); int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0); G[pid].push_back(qid); G[qid].push_back(pid); } } return make_pair(G, nextID[0]); } int maxGuards(int N, vector <string> escDescription) { // parse the input vector<int> As, Bs, Cs, Ds, Ks(N); { stringstream sin; copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") ); for(int A,B,C; sin>>A>>B>>C; ) { {char comma; sin>>comma;} --A, --B, --C; int D=(C+1)%N; // to 0-orign As.push_back(A); Bs.push_back(B); Cs.push_back(C); Ds.push_back(D); Ks[C] = max(Ks[C], A+1); Ks[D] = max(Ks[D], B+1); } } // the most simple floor, where the number Ks[msf] of stations is the least int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin(); // try all possibilities at the msf-th floor size_t answer = 0; for(int mask=0; mask<(1<<Ks[msf]); ++mask) { // then the rest of the part becomes a bipartite graph pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask); // |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch| answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask)); } return answer; } };
presented by
cafelier/k.inaba
under
・点被覆（＝どの辺もどっちかの頂点はカバーされてる）の補集合は独立点集合（＝どの辺もどっちかの頂点はカバーされてない）
・独立点集合の補集合は点被覆
・よって、 最小点被覆←補集合→最大独立点集合
・二部グラフの場合は、|最小点被覆| = |最大マッチング|
・よって二部グラフの場合は、|最大独立点集合|＝|V|-|最大マッチング|