スポンサーサイト

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

Codeforces Beta Round #75

2011/06/21 0:00~2:00 (JST)
Codeforces Beta Round #75 (Div.1 Only) の参加記録

Div.2 Only とは、 A, B, C の 3 問が重複。

Tags : プログラミング Codeforces 未解決
結果

A. AC (00:21)
B. AC (01:05)
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 190/409
Rating : 18471813


問題

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

A. Newspaper Headline
アルファベット小文字からなる 2 つの文字列 s1, s2 が与えられる。
s1 を n 個つなげた文字列からいくつかの文字を削除して s2 を作りたい。
ありうる n の最小値はいくつか?
そのような n が存在しないときは -1 と答えよ。

1 ≦ |s1| ≦ 104
1 ≦ |s2| ≦ 106

B. Queue
長さ n の数列 {an} がある。
各番号 i について、
ai > aj となる aj (j > i) のうち、j が最大のものを求めよ。
( 正確には、そのときの i と j の間にいくつの番号があるかを答えよ。 )
そのような j が存在しない場合は -1 と答えよ。

2 ≦ n ≦ 105
1 ≦ ai ≦ 109

C. Ski Base
頂点数 n の無向グラフ G=(V,E) が与えられる。
最初、グラフに辺はない。
グラフに合計 m 本の辺を 1 本ずつ追加していく。
辺を追加したあとの各状態において、E の部分集合 S で次の条件を満たすものの個数を求めよ。

・ G の閉路で、同じ辺を高々 1 回通るものを Track と呼ぶ。 (∞ のように、同じ頂点は複数回通ってもいい)
・ S は 1 個以上の Track に分解できる。 (つまり、S の任意の辺はちょうど 1 つの Track に含まれる)

2 ≦ n ≦ 105
1 ≦ m ≦ 105

D.

E. Igloo Skyscraper
n 本の塔がある。
塔は建設中であり、時刻 t における塔 i の高さは ai + bi t である。

次の q 個のクエリを処理せよ。
クエリは (l, r, t) の 3 つのパラメータからなり、
「 塔 l, l+1, ..., r の中で、時刻 t において高さ最大のものを求める 」
ことを意味する。

1 ≦ n, q ≦ 105
1 ≦ ai, bi ≦ 109
0 ≦ t ≦ 106
すべて整数

解答

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

A.
int main(){
string s1,s2; cin>>s1>>s2;
int len1=s1.length(),len2=s2.length();

vector<int> pos[128];
rep(i,len1) pos[s1[i]].push_back(i);
rep(i,len2) if(pos[s2[i]].size()==0) {
cout<<-1<<endl;
return 0;
}

int ans=1;
for(int i=0,j=0;i<len2;){
int k=lower_bound(all(pos[s2[i]]),j)-pos[s2[i]].begin();
if(k==pos[s2[i]].size()){
j=0;
ans++;
}
else{
j=pos[s2[i]][k]+1;
i++;
}
}

cout<<ans<<endl;

return 0;
}

すぐに思いつくのは、小さい n から順に LCS を求めるという方法だけど、文字列が長いのでそれだと遅すぎる。

そこで、s1 中の各アルファベットの出現位置を覚えておいて、次の文字の場所を二分探索で高速に検索できるようにした。
これで間に合う。

ちなみに、ほとんどの人は、次の文字の場所をテーブルで全部持っておいて、O(1) で参照できるようにしていた。

B.
int main(){
int n; scanf("%d",&n);
static int a[100000];
rep(i,n) scanf("%d",a+i);

deque<pii> dq;
static int ans[100000];
for(int i=n-1;i>=0;i--){
deque<pii>::iterator it=lower_bound(all(dq),mp(a[i],-1));
if(it==dq.begin()) ans[i]=-1;
else{
--it;
ans[i]=it->second-i-1;
}
if(dq.empty() || a[i]<dq.front().first){
dq.push_front(mp(a[i],i));
}
}
rep(i,n) printf("%d%c",ans[i],i<n-1?' ':'\n');

return 0;
}

数列を後ろから前に見ていって、リストの最初に順番に追加していく。
リストのデータ構造には deque を使った。
今見ている数より後ろにより小さい数があるときは、今見ている数が使われることはないので、リストに追加しない。
こうすれば、リストの中身は単調 (増加) になるので、目的の番号を求めるのに二分探索が使える。

実は、ai の値でソートしてごにょごにょするという別解があって、そっちのほうがシンプルで美しい。

C. (時間外)
const int M=1000000009;

class UnionFind{
vector<int> a;
public:
UnionFind(int n):a(n,-1){}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y){ a[x]+=a[y]; a[y]=x; }
}
};

int main(){
int n,m; scanf("%d%d",&n,&m);
int ans=1;
UnionFind uf(n);
rep(i,m){
int a,b; scanf("%d%d",&a,&b);
a--, b--;
if(uf.find(a)==uf.find(b)) ans=2*ans%M;
else uf.unite(a,b);
printf("%d\n",ans-1);
}

return 0;
}

コンテストが終わってから解いたけど、なぜこうなるのかはまだ理解できてない。
連結成分を Union-Find で管理して、すでに連結している頂点間に辺が張られたら、答えを 2 倍する。

Problem Setter の解説を読むと、接続行列の Rank がどうとからしいのだけど、ちょっと読んだくらいではさっぱり分からなかった。
興味深い内容なので、いつかしっかり読み直したい。

ただ、これほどシンプルな規則であれば、たくさんの例で実験していればコンテスト中でも規則に気付けていたはず。

D.



E. (時間外)
typedef pair<ll,int> pli;

int n;
ll a[101000],b[101000];

class Point{
public:
double x;
int i,j; // i : 交点の左に接続している直線の番号, j : 交点の右に接続している直線の番号
Point(double X,int I,int J):x(X),i(I),j(J){}
bool operator<(const Point &p)const{ return x<p.x; }
};

bool cmp(int i,int j){ return b[i]!=b[j] ? b[i]<b[j] : a[i]>a[j]; }

// i 番目の直線と j 番目の直線の交点の x 座標を求める
double crosspoint(int i,int j){
return (double)(a[j]-a[i])/(b[i]-b[j]);
}

class Polyline{
vector<Point> q;
public:
void make(int l,int r){
int n=r-l;
vector<int> p(n);
rep(i,n) p[i]=l+i;
sort(p.begin(),p.end(),cmp);

// 平行な直線の中で a (y 切片) が最大のものだけを残す
vector<int> tmp;
rep(i,n) if(i==0 || b[p[i-1]]<b[p[i]]) tmp.push_back(p[i]);
p=tmp;

q.push_back(Point(-1e60,-1,p[0])); // 左端の番兵
for(int j=1;j<p.size();j++){
int pi=q.back().j;
double x=crosspoint(pi,p[j]);
while(!q.empty() && x<q.back().x){
q.pop_back();
pi=q.back().j;
x=crosspoint(pi,p[j]);
}
q.push_back(Point(x,pi,p[j]));
}
q.push_back(Point(1e60,p.back(),-1)); // 右端の番兵
}

pli query(int t){
int i=lower_bound(q.begin(),q.end(),Point(t,-1,-1))->i;
return make_pair(a[i]+b[i]*t,i);
}
};

int main(){
int nq; scanf("%d%d",&n,&nq);
rep(i,n) scanf("%d%d",a+i,b+i);

int sqn=(int)(sqrt(n)+1);
Polyline pl[320];
rep(i,sqn) pl[i].make(sqn*i,sqn*(i+1));

while(nq--){
int l,r,t; scanf("%d%d%d",&l,&r,&t); l--;

pli ans(-1,-1);
rep(i,sqn){
int L=sqn*i,R=sqn*(i+1);
// バケットがクエリの区間に含まれていないとき
if(r<L || R<=l) continue;
// バケットがクエリの区間に完全に含まれているとき
else if(l<=L && R<=r){
ans=max(ans,pl[i].query(t));
}
// バケットがクエリの区間に部分的に含まれているとき
else{
rep(j,sqn) if(l<=L+j && L+j<r) {
ans=max(ans,make_pair(a[L+j]+b[L+j]*t,L+j));
}
}
}
printf("%d\n",ans.second+1);
}

return 0;
}

[ 2011/08/13 追記 ]

E にしては正解数多めだったので、Editorials を参考にして解いた。
難しかった。

Segment Tree でも解けるけど、Editorials にしたがってバケット法 (平方分割) で解いた。

塔の高さ y は t の一次関数になっているので、t-y グラフで表せば直線になる。
以下、n 本の直線を扱うものとして話を進める。

まず、直線を √n 個のバケットに分ける。
各バケットについて、t が与えられたときに、どの直線が最大の y をもつかを知りたい。


図を描くと明らかなように、バケットに含まれる直線たちの上側エンベロープを考えればいい。
これは折れ線になる。
上側エンベロープを求めるのは、直線を傾きの小さい順でソートして、2 直線の交点を求めながらごにょごにょすればいい。
この部分の計算量は、ソートが支配的で O(√n log √n) (= O(√n log n)) になる。
( 文章で説明するのが大変。蟻本にも載っていた気がする )

各バケットについて、あらかじめ上側エンベロープを求めておく。
すると、1 つのバケット内での y 最大の直線は二分探索を使えば O(log √n) で計算できる。

√n 個のバケットを作っていたので、クエリ 1 つあたりの計算量は O(√n log √n) となり、これで間に合う。


上で Segment Tree でも解けると書いた。
方針は平方分割のときと同じだけど、この方針では Segment Tree を構成するときに 2 つのエンベロープをマージして新たなエンベロープを作る処理が必要になり、さらに複雑になる。
その点、平方分割だと直線たちをマージするだけでいいので、幾分かは楽。

感想

B で大ポカしたとはいえ、次で挽回しないとオレンジから落ちてしまう。

A.
方針を立てるまでに時間がかかりすぎ。
見た瞬間に解けてもいい問題。

B.
「自分より後ろにあって、自分より小さい数の個数を数える問題」 だと誤読して、それだとサンプルが合わないので 30 分くらい迷走していた。
駄目元で clar を投げてみたら、とても丁寧な回答が返ってきてなんとか解くことができた。

C.
提出数も少なかったので、どうせ解けないだろうと思ってしまったのが悪かった。
まったく手がかりがつかめなくても、具体例を試すことはできるし、それで何かに気付くかもしれない。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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