スポンサーサイト

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

Codeforces Beta Round #80

2011/08/07 20:00~22:00 (JST)
Codeforces Beta Round #80 (Div.1 Only) の参加記録

#79 に参加しそこねたので、久しぶりのコンテストだった。

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

結果

A. AC (01:25)
B. -
C. AC (01:02)
D. -
E. -
Hacks : +-0 (0/0)
Standing : 150/357
Rating : 17771786


問題

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

A. Testing Pants for Sadness
n 個の問題に順番に答える。
i 番目の問題の答えは ai 通りありうる。

一度でも答えを間違えると、1 問目からやり直しになる。
ただし、同じ問題が出題されるので、2 回目以降は一発で正解を選ぶことができるものとする。

もっとも運が悪かったとして、最大で何回の質問に答えればいいか。

1 ≦ n ≦ 100
1 ≦ ai ≦ 109

B. Cthulhu
長さ 3 以上の単純閉路 C が 1 つあり、C に木がくっついているような形の無向グラフを Cthulhu と呼ぶことにする。
与えられるグラフが Cthulhu かどうかを判定せよ。

1 ≦ n ≦ 100
与えられるグラフは多重辺,自己ループをもたない

C. Russian Roulette
ロシアンルーレット。
n 個のスロットをもつリボルバーに k 個の弾を込める。

自分が先手。相手が後手。
順番に引き金を引いていって、最初に弾が発射されたほうの負け。
どのスロットから始まるかは等確率で決まる。

自分の勝率が最大になるような弾込めの配置について、
「 i 個目のスロットに弾があるか」 という p 個のクエリを処理せよ。

( ただし、複数の配置が考えられる場合は、弾の配置を文字列で表したときに辞書式最小のものを選ぶ。 )

1 ≦ n, k ≦ 1018
1 ≦ p ≦ 1000

D. Time to Raid Cowavans
長さ n の数列 { wi } が与えられる。

p 個のクエリを処理せよ。
クエリは (a, b) という形で与えられ、
wa + wa+b + wa+2b + ...
を計算することを意味する。
( ... は数列の末尾までの和の意味 )

1 ≦ n, p ≦ 3・105
1 ≦ wi ≦ 109

E.

解答

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

A.
int main(){
int n; cin>>n;
ll ans=0;
rep(i,n){
ll a; cin>>a;
ans+=(i+1)*(a-1)+1;
}
cout<<ans<<endl;

return 0;
}

n = 3 などの小さいケースで実験して、公式を見つけた。

B. (時間外)
class UnionFind{
int n;
vector<int> a;
public:
UnionFind(int N):a(N,-1),n(N){}
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; n--; }
}
int size(){ return n; }
};

int main(){
int n,m; scanf("%d%d",&n,&m);
UnionFind uf(n);
rep(i,m){ int u,v; scanf("%d%d",&u,&v); uf.unite(u-1,v-1); }

puts(uf.size()==1 && n==m ? "FHTAGN!" : "NO");

return 0;
}

コンテスト中は最後まで問題文を誤読していた。
まぁ、正しく読み取れていたとしてもこの解法に気付いたかどうかは怪しいけど。

ようするに、グラフが連結で、閉路を 1 つだけもてばいい。

連結性のチェックはどうやってもできるけど、今回は Union-Find を使った。

連結なグラフについて、「閉路を 1 つだけもつ」 という条件は 「頂点数 = 辺数」 という条件と同値。
ざっと証明してみよう。
グラフ理論はまともに勉強したことがないので、変な証明になってるかもしれない。

[ ⇒ ]
閉路から 1 つの辺を取り除くと、グラフは木になる。
( 閉路をもたない連結グラフが木である )

木は、頂点数 = 辺数 - 1 という性質をもつから、元のグラフは 頂点数 = 辺数 となっているはず。

[ 逆 ]
グラフは木でない ( 木であれば 頂点数 = 辺数 - 1 のはず ) から、閉路を 1 つ以上もつ。
閉路から 1 つの辺を取り除くと 頂点数 = 辺数 - 1 となるから、残ったグラフは木。
木に (頂点を増やさないように) 辺を 1 つ加えると閉路が 1 つできるので、元のグラフには閉路が 1 つだけあるはず。

C.
inline void out(bool b){ cout<<(b?'.':'X'); }

int main(){
ll n,k;
int p; cin>>n>>k>>p;
while(p--){
ll x; cin>>x;

if(k==0){ out(1); continue; }

if(n%2==0){ // n is even
if(k<=n/2) out(!(x%2==0 && n-2*(k-1)<=x));
else out(!(x%2==0 || 2*n-2*k+1<=x));
}
else{ // n is odd
if(x==n) out(0);
else{
if(k<=(n+1)/2) out(!(x%2==0 && n-2*(k-1)<=x));
else out(!(x%2==0 || 2*n-2*k+1<=x));
}
}
}

return 0;
}

一見すると、どんな配置でも勝率は変わらないように思えるけど、そんなことはない。

これも小さいケースで実験して規則性を見つけた。

n = 6 のとき
k = 0 ......
k = 1 .....X
k = 2 ...X.X
k = 3 .X.X.X
k = 4 .X.XXX
k = 5 .XXXXX
k = 6 XXXXXX


というふうに弾を込めるのが最良。
つまり、1 つおきに後ろから詰めていって、半分までいったら後ろから残りを詰める。
一般に、n が偶数のときはこの方針でうまくいく。

n = 7 のとき
k = 0 .......
k = 1 ......X
k = 2 .....XX
k = 3 ...X.XX
k = 4 .X.X.XX
k = 5 .X.XXXX
k = 6 .XXXXXX
k = 7 XXXXXXX


というふうに弾を込めるのが最良。
偶数のときとほとんど同じだが、末尾の 1 つだけが特殊。
一般に、n が奇数のときはこの方針でうまくいく。

D. (時間外)
struct Query{ int a,b,i; ll ans; };

bool cmp1(const Query &q1,const Query &q2){ return q1.b<q2.b; }
bool cmp2(const Query &q1,const Query &q2){ return q1.i<q2.i; }

int main(){
int n; scanf("%d",&n);
static int w[300000];
rep(i,n) scanf("%d",w+i);

int nq; scanf("%d",&nq);
static Query q[300000];
rep(i,nq) scanf("%d%d",&q[i].a,&q[i].b), q[i].a--, q[i].i=i;

sort(q,q+nq,cmp1);

int last=-1;
static ll dp[300300];
rep(i,nq){
int a=q[i].a,b=q[i].b;
if(b<300){
if(last!=b){
for(int j=n-1;j>=0;j--) dp[j]=dp[j+b]+w[j];
last=b;
}
q[i].ans=dp[a];
}
else{
ll sum=0;
for(int j=a;j<n;j+=b) sum+=w[j];
q[i].ans=sum;
}
}

sort(q,q+nq,cmp2);

rep(i,nq) printf("%I64d\n",q[i].ans);

return 0;
}

AlexanderBolshakov さんの非公式 Editorials を見て解いた。

まず、b がある程度大きい (b ≧ 300 とした) クエリは、直接計算しても間に合う。
クエリ 1 つあたりの計算量は O(n/b).

b < 300 のクエリだけが問題。

ところで、b が等しく a だけが異なるクエリたちは一気に計算できる。
DP を使う。
dp[i] := クエリ (i, b) の値
とすれば、漸化式
dp[i] = dp[i+b] + w[i]
が成り立つので、後ろから順に DP テーブルを埋めていくことで O(n) で計算できる。

なので、高々 300 通りの b に対して、この DP を行えばよい。

計算方法を変える b の閾値を T とすれば、すべてのクエリ処理の計算量は O(pn/T + Tn) となる。
( p はクエリの総数 )

E.


感想

いつも A, B しか解けてないので、今回は C から解くと決めていた。

C.
思考時間は 40 分くらい。
条件式がややこしくて実装に少してこずった。
system test に通ったときはけっこう嬉しかった。

B.
次に B を読もうとしたけど題意すらつかめなかった。
一旦 A を解いたあと、B に戻ってきて、コンテスト終了までうんうんうなっていた。

A.
今回の A は素直な問題だったように思う。
すぐに書きあがった。

D.
D はコンテスト中は読まなかったけど、読んでも解けなかったと思う。
入力によって処理を分けるという解法は、聞いたことはあったけど、自分で解いたのは今回が初めてだった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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