スポンサーサイト

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

Codeforces Beta Round #41

JST 11/19 01:00~03:00 に行われた Codeforces 第41回の記録です。

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

[ 結果 ]
A. AC (460)
B. AC (628)
C. -
D. -
E. -
1 Hacked
Standing 115/774
Rating 16261698

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

A. Guilty – to the kitchen!
ボルシチ (ロシアの伝統料理) を作ろう。
ボルシチは n 個の材料からなり、それぞれを
a1 : a2 : ... : an
の比で調合することで作られる。
今、冷蔵庫にはそれぞれの材料が
b1, b2, ..., bn
だけある。
また、作る鍋の大きさは V であり、使う材料の総和は V を越えることができない。
作ることができるボルシチの最大量を求める。

1 ≦ n ≦ 20, 1 ≦ V ≦ 10000, 1 ≦ ai ≦ 100, 0 ≦ bi ≦ 100

B. Game of chess unfinished
8 × 8 のチェスの盤面が与えられる。
与えられた盤面がすでに終局しているかどうかを答える。
※ ここで「終局している」とは、黒のキングがどう動いても(動かなくても)次の白の手番で取られることをいう。
  つまり、2手以上先は読まなくていい。

与えれられる盤面は次のようなもの。
・ 盤面に駒は 4 つだけ
・ すなわち、白のルークが 2 つ、白のキングが 1 つ、黒のキングが 1 つ

C.
あとで読む。

D. Strange town
n (≦ 20) 頂点の完全グラフで、次の条件をみたすように辺の重みを定めよ。
・ グラフ中の任意の Hamilton 閉路の重みが等しい
・ 任意の 2 辺の重みは相異なる
・ 任意の辺の重みは 1 以上 1000 以下の整数

E.
あとで読む。

[ 解答 ]
言語は C++。include文とusing文は省略。
追記した分のコードはテンプレを使っている。テンプレはここを参照。

A.
const double EPS=1e-9;

int main(){
int n,v; cin>>n>>v;
int a[20],b[20];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
double xmax=-1;
for(int i=0;i<n;i++){
double x=1.*b[i]/a[i];
bool ok=true;
for(int j=0;j<n;j++){
if(b[j]+EPS<a[j]*x) ok=false;
}
if(ok) xmax=max(xmax,x);
}
double sum=0;
for(int i=0;i<n;i++) sum+=a[i]*xmax;
printf("%.9f\n",min(1.*v,sum));

return 0;
}

とりあえず、鍋の大きさは無視して考えると、
ボルシチを作れるだけ作った状態では、少なくとも 1 種類の材料を使い切っているはず。
そうでなければ、もうちょっと多くのボルシチが作れるはずだから。

なので、どの材料を使い切ったのかを全部調べればいい。
材料 i を使い切ったとしたとき、他の材料の使用量もすべて決まるので、その使用量が今ある材料の量を超えないかどうかをチェックして、超えていなければそれが答えの候補になる。
答えの候補の中で最大のものが答え。
ただし、それが鍋の大きさを超えている場合は鍋の大きさに丸める。

もっとスマートな思考ルートがあると思う。

B.
#define mp  make_pair

typedef pair<int,int> pii;

char board[8][8];

bool checkmate(pii bk){
bool chk[8][8]={};
for(int y=0;y<8;y++)for(int x=0;x<8;x++){
if(board[y][x]=='\0') continue;
chk[y][x]=true;
if(board[y][x]=='R'){
for(int i=y+1;i<8;i++){
if(board[i][x]=='\0') chk[i][x]=true;
else break;
}
for(int i=y-1;i>=0;i--){
if(board[i][x]=='\0') chk[i][x]=true;
else break;
}
for(int j=x+1;j<8;j++){
if(board[y][j]=='\0') chk[y][j]=true;
else break;
}
for(int j=x-1;j>=0;j--){
if(board[y][j]=='\0') chk[y][j]=true;
else break;
}
}
else if(board[y][x]=='K'){
for(int dy=-1;dy<=1;dy++)for(int dx=-1;dx<=1;dx++){
if(dx==0 && dy==0) continue;
int xx=x+dx,yy=y+dy;
if(0<=xx && xx<8 && 0<=yy && yy<8){
if(board[yy][xx]=='\0') chk[yy][xx]=true;
}
}
}
}

return chk[bk.first][bk.second];
}

int main(){
pii bk;
for(int i=0;i<4;i++){
char s[3]; cin>>s;
if(i<3) board[s[0]-'a'][s[1]-'1']=(i<2?'R':(i<3?'K':'B'));
else bk=mp(s[0]-'a',s[1]-'1');
}

bool ok=true;
for(int dy=-1;dy<=1;dy++)for(int dx=-1;dx<=1;dx++){
int xx=bk.second+dx,yy=bk.first+dy;
if(0<=xx && xx<8 && 0<=yy && yy<8){
char tmp=board[yy][xx];
board[yy][xx]='\0';
if(!checkmate(mp(yy,xx))) ok=false;
board[yy][xx]=tmp;
}
}

cout<<(ok?"CHECKMATE":"OTHER")<<endl;

return 0;
}

黒のキングが動けるマスは (動かない場合も含めて) 高々 9 マスだけ。
全部シミュレートすればいい。
コードは、何もないマスにはNULL文字が入るという謎の仕様。
本番中に submit したものに少しだけ手を加えてある。

C.



D. (時間外)
int main(){
int n; scanf("%d",&n);
int mark[20]={0,1};
for(int i=2;i<n;i++){
int p;
for(p=2;;p++){
rep(a,i)rep(b,a)rep(c,i) if(mark[a]+mark[b]==mark[c]+p) goto BAD;
break;
BAD:;
}
mark[i]=p;
}

rep(u,n)rep(v,n) printf("%d%c",u==v?0:mark[u]+mark[v],v<n-1?' ':'\n');

return 0;
}

[ 2011/03/25 追記 ]

2 時間くらい考えても分からなかったので答えを見た。
とても賢い解法があって驚いた。

各頂点に適当に重みをつける。
辺の重みを両端点の重みの和と定めれば、当然、任意の Hamilton 閉路の重みは等しくなる。

あとは頂点の重みをどのように定めるかだけど、これは、使える数を小さいものから Greedy に割り当てていくだけでいい。
ちなみに、この数列は 0, 1, 2, 4, 7, 12, 20, 29, ... で、ここにも載っている。

E.



あとの問題はまた考えよう。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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