スポンサーサイト

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

Codeforces Beta Round #71

2011/05/01 0:00~2:00 (JST)
Codeforces Beta Round #71 の参加記録

writer は ir5 さんと rng_58 さん。
Codeforces で日本人 writer は多分今回が初。

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

結果

A. 2WA, AC (00:15)
B. AC (00:29)
C. WA, AC (01:28)
D. -
E. -
Hacks : -50 (0/1)
Standing : 179/1183
Rating : 18071843


問題

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

A. Bus Game
百円玉が x 枚、十円玉が y 枚つまれた山がある。
これを使って、二人でゲームをする。
ゲームはターン制で行われる。
各ターンにおいて、プレイヤーは山からちょうど 220 円を取る。
- 先手は百円玉をできるだけ多く取るような取り方をする。
- 後手は十円玉をできるだけ多く取るような取り方をする。
先に 220 円を取ることができなくなったプレイヤーの負け。
どちらが勝つか?

0 ≦ x, y ≦ 106

B. Colorful Field
m × n マスの畑に作物を植える。
畑の中で k 個のマスには作物を植えることができない。
左から右、上から下にかけて、Carrot, Kiwi, Grape, Carrot, ... の順で作物を植えていく。(問題文の図参照)

「マス (i, j) には何が植えられているか?」 という t 個のクエリを処理せよ。

1 ≦ m, n ≦ 4・104
1 ≦ k, t ≦ 103

C. Beaver
文字列 s と、n 個の禁止ワード bi が与えられる。
すべての禁止ワードを含まないような s の部分文字列の中で、最長のものを求めよ。
答えが複数あるときは、どれを答えてもよい。

1 ≦ s の長さ ≦ 105
1 ≦ n ≦ 10
1 ≦ bi の長さ ≦ 10

D.

E.

解答

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

A.
int main(){
int x,y; scanf("%d%d",&x,&y);
int i;
for(i=0;;i=1-i){
if(i==0){
if (x>=2 && y>= 2) x-=2, y-=2;
else if(x>=1 && y>=12) x-=1, y-=12;
else if(x>=0 && y>=22) y-=22;
else break;
}
else{
if (x>=0 && y>=22) y-=22;
else if(x>=1 && y>=12) x-=1, y-=12;
else if(x>=2 && y>= 2) x-=2, y-=2;
else break;
}
}
puts(i?"Ciel":"Hanako");

return 0;
}

問題文どおりにシミュレーションすればいい。
x, y が小さいので、線形時間で間に合う。

B.
int main(){
const char *crop[3]={"Carrots","Kiwis","Grapes"};

int m,n,nw,nq; scanf("%d%d%d%d",&m,&n,&nw,&nq);
set<int> waste[40000];
rep(i,nw){
int x,y; scanf("%d%d",&y,&x);
x--, y--;
waste[y].insert(x);
}

int hd[40000];
for(int i=0,tmp=0;i<m;i++){
hd[i]=tmp;
tmp=(tmp+(n-waste[i].size()))%3;
}

rep(i,nq){
int x,y; scanf("%d%d",&y,&x);
x--, y--;
if(waste[y].count(x)==1) puts("Waste");
else{
int tmp=distance(waste[y].begin(),waste[y].lower_bound(x));
tmp=x-tmp;
tmp=(hd[y]+tmp)%3;
puts(crop[tmp]);
}
}

return 0;
}

各行の先頭で、次に何を植えるかを前計算しておく。
こうしておけば、各クエリは列についてだけ考えればよい。
聞かれているマスより左に waste なマスがいくつあるかが分かればいい。これは二分探索すれば対数時間でできる。

という風にやったのだけど、二次元で考える必要はどこにもなくて、1 次元の畑だと考えれば二分探索するだけだった。
Hack してるときに人のコードを見て気付いた。

C.
vi findAllMatches(const string &s,const string &t){
int m=s.length(),n=t.length();
vi ans;
rep(i,m-n+1) if(s.substr(i,n)==t) ans.pb(i);
return ans;
}

int main(){
int n;
string msg,sub[10]; cin>>msg>>n;
int len=msg.length();
rep(i,n) cin>>sub[i];

vi pos[10];
rep(i,n) pos[i]=findAllMatches(msg,sub[i]);

vector<pii> l;
rep(i,n) rep(j,pos[i].size()) {
l.pb(mp(pos[i][j],pos[i][j]+sub[i].length()-1));
}
l.pb(mp(len,len));
sort(l.begin(),l.end());
l.erase(unique(l.begin(),l.end()),l.end());

int m=l.size();
vi rmin(m);
rmin[m-1]=l[m-1].second;
for(int i=m-1;i>0;i--) rmin[i-1]=min(rmin[i],l[i-1].second);

int ans=0,ans2=0;
rep(i,len){
int j=lower_bound(l.begin(),l.end(),mp(i,0))-l.begin();
int tmp=rmin[j]-i;
if(ans<tmp){
ans=tmp;
ans2=i;
}
}

printf("%d %d\n",ans,ans2);

return 0;
}

まず、禁止ワードが s のどこにマッチするのかを全部列挙した。
Aho-Corasick を使えば高速にできるけど、この問題の入力サイズなら愚直にやってもいい。

そして、s の各文字 s[i] について、s[i] を左端とした (禁止ワードを含まない) 最長部分文字列の右端がどこかになるを調べた。
これは、「s[i] かそれより右から始まる禁止ワードの中で、一番はやく終わるものの位置」 の 1 文字前になる。
この位置を高速に求めるため、二分探索と簡単な DP をした。
各 s[i] に対して得られた部分文字列の中で最長のものが答え。


たとえば
s = abcdefg, b1 = abc, b2 = cdefg, b3 = def
のとき、
s[0] = a を左端とする部分文字列は ab.
s[1] = b 〃 bcde.
s[2] = c 〃 cde.
s[3] = d 〃 de.
s[4] = e 〃 efg.
s[5] = f 〃 fg.
s[6] = g 〃 g.
となるので、答えは bcde.

D.



E.



感想

100 位台をとれれば、安定してオレンジにいられるようだ。
次回もこの調子で C を確実に解いていきたい。

A.
問題の読解ミスで、2WA した上に 15 分も時間を使ってしまった。
まぁ、これは仕方ない。

B.
問題を理解してすぐに解法が浮かんだ。
良いアルゴリズムではなかったものの、ほとんどバグなしで書き上げられた。

C.
多分、もっとシンプルな解法がある。あとで writer の解説を読んでおく。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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