スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Yandex.Algorithm 2011 Qualification 1

2011/05/04 14:00~16:00 (JST)
Codeforces で開催された Yandex.Algorithm 2011 Qualification 1 の参加記録

Yandex というのは、ロシアの大手検索エンジンらしい。

Tags : プログラミング Codeforces

結果

A. WA, AC (00:32)
B. WA
C. WA, AC (01:47)
D. -
E. -
Hacks : +0 (0/0)
Standing : 486/1628
Rating : 18431737


問題

問題セットの原文はここを参照。

A. Plug-in
与えられる文字列から、
「連続する 2 文字が同じ文字であれば、その 2 文字を削除する」
という操作を行えるだけ行ったあとに得られる文字列を答えよ。

1 ≦ 文字列長 ≦ 2・105

B. Sequence Formatting
正整数,","," ","..." からなる文字列が与えられる。
次のルールに従って、文字列を整形せよ。

- "," のあとにはちょうど 1 つの " " がある。ただし、"," が行末にある場合は " " はない。
- "..." の前にはちょうど 1 つの " " がある。ただし、"..." が行頭にある場合は " " はない。
- 2 つの数が " " だけで区切られている場合、その間の " " は 1 文字だけ。
- 上記の 3 条件に当てはまらない " " はない。

1 ≦ 文字列長 ≦ 255

C. Average Score
n 個の整数 ti と、整数 a, b が与えられる。

ti から a 個選んで、それらの平均を取ったものを x1 とする。
上で選ばなかった b 個の平均を取ったものを x2 とする。

x1 + x1 を最大化するような選び方を求めよ。
そのような求め方が複数ある場合は、出力する文字列の辞書式最小のものを答えよ。

2 ≦ n ≦ 105
1 ≦ a. b ≦ n-1; a + b = n
1 ≦ ti ≦ 5

D. Polycarp's Picture Gallery
m 個のアルバムに ai 枚ずつ写真が入っている。
この写真の中から n 枚を選んで、円筒形のギャラリーに 1 列に飾りたい。
このとき、隣り合う写真は別のアルバムから選んだものであるようにしたい。

条件に合う写真の並べ方を答えよ。
答えが複数ある場合はどれを答えてもいい。
答えがない場合は -1 を出力せよ。

1 ≦ m ≦ 40
1 ≦ n ≦ 1000
1 ≦ ai ≦ 1000

E. Pairs
n 人の男女がいる。各人は自分以外の 1 人を親友だと思っている。
A が B の親友であるからといって、B が A の親友であるとは限らない。
「A が B の親友である」 というペアをいくつか作る。 (ただし、各人は高々 1 組のペアに属する)
作れるペアの最大数と、具体的なペアを答えよ。
答えが複数あるときは、男女のペアの数を最大化するようにせよ。
それでも答えが複数あるときは、どれを答えてもよい。

2 ≦ n ≦ 105

解答

言語は C++。テンプレはここを参照。

A.
int main(){
string s; cin>>s; s="@"+s;
int n=s.length();
static int prev[200011],next[200011];
rep(i,n+10) prev[i]=i-1, next[i]=i+1;

for(int i=0;i<n;){
if(s[i]==s[next[i]]){
next[prev[i]]=next[next[i]];
prev[next[next[i]]]=prev[i];
i=prev[i];
}
else i=next[i];
}

for(int i=0;i<n;i=next[i]){
if(i>0) cout<<s[i];
}
cout<<endl;

return 0;
}

O(n2) だと遅いので、O(n) 解法を考えないといけない。
文字列を削除するのではなく、隣接リストのように各文字の前後の文字の位置を覚えておくようにした。
隣接する同じ文字列が見つかったときは、リストをつなぎ変えて、今見ている位置の 1 つ前から調べなおす。

本当は、スタックを使うのがシンプルで簡単に書ける。
なんで思いつかなかったんだろう。

B. (時間外)
bool isSpace(char c){ return c==' '; }

int main(){
string s; getline(cin,s);
int n=s.length();

rep(i,n) if(isdigit(s[i])) {
for(int j=i+1;j<n;j++) if(s[j]!=' ') {
if(j>i+1 && isdigit(s[j])) s[j-1]='|';
break;
}
}

s.erase(remove_if(s.begin(),s.end(),isSpace),s.end());

n=s.length();
rep(i,n) if(s[i]=='|') s[i]=' ';

int dots=0;
bool comma=false;
rep(i,n){
if(s[i]=='.'){
if(i>0 && dots==0 && !comma) cout<<' ';
cout<<'.';
}
else if(s[i]==','){
cout<<',';
if(i<n-1) cout<<' ';
}
else cout<<s[i];

comma=(s[i]==',');
dots=(s[i]=='.'?(dots+1)%3:0);
}
cout<<endl;

return 0;
}

がんばって実装するだけ。
実装方法は人それぞれ。

最初に、数と数の間の空白だけを残して、それ以外の空白を取り除いた。
その後は、前から見ていって、適宜、空白を追加していった。

watashi さんの正規表現による解法が美しい。

C.
bool cmp1(const pii &a,const pii &b){
if(a.first!=b.first) return a.first>b.first;
return a.second<b.second;
}

bool cmp2(const pii &a,const pii &b){
if(a.first!=b.first) return a.first>b.first;
return a.second>b.second;
}

int n,a,b;
pii f[100000];

vi solve(int id){
if(id==0) sort(f,f+n,cmp1);
else sort(f,f+n,cmp2);

static bool flg[100000];
rep(i,n) flg[i]=false;
rep(i,min(a,b)) flg[f[i].second]=true;

vi ans(n);
if(a<b){ // flg==true <=> assign 1
rep(i,n) ans[i]=(flg[i]?1:2);
}
else{ // flg==true <=> assign 2
rep(i,n) ans[i]=(flg[i]?2:1);
}

return ans;
}

int main(){
scanf("%d%d%d",&n,&a,&b);
rep(i,n){
int tmp; scanf("%d",&tmp);
f[i]=mp(tmp,i);
}

if(a==b){
rep(i,a) printf("1 ");
rep(i,b) printf("2%c",i<b-1?' ':'\n');
return 0;
}

vi ans[2];
ans[0]=solve(0);
ans[1]=solve(1);

rep(i,n){
if(ans[0][i]!=ans[1][i]){
if(ans[0][i]>ans[1][i]){
swap(ans[0],ans[1]);
}
break;
}
}

rep(i,n) printf("%d%c",ans[0][i],i<n-1?' ':'\n');

return 0;
}

a < b のときを考える。

a のグループに入る数を t1, ..., ta
b のグループに入る数を ta+1, ..., tn
とすると、平均の和は
( t1 + ... + ta )/a + ( ta+1 + ... + tn )/b
となる。
a < b だから、a のグループに含まれる数のほうが、割り算で小さくなりにくい。
なので、直感的には、できるだけ大きい数を a のグループに集めるのがよさそうである。

実際、これは正しくて、大きい順に a 個を a のグループに割り当てるのが最適になる。
ただし、辞書式最小のものを求めないといけないことに注意。 ( これが結構ややこしい

b < a のときも同様にしてわかる。

a = b のときは、どのように分けても平均の和は等しくなるので、左から a 個を a のグループに割り当てるのが辞書式最小。

D. (時間外)
int main(){
int n,m; scanf("%d%d",&n,&m);
int a[40];
rep(i,m) scanf("%d",a+i);

pii ord[40];
rep(i,m) ord[i]=mp(-a[i],i);
sort(ord,ord+m);

int ans[1000],pos=0;
memset(ans,-1,sizeof ans);
rep(k,2) for(int i=k;i<n;i+=2) {
int now,j;
for(j=0;j<m;j++){
now=ord[pos].second;
int prev=ans[(i-1+n)%n],next=ans[(i+1)%n];
if(a[now]>0 && now!=prev && now!=next) break;
pos=(pos+1)%m;
}
if(j==m){ puts("-1"); return 0; }
ans[i]=now;
a[now]--;
}

rep(i,n) printf("%d%c",ans[i]+1,i<n-1?' ':'\n');

return 0;
}

[ 2011/05/05 追記 ]
直感で正しいと思ったコードを書いたら通ったので、証明はできてない。

写真が多く入っているアルバムから順に、ギャラリーに貼っていく。
貼る順番は、まず偶数番目の位置をすべて貼ってから奇数番目の位置に貼る。
( たとえば n = 7 のときは、0 2 4 6 1 3 5 の順で貼るということ )

途中でどの写真も貼れなくなったら、解なし。

E. (時間外)
struct Edge{
int u,v;
Edge(){}
Edge(int U,int V):u(U),v(V){}
};

typedef pii Result;
#define num first
#define good second
Result &operator+=(Result &r,const Result &s){ r.num+=s.num; r.good+=s.good; return r; }
Result &operator-=(Result &r,const Result &s){ r.num-=s.num; r.good-=s.good; return r; }
Result operator+(const Result &r,const Result &s){ Result t=r; return t+=s; }
Result operator-(const Result &r,const Result &s){ Result t=r; return t-=s; }

vvi adj;
int n,sex[100000];

pair< vvi,vector<Edge> > decompose(){
static bool visited[100000];
fill(visited,visited+n,false);

vvi comps;
vector<Edge> edges;
rep(i,n) if(!visited[i]) {
vi comp;
Edge e;
queue<pii> qu; qu.push(mp(i,-1)); visited[i]=true;
while(!qu.empty()){
pii a=qu.front(); qu.pop();
int u=a.first,prev=a.second;
comp.pb(u);
rep(j,adj[u].size()){
int v=adj[u][j];
if(v!=prev){
if(!visited[v]){ qu.push(mp(v,u)); visited[v]=true; }
else e=Edge(u,v); // an edge which is used in the cycle
}
}
}
comps.pb(comp);
edges.pb(e);
}
return mp(comps,edges);
}

Result dp[2][100000];
int match[100000];
short path[2][100000];

Result dfs0(int u,int parent);
Result dfs1(int u,int parent);

// node u is used to matching
Result dfs0(int u,int parent){
if(~dp[0][u].num) return dp[0][u];
if(adj[u].size()==0 || (adj[u].size()==1 && adj[u][0]==parent)){ // u is leaf
return dp[0][u]=Result(0,0);
}

Result ans,ans2;
int x=-1;
rep(i,adj[u].size()){
int v=adj[u][i];
if(v!=parent){
Result tmp0=dfs0(v,u),tmp1=dfs1(v,u);
ans+=max(tmp0,tmp1);
if(tmp1<tmp0) path[0][v]=0;
else path[0][v]=1;

Result dif=Result(1,sex[u]==sex[v]?0:1)+min(tmp1-tmp0,Result(0,0));
if(x==-1 || ans2<dif){
ans2=dif;
x=v;
}
}
}
path[0][x]=1;
match[u]=x;

return dp[0][u]=ans+ans2;
}

// node u is not used to matching
Result dfs1(int u,int parent){
if(~dp[1][u].num) return dp[1][u];
if(adj[u].size()==0 || (adj[u].size()==1 && adj[u][0]==parent)){ // u is leaf
return dp[1][u]=Result(0,0);
}

Result ans;
rep(i,adj[u].size()){
int v=adj[u][i];
if(v!=parent){
Result tmp0=dfs0(v,u),tmp1=dfs1(v,u);
ans+=max(tmp0,tmp1);
if(tmp1<tmp0) path[1][v]=0;
else path[1][v]=1;
}
}
return dp[1][u]=ans;
}

void constructMatchings(int u,int parent,int type,vector<Edge> &matches){
if(type==0) matches.pb(Edge(u,match[u]));

rep(i,adj[u].size()){
int v=adj[u][i];
if(v!=parent){
if(path[type][v]==0) constructMatchings(v,u,0,matches);
else constructMatchings(v,u,1,matches);
}
}
}

void deleteNode(int u){
rep(i,adj[u].size()){
int v=adj[u][i];
adj[v].erase(find(all(adj[v]),u));
}
adj[u].clear();
}

void deleteEdge(const Edge &e){
int u=e.u,v=e.v;
adj[u].erase(find(all(adj[u]),v));
adj[v].erase(find(all(adj[v]),u));
}

pair< Result,vector<Edge> > solve(const vi &V,const Edge &e){
int u=e.u,v=e.v;
deleteEdge(e);
Result tmp0=dfs0(u,-1);
rep(k,2) rep(i,V.size()) dp[k][V[i]]=Result(-1,0);
Result tmp1=dfs1(u,-1);

Result r1=max(tmp0,tmp1);
vector<Edge> matches;
if(tmp0<tmp1) constructMatchings(u,-1,1,matches);
else constructMatchings(u,-1,0,matches);

vi cand=adj[v];
vector<pii> res;
deleteNode(v);
rep(k,2) rep(i,V.size()) dp[k][V[i]]=Result(-1,0);
Result r2=dfs1(u,-1)+Result(1,sex[u]==sex[v]?0:1);
rep(i,cand.size()){
int x=cand[i];
if(dp[1][x].num==-1){ // not visited sub-root
Result t0=dfs0(x,-1),t1=dfs1(x,-1);
r2+=max(t0,t1);
if(t0<t1) res.pb(mp(x,1));
else res.pb(mp(x,0));
}
}

if(r1<r2){
matches.clear();
constructMatchings(u,-1,1,matches);
rep(i,res.size()){
constructMatchings(res[i].first,-1,res[i].second,matches);
}
matches.pb(Edge(u,v));
r1=r2;
}

return mp(r1,matches);
}

int main(){
scanf("%d",&n);
adj.resize(n);
rep(u,n){
int v; scanf("%d%d",&v,sex+u);
v--;
adj[u].pb(v);
adj[v].pb(u);
}

pair< vvi,vector<Edge> > res=decompose();
vvi &comps=res.first;
vector<Edge> &edges=res.second;

rep(k,2) rep(u,n) dp[k][u]=Result(-1,0);
memset(match,-1,sizeof match);
memset(path,-1,sizeof path);

Result ans;
vector<Edge> matches;
rep(i,comps.size()){
pair< Result,vector<Edge> > tmp=solve(comps[i],edges[i]);
ans+=tmp.first;
matches.insert(matches.end(),all(tmp.second));
}

printf("%d %d\n",ans.num,ans.good);
rep(i,matches.size()) printf("%d %d\n",matches[i].u+1,matches[i].v+1);

return 0;
}

[ 2011/05/08 追記 ]

二部グラフの最大マッチングの辺に重みがあるバージョンだけど、|V| が大きいので、その解法では間に合わない。
グラフの形の特殊性を利用した、効率の良い解法が必要。

maksay さんと Rizvanov さんのコメントとソースコードを参考にした。
方針が分かってからも書き上げるのにかなり時間がかかった。

親友が 1 人という制約から、グラフの各連結成分は、閉路をちょうど 1 つだけもつことがわかる。
この各連結成分に対して、ペアの数を最大化すればよい。
具体的には、閉路上にある辺 e (どれでもいい) を 1 つ指定する。
連結成分から e を削除したグラフは木になることに注意。
e をペアに使う場合と使わない場合それぞれについて、最大ペア数を調べて大きいほうを取ればよい。
これは DP で調べることができる。

コード中の DP は
dp[0][u] := 頂点 u を根とした部分木について、u をペアに使わないときの最大ペア数
dp[1][u] := 頂点 u を根とした部分木について、u をペアに使うときの最大ペア数
とした。

感想

A のバグ取りではまってしまってかなり時間を使ってしまった。
結局、配列の範囲を間違えてただけだった。
スタック解法を思いついていればこんなことにはならなかったので、やはり能力不足である。

その次の B は、10 分ちょっとで書き上げられたものの、連続する数の条件を読み飛ばしていて WA.

C に関しては、最初、Greedy でできるという考えはあったのに、一旦捨ててしまったのが悪かった。
途中、ずっと DP 解法を考えていて、結構はまってしまった。
見た瞬間解けてもいい問題だったと思う。

結局、A と C に時間を使いすぎて、D は問題文も読めなかった。
手間取った理由はひとえに能力不足なので、練習による能力向上が望まれる。



自分で書いててなんだけど、変な文章だなぁ。
スポンサーサイト

コメントの投稿

非公開コメント

No title

Aの問題を読み間違えてハマってしまいました(笑

連続した文字はすべて消えると思い込んでましたが、よく問題を読むとpairだったのですね。。
私は、queueで実装しました。

本戦出場おめでとうございます。

Re: No title

返事が遅くなって申し訳ないです。

queue でどうやって実装するんだろうと思って、ソースコードを見てみました。
なるほど、確かに queue でもできますね。先に全部 queue に入れておくんですね。
それもうまい方法だと思います。

私も、最初は連続する全部を消すのかと思ってたんですが、それだと最後のサンプルが合わなかった気がします。
プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。