スポンサーサイト

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

Codeforces Beta Round #58

2011/02/26 1:00~3:00 (JST)
Codeforces Beta Round #58 の参加記録。

A 問題にミスがあって、Rating がつくとかつかないとかで揉めてるみたい。

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

結果

A. Hacked,AC(352)
B. AC(708)
C. -
D. -
E. -
Hacks : 0
Standing : 224/1261


問題

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

A. A Students Dream
左手の指が al 本, 右手の指が ar の宇宙人 A、
左手の指が bl 本, 右手の指が br の宇宙人 B がいる。
「A の連続する 2 つの指の間には必ず B の指があり、B の任意の連続する 3 つの指の間には必ず A の指がある」ような手のつなぎ方 (指の交差のさせ方) があるかどうかを判定せよ。
手をつなぐのは、" A の左手と B の右手"、" A の右手と B の左手" のどちらでもいい。

B. Tyndex.Brome
ユーザが入力した文字列 s と辞書にある文字列 c との誤差 F(c) を求めよ。
F は次のアルゴリズムで定義される関数。
F <- 0
for i = 1 to |c|
if ci = sj となる j がある
then F <- F + min |i-j|
else F <- F + |c|
for end
return F

s の長さは 105 以下。
c の長さの合計 2・105 以下。

C. Inquisition
三角形が 100 個以下与えられる。
すべての三角形の論理和をとった図形の面積を求めよ。

D.
E.
読んでない。

解答

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

A.
int main(){
int al,ar,bl,br; scanf("%d%d%d%d",&al,&ar,&bl,&br);
if((-1<=br-al && br-2*al<=2)
|| (-1<=bl-ar && bl-2*ar<=2)) puts("YES");
else puts("NO");
return 0;
}

A の指の数が最大になるケースは aba..aba というケース。
B の指の数が最大になるケースは bbabba..abbabb というケース。

B.
int ulen;
string usr;
vi buc[128];

ll F(const string &dic){
int dlen=dic.length();

ll ans=0;
rep(i,min(ulen,dlen)){
char c=dic[i];
if(c==usr[i]) continue;

int cost=INF;
if(buc[c].size()==0) cost=dlen;
else{
vi::iterator it=lower_bound(buc[c].begin(),buc[c].end(),i);
if(it!=buc[c].end()) cost=min(cost,abs((*it)-i));
if(it!=buc[c].begin()) cost=min(cost,abs((*--it)-i));
}
ans+=cost;
}
for(int i=ulen;i<dlen;i++){
char c=dic[i];
int cost;
if(buc[c].size()==0) cost=dlen;
else cost=abs(buc[c].back()-i);
ans+=cost;
}

return ans;
}

int main(){
int n,k; cin>>n>>k>>usr;
ulen=usr.length();
rep(i,ulen) buc[usr[i]].pb(i);

rep(i,n){
string dic; cin>>dic;
cout<<F(dic)<<endl;
}

return 0;
}

辞書の各文字列長が 105 だと読み間違えて、O(klog(n)) 解法を考えていた。よく考えると、それだと入力だけで O(nk) かかって TLE になるから、そんなことはありえない。

F を如何に速く計算するかという問題。
アルファベットごとに登場する位置を記録しておいて、二分探索で min |i-j| を求めるとそれなりに速くなる。
あまりきれいに書けなかった。

C.


C で幾何が出るとは思わなかった。
ライブラリがないと話にならない。
多角形の共通部分を求める関数とかがあれば、包除原理でうまく計算できるかもしれない。

D.



E.


スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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