スポンサーサイト

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

VK Cup 2012 Qualification Round 2

2012/03/09 ~ 03/10
VK Cup 2012 Qualification Round 2 の参加記録

Qual Round 1 に出損ねたので最後のチャンスだった。
眠くて途中で切り上げたけどぎりぎり通過できてよかった。

Tags : プログラミング Codeforces

結果

A. pretest WA, WA
B. AC
C. pretest WA
D. -
E. AC
Standing : 768/3406
Unrated


問題

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

A. Friends or Not

ある時刻にある人がある人にメッセージを送った、というログが n 個与えられる。
二人が相互に時間間隔 t でメッセージをやりとりしていて、かつ 0 < t ≦ d となる t が一つ以上あれば、二人は友人である。
すべての友人のペアを出力せよ。

1 ≦ n, d ≦ 1000

B. Matchmaker

n 本のマーカーと m 本のキャップがあり、それぞれ直径と色で特徴付けられている。
直径が一致するペアは closed であるという。
直径と色が共に一致するペアは beautiful であるという。
マーカーとキャップのマッチングを作り closed の個数を最大化せよ。
その上で beautiful の個数を最大化せよ。

1 ≦ n, m ≦ 10^5

C. String Manipulation 1.0

文字列 s ( 入力された文字列を k 回繰り返して得られる文字列 ) に対して
" s の先頭から p 回目に現れる文字 c を消す "
という操作を n 回繰り返してできる文字列を答えよ。

|s| ≦ 200000
0 ≦ n ≦ 200000
各 (p, c) の組に対応する s の文字が存在する

D. Palindrome pairs

文字列 s[1..n] に対して
" 1 <= a <= b < x <= y <= n かつ s[a..b] と s[x..y] は回文 "
をみたす組 (a, b, x, y) の個数を数えよ

n ≦ 2000

E. Zebra Tower

色とサイズで特徴付けられる立方体が n 個ある。
ちょうど 2 色の立方体だけを使って、それらを色が交互になるように積んでいく。
立方体のタワーの高さを最大化し、そのときのタワーを求めよ。
解が複数あるときはどれを答えてもよい。

2 ≦ n ≦ 10^5
少なくとも 2 色の立方体が存在

解答

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

A.
int main(){
int n,d; cin>>n>>d;
set< pair<string,string> > ans;
map< pair<string,string>,vector<int> > logs;
rep(_,n){
string s1,s2;
int t; cin>>s1>>s2>>t;
if(logs.count(make_pair(s2,s1))>0){
vector<int> t_pre=logs[make_pair(s2,s1)];
bool ok=false;
rep(i,t_pre.size()) if(0<t-t_pre[i] && t-t_pre[i]<=d) ok=true;
if(ok){
ans.insert(make_pair(min(s1,s2),max(s1,s2)));
}
}
logs[make_pair(s1,s2)].push_back(t);
}

cout<<ans.size()<<endl;
set< pair<string,string> >::iterator it;
for(it=ans.begin();it!=ans.end();++it) cout<<it->first<<' '<<it->second<<endl;

return 0;
}

入力サイズが小さいので全部試せばいい。
差が 0 のときは友人とみなさないので、最新の時刻だけ保存していると WA になる。

B.
int main(){
int n,m; scanf("%d%d",&n,&m);
static int mar[1000][1000],cap[1000][1000];
rep(i,n){
int x,y; scanf("%d%d",&x,&y); x--; y--;
mar[x][y]++;
}
rep(i,m){
int x,y; scanf("%d%d",&x,&y); x--; y--;
cap[x][y]++;
}

int ans1=0;
rep(x,1000) rep(y,1000) {
int c=min(mar[x][y],cap[x][y]);
mar[x][y]-=c;
cap[x][y]-=c;
ans1+=c;
}
int ans2=0;
rep(y,1000){
int mar_sum=0,cap_sum=0;
rep(x,1000){
mar_sum+=mar[x][y];
cap_sum+=cap[x][y];
}
ans2+=min(mar_sum,cap_sum);
}
printf("%d %d\n",ans1+ans2,ans1);

return 0;
}

beautiful のものを先に決めてしまって、残った中で closed を最大化する。

C.
const int N_MAX=200000;

template<class T>
class Fenwick_tree{
int n;
T a[N_MAX];

public:
void build(int n){
this->n=n;
rep(i,n) a[i]=0;
}

void add(int i,T v){
for(;i<n;i|=i+1) a[i]+=v;
}

T sum(int i,int j){
if(i==0){
T s=0;
for(;j>=0;j=(j&(j+1))-1) s+=a[j];
return s;
}
return sum(0,j)-sum(0,i-1);
}
};

int main(){
int k,q;
string s,s_tmp; cin>>k>>s_tmp>>q;
rep(i,k) s+=s_tmp;

int len=s.length();
vector<int> pos[26];
rep(i,len) pos[s[i]-'a'].push_back(i);

static Fenwick_tree<int> F[26];
rep(c,26) F[c].build(pos[c].size());

static bool del[200000];
rep(_,q){
int p;
char c; cin>>p>>c; p--; c-='a';

int lo=p,hi=pos[c].size()-1;
while(lo<hi){
int mi=(lo+hi)/2;
if(mi-F[c].sum(0,mi)<p) lo=mi+1; else hi=mi;
}

p=lo;
F[c].add(p,1);
del[pos[c][p]]=true;
}

rep(i,len) if(!del[i]) cout<<s[i];
cout<<endl;

return 0;
}

wrong さんのコードを参考にした。

クエリ (p, c) に対して、s の何文字目を消さないといけないかという対応を効率よく更新しないといけない。
たとえば、Fenwick 木で二分探索すればうまくいく。
テストケースが弱いらしく、vector で線形時間をかけても通るとか。

D.
const int L_MAX=2000;
int rad[2*L_MAX];
void Manacher(const char *s){
int m=2*strlen(s);
for(int i=0,j=0;i<m;){
while(0<=i-j && i+j+1<m && s[(i-j)/2]==s[(i+j+1)/2]) j++;
rad[i]=j;

int k;
for(k=1;i-k>=0 && rad[i-k]<rad[i]-k;k++) rad[i+k]=rad[i-k];

i+=k;
j=(j>k?j-k:0);
}
}

int main(){
char s[2001]; gets(s);
int n=strlen(s);
Manacher(s);

// left [i] := s[i] を左端とする回文の総数
// right[i] := s[i] を右端とする回文の総数
int left[2000]={},right[2000]={};
rep(i,n){
rep(j,rad[2*i]/2+1){
left [i-j]++;
right[i+j]++;
}
rep(j,rad[2*i+1]/2){
left [i-j]++;
right[i+j+1]++;
}
}

ll ans=0;
rep(j,n) rep(i,j) ans+=(ll)right[i]*left[j];
printf("%lld\n",ans);

return 0;
}

ソースコード中にコメントで書いた二つの配列 left, right を求めるのがメイン。
これが求まれば、答えは単に二重ループして足し合わせれば求まる。
left, right は内側のループを回すのと同時に回文かどうかを判定していけば O(n^2) で計算できる。
せっかく Manacher のライブラリがあるので、コードではそれを使っている。回文かどうかの判定はしていない。

E.
struct pile{
ll h;
int color;
bool operator<(const pile &p)const{
return make_pair(h,color)<make_pair(p.h,p.color);
}
};

int main(){
int n; cin>>n;
static int color[100000];
static ll height[100000];
rep(i,n) cin>>color[i]>>height[i];

// color を座標圧縮して [0, nc) の範囲に縮める
int nc=0;
map<int,int> f_color;
rep(i,n){
if(f_color.count(color[i])==0){
f_color[color[i]]=nc++;
}
color[i]=f_color[color[i]];
}

// 同色のブロックをまとめる
static vector< pair<ll,int> > h[100000]; // (height, id)
rep(i,n) h[color[i]].push_back(make_pair(height[i],i+1));

// 同じ個数のブロックからなる "同色の山" をまとめる
static vector<pile> a[100000];
rep(c,nc){
// 大きいものから取っていったほうがいい
sort(h[c].rbegin(),h[c].rend());
ll acc=0;
rep(i,h[c].size()){
acc+=h[c][i].first;
a[i].push_back((pile){acc,c});
}
}
rep(i,n) sort(a[i].rbegin(),a[i].rend());

// 答えを計算
ll h_ans=-1;
int i1_ans,i2_ans,j1_ans,j2_ans;
rep(i,n){
// i+1 個のブロックからなる二つの山をマージした答えを探す
rep(j1,min(7u,a[i].size())) rep(j2,min(7u,a[i].size())) {
if(a[i][j1].color!=a[i][j2].color){
ll h_tmp=a[i][j1].h+a[i][j2].h;
if(h_ans<h_tmp){
h_ans=h_tmp;
i1_ans=i;
i2_ans=i;
j1_ans=j1;
j2_ans=j2;
}
}
}

// i+1 個のブロックからなる山と i+2 個のブロックからなる山をマージした答えを探す
if(i==n-1) continue;
rep(j1,min(7u,a[i].size())) rep(j2,min(7u,a[i+1].size())) {
if(a[i][j1].color!=a[i+1][j2].color){
ll h_tmp=a[i][j1].h+a[i+1][j2].h;
if(h_ans<h_tmp){
h_ans=h_tmp;
i1_ans=i;
i2_ans=i+1;
j1_ans=j1;
j2_ans=j2;
}
}
}
}

// 出力
vector<int> ans;
int color1=a[i1_ans][j1_ans].color;
int color2=a[i2_ans][j2_ans].color;
rep(i,i1_ans+1){
ans.push_back(h[color2][i].second);
ans.push_back(h[color1][i].second);
}
if(i1_ans<i2_ans){
ans.push_back(h[color2][i2_ans].second);
}

cout<<h_ans<<endl<<ans.size()<<endl;
rep(i,ans.size()){
if(i>0) cout<<' ';
cout<<ans[i];
}
cout<<endl;

return 0;
}

色が交互になるように積むのだから、タワーに使われている同じ色の立方体の個数の差は高々 1 だけ。
実装をがんばる。
詳細はコメントを参照。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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