スポンサーサイト

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

Codeforces Beta Round #56

2011/02/20 1:00~3:00 (JST)
Codeforces Beta Round #56 の記録

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

結果

A. AC(484)
B. AC(848)
C. 6WA
D. -
E. -
Hacks : None
Standing : 244/1193
Rating : 17761700


問題

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

A. Where Are My Flakes?
n 個の箱が一列に並べられている。
これらの箱のうち 1 つだけは当たりの箱である。

当たりの箱の場所に関して、m 個のヒントが与えられる。
ヒントは次のどちらかの形式にしたがう。
・ 当たりの箱は i 番目の箱より左にある
・ 当たりの箱は i 番目の箱より右にある

当たりの箱の位置としてありうるものは何箇所あるか?
なお、ヒントが矛盾しているときは -1 と答えよ。

1 ≦ n, m ≦ 1000

B. Serial Time!
サイズ n × m × k の直方体の容器に水を入れる。
容器にはいくつかの障害物が入っており、障害物のあるマスには水は入れない。
水のあるマスの六方(上下左右前後)が空きマスであれば、その方向に水が流れる。
水は直方体の上にある蛇口から、毎秒 1 単位量ずつ注がれる。
容器が水でいっぱいになるまでの時間を求めよ。

n, m, k ≦10; 1 ≦ x ≦ n, 1 ≦ y ≦ m ( x, y : 蛇口の位置 )

C. Mushroom Strife
ノード数 100 以下の単純グラフが与えられる。
グラフの各辺には 2 つのパラメータ GCD, LCM が付随している。

次の条件をみたすように、グラフのノードに重みを割り当てよ。
条件をみたすような割り当てが存在しない場合は NO と答えよ。

[ 条件 ]
各辺について
・ その辺の両端にあるノードの重みの最大公約数が GCD に等しい
・ その辺の両端にあるノードの重みの最小公倍数が LCM に等しい
が成立する。

1 ≦ GCD, LCM ≦ 106

D. Savior
106 個以下の芝生があり、芝生 i には ai 個のきのこが生えている。
芝生 i の上で笑うと、芝生 i のきのこおよび、次の条件をみたすような芝生 j のきのこが爆発する。
すべての芝生のきのこを爆発させるためには、最小で何回笑えばいいか?

[ 条件 ]
ある b があって、組 (ai, aj, b) (またはその任意の順列) が原始 Pythagoras 数になる

1 ≦ ai ≦ 107 (相異なる整数)

E.
読んでない。

解答

言語は C++。テンプレはここを参照。
ただし、A だけは C 言語で書いた。

A.
#include<stdio.h>

#define rep(i,n) for(i=0;i<n;i++)

int main(){
int i;
int m,n,l,r; scanf("%d%d ",&n,&m);
l=1,r=n;
rep(i,m){
int p;
char s[128]; fgets(s,127,stdin);
if(s[7]=='l'){
p=atoi(s+15);
if(p-1<r) r=p-1;
}
else{
p=atoi(s+16);
if(l<p+1) l=p+1;
}
}

printf("%d\n",l>r?-1:r-l+1);

return 0;
}

A 問題くらいなら、問題文を全部読まなくても題意を把握できるようになってきた。
気分転換に C 言語で書いてみた。
与えられるヒントが区間を限定するタイプのものなので、ありうる区間の左端と右端を覚えておいて、その値を逐次更新していけばいい。

B.
const int dx[]={1,0,-1,0,0,0},dy[]={0,-1,0,1,0,0},dz[]={0,0,0,0,-1,1};

struct P{
int x,y,z;
P(){}
P(int X,int Y,int Z):x(X),y(Y),z(Z){}
};

bool inrange(int x,int y,int z,int m,int n,int k){
return (0<=x && x<m && 0<=y && y<n && 0<=z && z<k);
}

int main(){
int dep,m,n; scanf("%d%d%d",&dep,&m,&n);
char plate[10][10][11];
rep(k,dep)rep(i,m) scanf("%s",plate[k][i]);
int tx,ty; scanf("%d%d",&ty,&tx);
tx--,ty--;

int vol=0;
bool filled[10][10][10]={};
queue<P> qu;
if(plate[0][ty][tx]=='.'){
qu.push(P(tx,ty,0));
filled[0][ty][tx]=true;
}
while(!qu.empty()){
P a=qu.front(); qu.pop();
int x=a.x,y=a.y,z=a.z;
vol++;
rep(i,6){
int xx=x+dx[i],yy=y+dy[i],zz=z+dz[i];
if(inrange(xx,yy,zz,n,m,dep) && plate[zz][yy][xx]=='.' && !filled[zz][yy][xx]){
qu.push(P(xx,yy,zz));
filled[zz][yy][xx]=true;
}
}
}

printf("%d\n",vol);

return 0;
}

3 次元で BFS するだけといえばそれまでだけど、ちょっと実装が重い。
デバッグも含めて結構時間をとられた。

C. (時間外)
ull gcd(ull a,ull b){ return b?gcd(b,a%b):a; }
ull lcm(ull a,ull b){ return a/gcd(a,b)*b; }

vvi toConnectedComponents(const vvb &adj){
int n=adj.size();
vvi res;
vb visited(n);
rep(i,n)if(!visited[i]){
vi comp;
queue<int> qu; qu.push(i); visited[i]=true;
while(!qu.empty()){
int u=qu.front(); qu.pop();
comp.pb(u);
rep(v,n)if(adj[u][v] && !visited[v]){ qu.push(v); visited[v]=true; }
}
res.pb(comp);
}
return res;
}

struct Edge{
ll g,l;
Edge(){}
Edge(ll G,ll L):g(G),l(L){};
};

vvb adj;
Edge prm[100][100];
ll num[100];
bool visited[100];

bool dfs(int cur,const vi &comp){
int n=comp.size(),u=comp[cur];
visited[u]=true;

rep(i,n){
int v=comp[i];
if(adj[u][v] && !visited[v]){
ll g=prm[u][v].g,l=prm[u][v].l;
num[v]=l/num[u]*g;

rep(j,n){ // check consistency
int w=comp[j];
if(adj[v][w] && visited[w]){
if(prm[v][w].g!=gcd(num[v],num[w])
|| prm[v][w].l!=lcm(num[v],num[w])) return false;
}
}

if(!dfs(i,comp)) return false;
}
}

return true;
}

bool paint(const vi &comp){
int n=comp.size();

if(n==1){ num[comp[0]]=1; return true; }

int u1=comp[0],u2;
rep(i,n)if(adj[u1][comp[i]]){ u2=comp[i]; break; }

vector<ll> candi; // make candidates
{
ll g=prm[u1][u2].g,l=prm[u1][u2].l;
for(ll a=g;a<=l;a+=g){
if(l%a!=0) continue;
ll b=l/a*g;
if(g==gcd(a,b)) candi.pb(a);
}
}

rep(i,candi.size()){ // foreach candidate
ll a=candi[i];
num[u1]=a;

rep(j,n) visited[comp[j]]=false;
if(dfs(0,comp)) return true;
}

return false;
}

int main(){
int m,n; scanf("%d%d",&n,&m);
adj=vvb(n,vb(n));
rep(i,m){
int u,v,g,l; scanf("%d%d%d%d",&u,&v,&g,&l);
u--,v--;
adj[u][v]=adj[v][u]=true;
prm[u][v]=prm[v][u]=Edge(g,l);
}

vvi comps=toConnectedComponents(adj);
rep(i,comps.size())if(!paint(comps[i])){ puts("NO"); return 0; }

puts("YES");
rep(i,n) printf("%s%d",i?" ":"",(int)num[i]);
putchar('\n');

return 0;
}

おおよその方針は競技中に思いついていたけど、実装に手間取った。
残り 20 分でなんとか書き上げるも、グラフが連結していない場合を考えていなくて WA.

「コーディングが遅いのならよく使うパーツは作りおきしておけばいい」ということで、無向グラフを連結成分に分ける処理を関数化してみた。

方針は、
a × b = gcd(a,b) × lcm(a,b)
という関係式があるので、1 つのノードの重みを決めれば連結成分の残りの重みは自動的に決まるということに注目する。この式については、以前の記事を参照。

なので、候補を全部調べてみて、辺の条件をみたすものがあるかをチェックすればいい。

残りのノードの重みを決定する際に、そのノードにつながっている他の辺との整合関係も同時にチェックしないとけないことに注意する。
これをせずに、最後に整合関係を一気にチェックしようとするとはまる。(真の解を調べもらす可能性がある。)

D. (時間外)
ull gcd(ull a,ull b){ return b?gcd(b,a%b):a; }

class UnionFind{
vi a;
int root(int x){ return ~a[x]?a[x]=root(a[x]):x; }
public:
UnionFind(int n):a(n,-1){}
bool find(int x,int y){ return root(x)==root(y); }
bool unite(int x,int y){ return find(x,y)?0:(a[root(y)]=root(x),1); }
};

struct Triple{
int a,b,c;
Triple(){}
Triple(int A,int B,int C):a(A),b(B),c(C){}
};

bool cmpA(const Triple &s,const Triple &t){ return s.a<t.a; }
bool cmpB(const Triple &s,const Triple &t){ return s.b<t.b; }

int main(){
const int PYMAX=20000000;
int len=0;
static Triple pyA[3200000],pyB[3200000];
for(int m=1;;++m){
int m2=m*m;
if(m2>PYMAX) break;
for(int n=(m%2?2:1);n<m;n+=2){
int mn=m*n,n2=n*n;
if(m2+n2>PYMAX) break;
if(gcd(m,n)==1){
int v[]={m2-n2,2*mn,m2+n2},t;
if(v[0]>v[1]) t=v[0],v[0]=v[1],v[1]=t;
pyA[len]=Triple(v[0],v[1],v[2]);
pyB[len]=pyA[len];
++len;
}
}
}

sort(pyA,pyA+len,cmpA);
sort(pyB,pyB+len,cmpB);

int n; scanf("%d",&n);
static int num[1000000];
rep(i,n) scanf("%d",num+i);
sort(num,num+n);

int cnt=n;
UnionFind uf(PYMAX+1);
rep(i,n){
pair<Triple*,Triple*> rng;
rng=equal_range(pyA,pyA+len,Triple(num[i],-1,-1),cmpA);
for(int j=rng.first-pyA;j<rng.second-pyA;j++){
int a=pyA[j].a,b=pyA[j].b,c=pyA[j].c;
if(binary_search(num,num+n,b) && uf.unite(a,b)) cnt--;
if(binary_search(num,num+n,c) && uf.unite(a,c)) cnt--;
}

rng=equal_range(pyB,pyB+len,Triple(-1,num[i],-1),cmpB);
for(int j=rng.first-pyB;j<rng.second-pyB;j++){
int a=pyB[j].a,b=pyB[j].b,c=pyB[j].c;
if(binary_search(num,num+n,c) && uf.unite(b,c)) cnt--;
if(binary_search(num,num+n,a) && uf.unite(b,a)) cnt--;
}
}

printf("%d\n",cnt);

return 0;
}

問題の設定がおかしい。laughy mushroom は多分、笑い茸のこと。

正解者のコードを見ながら解いた。

芝生をノード、誘爆するという関係を辺とみてできるグラフの連結成分の個数を求める問題。

まず、十分な大きさまでの原始 Pythagoras 数 (a, b, c) を全列挙する。
( a2 + b2 = c2 )
あとのために、a の昇順にソートしたものと b の昇順にソートしたものを用意した。
a, b が 107 以下になるためには、c < 2×107 程度までを用意すればいい。
ここまでの処理が Codeforces サーバ上で約 2 秒。ちなみに、手元では -O3 オプション付きで約 4 秒。

これが列挙できてしまえば、各ノードから出るエッジがすべてわかる。 (二分探索すれば log オーダー)
小さいケースを見てみた感じだと、各ノードにつながるエッジの数はそんなに多くない。
なので、すべての辺を走査して、連結成分の個数を求める解法で間に合う。
連結成分を効率よく管理するのには UnionFind を使う。
最大ケースで約 3.1 秒。Time Limit は 4 秒だからぎりぎり OK。

もっと速くするには、Pythagoras 数の列挙と連結成分の処理を同時に行えばいい。

E.


スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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