スポンサーサイト

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

Codeforces Beta Round #48

日本時間 2010/12/29 01:00~03:30 に行われた、Codeforces Beta Round #48 の参加記録です。

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

結果

A. AC(476)
B. AC(844)
C. -
D. Hacked
E. -
F. -
Hacks : +250 (3 hacked / 1 missed)
Standing : 155/859
Rating : 16711724


問題

今回の問題セットはこんな感じでした。

A. Cheaterius's Problem
4 つのさいころを 2 × 2 正方形状に並べたものを amulet と呼ぶことにする。
n コの amulet が与えられる。
回転で一致する amulet どうしは同じであるとみなすとき、異なる amulet は幾つあるか。

B. bHTML Tables Analisys
html の table タグとほぼ同じフォーマットにしたがって、テーブルを表す html 文が与えられる。
テーブルは入れ子になっている可能性がある。
html 文に含まれるすべてのテーブルについて、そのセル数を求め、昇順に出力せよ。
( ※ テーブルのセル数 = テーブルに含まれる <td></td> の個数 とする )

入力は <table> </table> <tr> </tr> <td> </td> を正しい順序で組み合わせたものであることが保証されている。
( BNF による正確な定義は原文中にある。)

C. Three Base Stations
直線上に並んだ n (≦ 2・105) コの家がある。
家の位置は、数直線上の座標で表され、それぞれ 1 以上 109 以下の整数である。

すべての家をカバーするように、携帯電話の基地局を 3 つ造りたい。基地局から出る電波の強さを d , 基地局の位置を t とすると、基地局がカバーできる範囲は [ t-d, t+d ] である。ここで、t, d は整数でなくてもいい。

d は 3 つの基地局に共通の値である。d を最小化するような基地局の配置とそのときの d の値を求めよ。
答えが複数ある場合はどれを答えてもいい。

D. Geometrical problem
n (≦ 105) コの整数からなる数列について、
・ この数列が幾何数列 ならば、0 と答えよ。
・ この数列から 1 つの数を取り除くと幾何数列になるならば、1 と答えよ。
・ 上のいずれにもあてはまらないならば、2 と答えよ。
( ※ 幾何数列 = 等比数列 )

E. Pentagon
ノード数 700 以下の単純無向グラフが与えられる。
グラフ中にある長さ 5 の単純閉路 (自己交差しない閉路) の個数を求めよ。

制限時間 10 秒

F.
未読

解答

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

A.
int main(){
int n; scanf("%d ",&n);
set< vector<char> > pile;
while(n--){
char a,b,c,d; scanf("%c%c %c%c %*s ",&a,&b,&d,&c);
vector<char> amu[4];
amu[0].pb(a),amu[0].pb(b),amu[0].pb(c),amu[0].pb(d);
amu[1].pb(b),amu[1].pb(c),amu[1].pb(d),amu[1].pb(a);
amu[2].pb(c),amu[2].pb(d),amu[2].pb(a),amu[2].pb(b);
amu[3].pb(d),amu[3].pb(a),amu[3].pb(b),amu[3].pb(c);

sort(amu,amu+4);

pile.insert(amu[0]);
}

printf("%d\n",pile.size());

return 0;
}

4 つのサイコロの並びのうち、辞書式で一番小さいものを set につっこんで、最後に set の要素数を答えるようにした。
A問題なので データ数が少ないので、hash などの特別な工夫はしなくてもいい。

B.
void parse(const string &s,vi &cell){
int len=s.length();

stack<int> sk;
int cnt=0;
rep(i,len){
if(s[i]=='<'){
int b=i;
for(;s[i]!='>';i++); // skip
string tag=s.substr(b,i-b+1);
if(tag=="<table>"){
sk.push(cnt);
cnt=0;
}
else if(tag=="</table>"){
cell.pb(cnt);
cnt=sk.top(); sk.pop();
}
else if(tag=="<td>"){
cnt++;
}
}
}

while(!sk.empty()){
int a=sk.top(); sk.pop();
cell.pb(a);
}
}

int main(){
string in;
for(string s;cin>>s;in+=s);

vi cell;
parse(in,cell);

sort(cell.begin(),cell.end());

rep(i,cell.size()) cout<<(i?" ":"")<<cell[i];
cout<<endl;

return 0;
}

興味あるタグは <table>, </table>, <td> の 3 種類だけで、あとは無視してもいい。
テーブルの入れ子構造は stack を使えばうまく実装できる。
前から順にタグを調べていって、
・ <table> が来たら、今 見ているテーブルのセル数を stack に積んでおいて、新しいテーブルを見るようにする。
・ </table> が来たら、今 見ているテーブルのセル数を記録して、1つ前のテーブルに戻る。
・ <td> が来たら、今 見ているテーブルのセル数を 1 つ増やす。
みたいな感じ。

C. (時間外)
int n,x[200000];

bool isCoverable(int d){
int p1=upper_bound(x,x+n,x[0]+d)-x;
if(p1==n) return true;
int p2=upper_bound(x+p1,x+n,x[p1]+d)-x;
if(p2==n) return true;
int p3=upper_bound(x+p2,x+n,x[p2]+d)-x;
return p3==n;
}

int main(){
scanf("%d",&n);
rep(i,n) scanf("%d",x+i);
sort(x,x+n);

int Dl=0,Dr=10e10;
while(Dl!=Dr){
int Dm=(Dl+Dr)/2;
if(isCoverable(Dm)) Dr=Dm;
else Dl=Dm+1;
}

printf("%f\n",Dl/2.0);
int p1,p2,p3;
p1=upper_bound(x,x+n,x[0]+Dl)-x;
if(p1==n) p1=0;
p2=upper_bound(x+p1,x+n,x[p1]+Dl)-x;
if(p2==n) p2=0;
printf("%.6f %.6f %.6f\n",x[0]+Dl/2.0,x[p1]+Dl/2.0,x[p2]+Dl/2.0);

return 0;
}

競技中に解法がまったく思いつかなかったのは悔しい。
submit してる人がたくさんいたので、そんなに複雑な問題ではないはず。

解いた人のソースをみていると、どうやら二分探索しているようだ。
またあとで考える。

[ 2011/01/15 追記 ]
固定した d に対して、その d で全部の家を覆えるかどうかは二分探索を用いると O(log n) で判定できる。
具体的には、左から Greedy に割り当てていけばいい。

D. (時間外)
bool isGeometrical(int *a,int n){
if(a[0]==0){
rep(i,n) if(a[i]!=0) return false;
return true;
}

rep(i,n-1) if(a[i+1]*a[0]!=a[i]*a[1]) return false;
return true;
}

int main(){
int n; scanf("%d",&n);
int a[100000],num0=0,pos0=-1;
rep(i,n){
scanf("%d",a+i);
if(a[i]==0){
num0++;
if(pos0==-1) pos0=i;
}
}

if(n<=2){
printf("%d\n",isGeometrical(a,n)?0:1);
return 0;
}

// n>=3
if(num0>=2){ // r must equals 0
int cnt=0;
for(int i=1;i<n;i++) if(a[i]!=0) cnt++;
printf("%d\n",min(cnt,2));
return 0;
}
if(num0==1){ // 0 must be deleted
for(int i=pos0;i<n-1;i++) a[i]=a[i+1];
printf("%d\n",isGeometrical(a,n-1)?1:2);
return 0;
}

// sequence {a_n} is not include any 0s
int ans;
if(isGeometrical(a,n)) ans=0;
else{
if(isGeometrical(a+1,n-1)){ ans=1; goto END; }
swap(a[0],a[1]);
if(isGeometrical(a+1,n-1)){ ans=1; goto END; }
swap(a[0],a[1]);

ans=0;
rep(i,n-1){
if(a[i+1]*a[0]!=a[i]*a[1]){
ans++;
a[i+1]=a[i];
}
if(ans==2) break;
}

END:;
}
printf("%d\n",ans);

return 0;
}

アルゴリズム自体は単純だけど、例外処理が多くてかなり注意深く書かないと間違える。

競技中は、C が解けなくて何とか点数取らないといけないというのもあったので、
Hack される気はしたけど、submit したコードをロックして他の人の D 問題を Hack することに専念した。
結局、4 回チャレンジして 3 回成功した。

上のコードは競技が終わってから書いたもの。

方針としては、
・ n ≦ 2 のとき
・ n ≧ 3 で 0 が 2 つ以上含まれているとき ( このときは、公比 = 0 でないと幾何数列にならない )
・ n ≧ 3 で 0 が 1 つだけ含まれているとき ( このときは、0 を削除しないと幾何数列にできない )
・ n ≧ 3 で 0 が含まれていないとき
で場合分けした。

E. (時間外)
int main(){
int n,m; scanf("%d%d",&n,&m);
static bool adj[700][700];
rep(i,m){
int u,v; scanf("%d%d",&u,&v);
u--,v--;
adj[u][v]=adj[v][u]=true;
}

static int cnt3[700][700],cnt4[700][700];
rep(i,n)rep(j,i){
rep(k,n)if(i!=k && j!=k){
if(adj[i][k] && adj[k][j]) cnt3[i][j]++;
}
cnt3[j][i]=cnt3[i][j];
}
rep(i,n)rep(j,i){
rep(k,n)if(i!=k && j!=k){
if(adj[k][j]) cnt4[i][j]+=cnt3[i][k]-(adj[i][j] && adj[j][k]);
}
cnt4[j][i]=cnt4[i][j];
}

ll ans=0;
rep(u0,n){
// counting part (count the number of cycles that include node u0)
ll tmp=0;
rep(u,n)if(adj[u0][u]){
rep(v,n)if(adj[u][v] && v!=u0){
tmp+=cnt4[u0][v];
if(adj[u0][u]) tmp-=cnt3[u][v ]-(adj[u][u0] && adj[u0][v ]);
if(adj[v ][u]) tmp-=cnt3[u][u0]-(adj[u][v ] && adj[v ][u0]);
}
}
ans+=tmp/2;

// contraction part
rep(u,n)rep(v,u){
if(adj[u][u0]) cnt4[u][v]-=cnt3[u0][v]-(adj[u0][u] && adj[u][v]);
if(adj[v][u0]) cnt4[u][v]-=cnt3[u0][u]-(adj[u0][v] && adj[v][u]);
cnt4[v][u]=cnt4[u][v];
}
rep(u,n)rep(v,u){
if(adj[u][u0] && adj[u0][v]) cnt3[u][v]--,cnt3[v][u]=cnt3[u][v];
}
rep(u,n) adj[u0][u]=adj[u][u0]=false;
}

printf("%I64d\n",ans);

return 0;
}

[ 2011/03/19 追記 ]

解いた。
頂点数と妙に長い Time Limit から、O(n3) で間に合うだろうと推測できる。

解法は DP。
cnt3[u][v] := u, v を端点とする長さ 2 の (3 頂点からなる) 道の数
cnt4[u][v] := u, v を端点とする長さ 3 の (4 頂点からなる) 道の数

とする。これらはうまくやれば O(n3) で計算できる。

長さ 5 の閉路の数 = 頂点 0 を通る長さ 5 の閉路の数 + 0 を通らない長さ 5 の閉路の数
と分解すれば、右辺第 1 項は cnt3, cnt4 を使って O(n2) で求められる。
その後、右辺第 2 項を求めるために、グラフから頂点 0 を削除する。その際に cnt3, cnt4 の情報も更新する。
以下、縮約したグラフに対して同様の処理を繰り返す。



今回は A, B だけしか解けなくて全然ダメだったけど、System Test で C, D が大量に落ちていたせいか Rating は上がった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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