スポンサーサイト

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

Codeforces Beta Round #62

2011/03/19 1:00~3:00 (JST)
Codeforces Beta Round #62 の参加記録

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

結果

A. AC(474)
B. 3WA
C. -
D. -
E. -
Hacks : +-0 (0 hacked / 0 missed)
Standing : 544/1129
Rating : 17811660


ダメすぎて、もう笑うしかない。

問題

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

A. Irrational problem
p1, p2, p3, p4, a, b (すべて整数) が与えられる。
f(x) = (((x mod p1) mod p2) mod p3) mod p4 とおく。
p1, p2, p3, p4 の並び (4! 通り) のうち、7 通り以上で f(x) = x となるような整数 x (a ≦ x ≦ b) の個数を求めよ。

B. Energy exchange
n 個のタンクがあり、最初、それぞれのタンクには ai 単位の燃料が入っている。
任意のタンク間で燃料を移動することができて、その際に k % の損失が出る。
つまり、あるタンクから x 単位の燃料を取り出すと、(1 - k/100)・x 単位の燃料を他のタンクに追加することができる。
すべてのタンクの燃料の量を等しくするように移動させるとき、ありうる燃料の最大量を求めよ。

C. Synchrophasotron
頂点数 n の完全グラフで、頂点 1 をソース、頂点 n をシンクとしてフローを流す。
グラフの各辺には、流さなければならないフローの下限と上限、フローを流すためのコストが定められている。
総フローを最小化し、その下で総コストを最大化せよ。
総コストは、1 以上のフローを流している各辺について、辺のコスト + 辺のフロー量2 を足し合わせたものとする。

2 ≦ n ≦ 6
0 ≦ 辺のフローの下限 ≦ 辺のフローの上限 ≦ 5
0 ≦ 辺のコスト ≦ 6
すべて整数

D.
E.
あとで読む。

解答

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

A.
int main(){
int p[4];
rep(i,4) scanf("%d",p+i);
int a,b; scanf("%d%d",&a,&b);

int ans=0;
for(int x=a;x<=b;x++) if(x%p[0]%p[1]%p[2]%p[3]==x) ans++;

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

return 0;
}

問題文が読みにくかった。

f(x) = x かどうかを気にするなら、mod を取る順番は関係ない。
( mod で一度でも丸められたら、f(x) < x となる )
なので、7 通り以上がどうとかいう条件は考えなくていい。
あとは線形探索。O(b-a).

※ 上位者のコードを見ていると、O(1) でも解けるようだ。

B. (時間外)
int n,k,a[10000];

bool isMovable(double x){
double m=0;
rep(i,n) if(a[i]>x) m+=a[i]-x;
m*=1-k/100.;
rep(i,n) if(a[i]<x) m-=x-a[i];
return m>-1e-12;
}

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

double lo=0,hi=1000;
rep(k,100){
double mi=(lo+hi)/2;
if(isMovable(mi)) lo=mi;
else hi=mi;
}
printf("%.15f\n",lo);
}

答えが解析的に求まるものだと思い込んでいて、正解にたどり着けなかった。
自分の頭の固さに泣けてくる。

ほとんどの人は二分探索で解いていた。
答え x を決め打ちしたときに、タンクの燃料を x 以上でそろえられるかは、O(n) で判定できる。
この x には単調性があるので二分探索が使える。

C. (時間外)
int n,lo[6][6],hi[6][6],act[6][6];
int flow[6][6],nodeflow[6];

pii solve(int from,int to){
if(2<=from && from<n && from+1==to){ // pruning
if(nodeflow[from-1]!=0) return mp(INF,-1);
}

if(from==n-1 && to==n){
int cost=0;
rep(v,n)rep(u,v) if(flow[u][v]>0) cost+=act[u][v]+flow[u][v]*flow[u][v];
return mp(-nodeflow[0],cost);
}

int nextfrom,nextto;
if(to<n-1){
nextfrom=from;
nextto=to+1;
}
else{
nextfrom=from+1;
nextto=nextfrom+1;
}

pii ans=mp(INF,-1);
for(int f=lo[from][to];f<=hi[from][to];f++){
flow[from][to]=f;
nodeflow[from]-=f;
nodeflow[to]+=f;

pii tmp=solve(nextfrom,nextto);
if(tmp.first<ans.first || (tmp.first==ans.first && tmp.second>ans.second)) ans=tmp;

nodeflow[from]+=f;
nodeflow[to]-=f;
}

return ans;
}

int main(){
scanf("%d",&n);
rep(i,n*(n-1)/2){
int s,f,l,h,a; scanf("%d%d%d%d%d",&s,&f,&l,&h,&a);
s--,f--;
lo[s][f]=l;
hi[s][f]=h;
act[s][f]=a;
}

pii ans=solve(0,1);
printf("%d %d\n",ans.first<INF?ans.first:-1,ans.second);

return 0;
}

[ 2011/03/25 追記 ]

解いた。
競技中は、問題が複雑すぎてとても解けないと思ったけど、解答が分かってしまえば決して難しくない。

入力されるすべての値が極端に小さいので、すべての辺についてすべてのありうるフロー量を試してみるという全探索でいい。
自明な枝刈りを少し入れれば間に合う。
DFS でバックトラックした。
制限時間 3 sec のところ、上記コードは最悪ケースで 2.7 sec くらい。

D.


いつか。

E.


いつか。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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