CF 782 D - Innokenty and a Football League
問題
問題概要
サッカーチームが個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。
各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある:
- 1単語目のprefix3文字を取る。
- 1単語目のprefix2文字と2単語目の頭文字を取る。
ただ、あるチームが2つめの候補を選ぶためには条件がある。それはチームが2つめの候補を選んだ場合、他のチームはチームの1つめの候補を、「1つ目の候補として」選んでいてはいけないということである。もちろん、同じ省略形を複数のチームが使うことも許されない。
チームの省略形の割り当てとして、正当なものがあればその割当て方法を、不可能ならNO
と答えよ。
- 各チームの2つの単語はそれぞれ3文字以上20文字以下
アイデア
最近2-SATを使う問題(http://codeforces.com/problemset/problem/875/C)にコンテスト中に遭遇した(残念ながら時間内に解けなかった)ので、それもあって2-SATの問題をいくつかやっていた。以前に出会ったこの問題も変な貪欲をやろうしていたが、考慮しきるのは大変だし見落としがちなので、条件を作って2-SATで解いてみる。
リテラルを、1つ目の候補を採用することをtrue
、2つ目の候補を採用することをfalse
として表すことにする。
クロージャとして作らなければならないのは、まず大前提として同じになってしまうのは避けなければならない。
あとは、概要のところにも書いたとおり、あるチームが2つめの候補を取る場合は、他のチームが、チームが1つめの候補を、1つめの候補として採用していてはならないということである。これは、との1つめの候補が同じ場合に、というクロージャを追加するということを意味する。これで2-SATの条件を盛り込めるので、後はSCCによりこれを解く。辺の数はなので、十分間に合う。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct SCC{ int V; vector<vector<int>> G, rG; vector<int> vs; // 帰りがけ順の並び vector<int> cmp; //属する強連結成分トポロジカル順序 vector<bool> used; SCC(){} SCC(int n){ V = n; G = vector<vector<int>>(n); rG = vector<vector<int>>(n); } void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; rep(i,G[v].size())if(!used[G[v][i]]) dfs(G[v][i]); vs.push_back(v); } void rdfs(int v, int k){ used[v]=true; cmp[v]=k; rep(i,rG[v].size())if(!used[rG[v][i]]) rdfs(rG[v][i],k); } int scc(){ used = vector<bool>(V,false); vs.clear(); rep(i,V)if(!used[i]) dfs(i); used = vector<bool>(V,false); cmp = vector<int>(V); int num_scc = 0; for(int i=vs.size()-1; i>=0; --i)if(!used[vs[i]]) rdfs(vs[i],num_scc++); return num_scc; } }; struct TwoSat{ int v; SCC graph; // v literals // 0~v-1: true // v~2v-1: false TwoSat(int num_literal){ v = num_literal; graph = SCC(2*v); } inline int num(int id, bool b){return id+(b?0:v);} void add_clause(int x, bool X, int y, bool Y){ graph.add_edge(num(x,!X), num(y,Y)); graph.add_edge(num(y,!Y), num(x,X)); } // 割り当てが可能か調べる bool calc(){ graph.scc(); rep(i,v)if(graph.cmp[i]==graph.cmp[v+i]) return false; return true; } // リテラルの真偽値を返す vector<bool> get_literals(){ assert(calc()); vector<bool> res(v); rep(i,v) res[i] = (graph.cmp[i]>graph.cmp[v+i]); return res; } }; int main() { int n; cin >>n; vector<vector<string>> s(n); rep(i,n) { string x,y; cin >>x >>y; s[i].pb(x.substr(0,3)); s[i].pb(x.substr(0,2)+y.substr(0,1)); } TwoSat solver(n); rep(i,n)rep(j,i) { rep(ii,2)rep(jj,2) { if(s[i][ii] == s[j][jj]) solver.add_clause(i,ii,j,jj); } if(s[i][0]==s[j][0]) { solver.add_clause(i,true,j,false); solver.add_clause(j,true,i,false); } } string ans = "NO"; vector<string> v; if(solver.calc()) { ans = "YES"; vector<bool> literals = solver.get_literals(); rep(i,n) { int idx = 1; if(literals[i]) idx = 0; v.pb(s[i][idx]); } } cout << ans << endl; for(string w:v) cout << w << endl; return 0; }