スポンサーサイト

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

Codeforces Beta Round #86

2011/09/09 00:00~02:00 (JST)
Codeforces Beta Round #86 の参加記録

最近 B 問題が難しい。

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

結果

A. WA
B. -
C. 2WA, AC (01:41)
D. -
E. -
Hacks : +-0 (0/0)
Standing : 90/456
Rating : 19261980


問題

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

A. Grammar Lessons
与えられる文字列が次で定義される Petya's language の sentence として正しいかどうかを判定せよ。

・ 単語は形容詞、名詞、動詞のいずれかである
・ 単語は男性形と女性形どちらかの性別をもっている
・ 男性形の形容詞は lios で終わり、女性形の形容詞は liala で終わる
・ 男性形の名詞は etr で終わり、女性形の名詞は etra で終わる
・ 男性形の動詞は initis で終わり、女性形の動詞は inites で終わる
・ sentence は 1 つの単語、または 1 つのstatement である
・ statement は 0 個以上の形容詞、1 個の名詞、0 個以上の動詞をこの順で並べたものである
・ statement にあるすべての単語は同じ性別をもつ

B.

C. Double Happiness
閉区間 [l, r] に、2 つの平方数の和で表せる素数はいくつあるか?

1 ≦ l ≦ r ≦ 3×108

D.

E.

解答

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

A. (時間外)
const int M=0,F=1,ADJE=2,NOUN=3,VERB=4,NG=5;

const char *WORD[]={"lios","liala","etr","etra","initis","inites"};

bool isSuffix(const string &s,const string &t){
int m=s.length(),n=t.length();
if(m<n) return false;
return s.substr(m-n)==t;
}

pii type(const string &s){
if(isSuffix(s,WORD[0])) return make_pair(M,ADJE);
if(isSuffix(s,WORD[1])) return make_pair(F,ADJE);
if(isSuffix(s,WORD[2])) return make_pair(M,NOUN);
if(isSuffix(s,WORD[3])) return make_pair(F,NOUN);
if(isSuffix(s,WORD[4])) return make_pair(M,VERB);
if(isSuffix(s,WORD[5])) return make_pair(F,VERB);
return make_pair(NG,NG);
}

int main(){
vector<string> S;
vector<pii> T;
for(string s;cin>>s;){
S.push_back(s);
T.push_back(type(s));
}

bool ok=true;
rep(i,S.size()){
if(T[i].first==NG
|| i>0 && T[i-1].first!=T[i].first) ok=false;
}

if(T.size()>1){
int p=0;
rep(i,T.size()){
if(T[i].second==ADJE){
if(p!=0) ok=false;
}
else if(T[i].second==NOUN){
if(p==0) p=1;
else ok=false;
}
else{ // T[i].second==VERB
if(p!=0) p=2;
else ok=false;
}
}
if(p==0) ok=false;
}

cout<<(ok?"YES":"NO")<<endl;

return 0;
}

実装するだけだけど、いろんなところではまってしまった。
statement の判定はオートマトンを書けばよかった。

B.


C.
bool er2[100000000]; // er2[n]==false <=> 4n+1 is a prime

int f(int l,int r){
int two=(l<=2&&2<=r?1:0);
while(l%4!=1) l++; l/=4;
while(r%4!=1) r--; r/=4;
return two+count(er2+l,er2+r+1,false);
}

int main(){
er2[0]=true;

const int Ne=17500;
static bool er[Ne+1]={true,true};
for(int i=2;i*i<=Ne;i++) if(!er[i]) for(int j=i*i;j<=Ne;j+=i) er[j]=true;

// (4n+1)^2 = 4(4n^2+2n)+1
// (4n+3)^2 = 4(4n^2+6n+2)+1
rep(p,Ne+1) if(!er[p]) {
if(p==2 || ((p&3)==1 && er2[p>>2])) continue;
for(int j=p*p;j<=300000000;j+=(p<<2)) er2[j>>2]=true;
}

int l,r; scanf("%d%d",&l,&r); printf("%d\n",f(l,r));

return 0;
}

ガウス素数まわりの話で、2 つの平方の和で書けるかどうかというのは聞いたことがあったので、とりあえず検索。
p (≧ 3) が 2 つの平方数の和で書ける ⇔ p ≡ 1 (mod 4)
というのがわかった。 (ここ)

なので、元の問題は 4n+1 型の素数の個数を求める問題に帰着される。

エラトステネスの篩。
最大値が 3×108 と大きいけど、4 つとばしに見ればいいので、実質 108 くらいと思っていい。
time limit が 5 秒なのでぎりぎり間に合う気がする。

memory limit が 128 MB だから、ナイーブにサイズ 3×108 の bool 配列を取ると MLE。
これも 4 分の 1 だけならぎりぎり収まる。
※ vector<bool> とか bitset を使えば、3×108 をとっても大丈夫だった。

4n+1 の素数だけを篩うのは、エラトステネスの篩とほぼ同じ要領でできる。
少しでも速度を上げるために、小さな最適化はいくつかした。

区間篩 (逐次篩) のようなことをしている人や、区間をいくつかのブロックに分けてブロック内の解の個数を埋め込んでいる人もいた。

D.


E.


感想

なぜか Rating は上がった。

A.
時間がかかりすぎた上に WA。
明らかに実装力が足りない。

B.
問題をざっと読んで、O(n3) より速い解法が思いつかなそうだったので C をやることにした。
B を落としている人がかなり多かったので、結果としてはこの選択は正解だった。

C.
前回に続き、知識問題だったので助かった。
KUPC 2011 E の篩を応用する問題が解けなくて悔しかったので、雪辱を果たせた気になっている。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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