スポンサーサイト

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

Codeforces Beta Round #73

2011/06/08 0:00~2:00 (JST)
Codeforces Beta Round #73 (Div.1 Only) の参加記録

Div.2 Only とは、 A, B, C の 3 問が重複。

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

結果

A. 2WA, AC (00:20)
B. AC (01:28)
C. AC (00:47)
D. -
E. -
Hacks : +-0 (0/0)
Standing : 79/444
Rating : 18041915


問題

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

A. Trains
a 分ごとにホームに来る電車 A と b 分ごとにホームに来る電車 B がある。
あるタイミングでは、電車 A, B は同時にホームにいる。

Vasya はホームに着いて最初に来た電車に乗る。
ただし、2 本の電車が同時に来た場合は、a, b の大きいほうに乗る。
Vasya が乗る確率が高い電車は A, B のどちらか? もしくは同じか?

1 ≦ a, b ≦ 106, a ≠ b

B. Vasya and Types
typedef a b
typeof a
という 2 種類のコマンドからなる列が与えられる。
各 typeof a について、a の型を答えよ。

・ 基本的な型は void, errtype の 2 種類。
・ 型の右に * をつなげたものも型である。
・ * と & は逆の意味であり、相殺される。たとえば、 &void** は void* としなければいけない。
・ * より & の数の方が多かったり、未定義であったりした場合、その型は errtype になる。
・ errtype = errtype* = &errtype である。

C. Interesting Game
2 人でターン制のゲームをする。
打つ手がなくなったほうが負け。

最初、n 個の石からなる 1 つの山がある。
プレイヤーは、山を 1 つ選んで、それを k 個の山に分割する。
ただし、分割した山にある石の個数は、昇順で公差 1 の数列になっていないといけない。

先手必勝かどうかを判定せよ。
そうであれば、先手が最初に打つべき手を求めよ。

1 ≦ n ≦ 105

D. Beautiful Road
n 個の町があり、n-1 本の (両方向の) 道路でつながれている。
道路には重みがつけられている。
どの 2 つの町の間も行き来できることが保障されている。

2 つの町を選んで、それらをつなぐ道にある道路の中で重み最大のもの (複数ありうる) の傍に植物を植える。
これをすべての 2 つの町の選び方 ( n(n-1) 通り ) について行う。

もっとも多くの植物が植えられている道路と、そこにある植物の本数を答えよ。

2 ≦ n ≦ 105

E.

解答

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

A.
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }

int main(){
int a,b; scanf("%d%d",&a,&b);
ll L=lcm(a,b);
ll cnta=L/a,cntb=L/b;
if(a>b) cntb--;
else cnta--;
if (cnta>cntb) puts("Dasha");
else if(cnta<cntb) puts("Masha");
else puts("Equal");

return 0;
}

A と B の共通の周期である L=LCM(a,b) までを考える。

区間 [0, L) の間で、
最初に来る電車が A である時間 ta と
最初に来る電車が B である時間 tb が分かればいい。

数直線を書いて、適当な例でプロットしてみればわかるように、
ta = L/a
tb = L/b
である。

[0, L) の範囲で考えているので、電車 A と B が同時にホームに着くのは、時刻 0 のときだけ。
なので、同時にホームに着くときの処理は ta と tb のどちらかを 1 減らせばいい。

B.
struct Data{
int ast;
string name;
Data(){}
Data(string N,int AS):name(N),ast(AS){}
bool operator<(const Data &d)const{
if(ast!=d.ast) return ast<d.ast;
return name<d.name;
}
string str(){ return name+string(ast,'*'); }
};

map<string,Data> f;

Data parse(const string s){
int len=s.length();
int i,j;
for(i=0;i<len;i++) if(s[i]!='&') break;
for(j=len-1;i>=0;j--) if(s[j]!='*') break;

int amp=i,ast=len-j-1;
string name=s.substr(i,j-i+1);

while(name!="void" && name!="errtype"){
if(f.find(name)==f.end()) return Data("errtype",0);

Data tmp=f[name];
ast+=tmp.ast;
name=tmp.name;
}

if(name=="void"){
while(amp>0 && ast>0) amp--, ast--;
if(amp>0) name="errtype";
}
if(name=="errtype") amp=ast=0;

return Data(name,ast);
}

int main(){
int n; cin>>n;
rep(i,n){
string cmd; cin>>cmd;
if(cmd=="typedef"){
string a,b; cin>>a>>b;
f[b]=parse(a);
}
else{ // cmd=="typeof"
string a; cin>>a;
cout<<parse(a).str()<<endl;
}
}

return 0;
}

がんばって実装するだけ、としか言えない。

C.
int dp[100001];

int solve(int n){
if(~dp[n]) return dp[n];

vi grundy;
for(int k=2;2*n-k*(k+1)>=0;k++){
if((2*n-k*(k+1))%(2*k)==0){
int a=(2*n-k*(k+1))/(2*k);
int tmp=0;
rep(i,k) tmp^=solve(a+i+1);
grundy.pb(tmp);
}
}

sort(all(grundy));
grundy.erase(unique(all(grundy)),grundy.end());

rep(i,grundy.size()) if(grundy[i]!=i) return dp[n]=i;
return dp[n]=grundy.size();
}

int solve2(int n){
for(int k=2;2*n-k*(k+1)>=0;k++){
if((2*n-k*(k+1))%(2*k)==0){
int a=(2*n-k*(k+1))/(2*k);
int tmp=0;
rep(i,k) tmp^=solve(a+i+1);
if(tmp==0) return k;
}
}
return -1;
}

int main(){
memset(dp,-1,sizeof dp);

int n; scanf("%d",&n);
int ans=solve(n);
if(ans==0) puts("-1");
else printf("%d\n",solve2(n));

return 0;
}

まともにやって規則を見つけ出すのは、多分、すごく難しい。

この手のゲームに対する常套手段である Grundy number を使った。
Grundy number の簡単なまとめ記事は今度書くつもり。

D. (時間外)
struct Edge{
int u,v,w,id;
Edge(){}
Edge(int U,int V,int W,int ID):u(U),v(V),w(W),id(ID){}
bool operator<(const Edge &e)const{ return w<e.w; }
};

class UnionFind{
vector<int> a;
public:
UnionFind(){}
UnionFind(int n):a(n,-1){}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y){ a[x]+=a[y]; a[y]=x; }
}
int size(int x){ return -a[find(x)]; }
};

UnionFind uf;
vector<Edge> adj[100000];

int i_now;
int dp[200000],i_dp[200000];

int dfs(int u,int prev,int id){
if(i_dp[id]==i_now) return dp[id];

int res=uf.size(u);
rep(i,adj[u].size()){
int v=adj[u][i].v,id2=adj[u][i].id;
if(v!=prev) res+=dfs(v,u,id2);
}

i_dp[id]=i_now;
return dp[id]=res;
}

int main(){
int n; scanf("%d",&n);
uf=UnionFind(n);
static Edge E[100000];
rep(i,n-1){
int u,v,w; scanf("%d%d%d",&u,&v,&w); u--; v--;
E[i]=Edge(u,v,w,i);
i_dp[i]=i_dp[i+n]=-1;
}
sort(E,E+n-1);

static ll res[100000];
for(int i=0;i<n-1;){
vector<Edge> E2;
for(int i0=i;i<n-1;i++){
if(i==i0 || E[i-1].w==E[i].w){
E2.push_back(E[i]);

int u=uf.find(E[i].u),v=uf.find(E[i].v),id=E[i].id;
adj[u].push_back(Edge(u,v,-1,id));
adj[v].push_back(Edge(v,u,-1,id+n));
}
else break;
}

i_now=i;
rep(j,E2.size()){
int u=uf.find(E2[j].u),v=uf.find(E2[j].v),id=E2[j].id;
res[id]=2LL*dfs(v,u,id)*dfs(u,v,id+n);
}

rep(j,E2.size()){
uf.unite(E2[j].u,E2[j].v);

int u=uf.find(E2[j].u),v=uf.find(E2[j].v);
adj[u].clear();
adj[v].clear();
}
}

ll ans=*max_element(res,res+n-1);
printf("%I64d %d\n",ans,count(res,res+n-1,ans));
rep(i,n-1) if(res[i]==ans) printf("%d\n",i+1);

return 0;
}

[ 2011/09/04 追記 ]

Editorials を見ながら解いた。とても難しかった。

辺数 n-1 の連結グラフなので、グラフは木。

最初、辺がない n 頂点のグラフを考える。
辺を重みが小さい順にソートして、その順にグラフに追加していく。

同じ重みの辺は同時に追加する。
辺に何本の植物が植えられているかは、その辺の両端から先にいくつの頂点がつながっているかがわかればいい。
これは DFS (メモ化再帰) でできる。
ただし、メモ化用の配列を毎回初期化すると O(V) のコストがかかって TLE になるので、うまく情報を上書きしないといけない。

辺を追加したら、グラフの連結成分がどうつながっているかは興味がない (頂点数だけわかればいい) ので、Union-Find を使って、1 頂点に縮約してしまう。

E.



感想

どう考えても実力以上の Rating がついてしまった。

A.
同時にホームに来るタイミングが GCD(a,b) 回あると勘違いして WA.
一瞬で解けてもいい問題だった。

B.
正解者が多かった C を先に解いた。
時間かかりすぎ。
問題読解も含めて 40 分。

3 問解いたあとは、B. C. を Lock して Hack に専念した。
未定義の文字列が与えられるケースがサンプルにないことには気付いていたので、それを狙おうとしたけど、忘れている人が誰もいない。
どうやら pretest ではじかれていたらしい。残念。

C.
CodeChef May Cook-Off の問題を復習していたのがよかった。
Grundy number にもだんだんなじんできた。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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