スポンサーサイト

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

Codeforces Beta Round #74

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

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

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

結果

A. Hacked, AC (01:50)
B. -
C. Hacked
D. -
E. -
Hacks : +-0 (0/0)
Standing : 230/430
Rating : 19151847


問題

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

A. Robbery
n 個の一列に並んだ箱がある。
箱 i には ai 個のダイヤモンドが入っている。

泥棒は、できるだけ多くのダイヤモンドを盗みたい。
泥棒は次の 3 種類の操作ができる。
・ 1 つのダイヤモンドを 箱 から 箱 に移す
・ 1 つのダイヤモンドを 箱 から 泥棒のポケット に移す
・ 1 つのダイヤモンドを 泥棒のポケット から 箱 に移す
操作できる回数は 1 分間に高々 m 回。

部屋にはセキュリティシステムがあり、毎分、各箱のダイヤモンドの個数をチェックする。
隣りあう箱にあるダイヤモンドの和が異なっているものがあれば、警報が鳴る。
すなわち、 i = 1, 2, .., n-1 に対して、ai + ai+1 が 1 分前と異なるものがあれば警報が鳴る。

警報が鳴らないように、泥棒が k 分間で盗むことのできるダイヤモンドの最大個数を求めよ。
( k 分間たったあとに警報が鳴るのもダメ )

1 ≦ n ≦ 104
1 ≦ ai ≦ 105
1 ≦ m, k ≦ 109

B. Widget Library
Widget, HBox, VBox という 3 種類の部品がある。
どの部品も長方形の形状。
Widget は、中に何も入れることができず、サイズが固定されている。
HBox と VBox は、中に部品を入れることができ、中の部品に合わせてサイズが変わる。
HBox と VBox の違いは、中の部品を水平方向に並べるか、垂直方向に並べるか。
HBox と VBox には border, spacing というパラメータがあり、それぞれ、余白の幅と中の部品の間隔をあらわす。

問題文中で定義されるスクリプト言語で書かれたコードが与えられるので、各部品のサイズを求めよ。

C. Chip Play
n × m のグリッドで、各マスは、矢印が書かれているか何もないかのいずれか。
矢印のマスにいるとき、別の矢印マスに着くまで、矢印の方向に直進する。
一度踏んだ矢印マスは 2 度目以降は機能しない。

グリッドの外に出るまでに踏んだ矢印マスの最大個数と、その個数を達成するスタート位置の個数を答えよ。

1 ≦ n×m ≦ 5000

D.

E.

解答

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

A.
int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
int a[10000];
rep(i,n) scanf("%d",a+i);

if(n%2==0){ puts("0"); return 0; }

int a_min=1000000;
for(int i=0;i<n;i+=2) a_min=min(a_min,a[i]);

int n_ope=m/(n/2+1);
printf("%d\n",(int)min((ll)a_min,(ll)k*n_ope));

return 0;
}

サンプルにもあるように、両端のダイヤモンドは 1 回しか足されないので、それをうまく使う。
紙に書いて実際にやってみると、
  • 箱が偶数個のときは、1 つも盗めない

  • 箱が奇個のときは、
    奇数番目の箱のダイヤモンドを偶数番目の箱に 1 つずつ移す。余った 1 つのダイヤモンドを盗む
    とするしか方法がない。
    この動かし方では、奇数番目のダイヤモンドが 1 つずつ減るので、その最小値が上界になる。
    また、1 つを盗むのに (n+1)/2 回の操作がいるので、m, k に関する制限からもう一つの上界が出る。


  • B. (時間外)
    typedef pair<ll,ll> pll;

    enum{WIDGET,HBOX,VBOX};
    struct Widget{
    int w,h,type,spacing,border;
    vector<string> item;
    Widget(){}
    Widget(int W,int H,int T):w(W),h(H),type(T),spacing(0),border(0){}
    };

    map<string,Widget> f;
    map<string,pll> memo;

    pll calc(const string &name){
    if(memo.count(name)) return memo[name];

    const Widget &wi=f[name];
    ll w,h;
    if(wi.type==WIDGET) w=wi.w, h=wi.h;
    else{
    if(wi.item.size()==0) w=h=0;
    else{
    if(wi.type==HBOX){
    w=2*wi.border+(wi.item.size()-1)*wi.spacing; h=0;
    rep(i,wi.item.size()){
    pll tmp=calc(wi.item[i]);
    w+=tmp.first;
    h=max(h,tmp.second+2*wi.border);
    }
    }
    else{ // wi.type==VBOX
    w=0; h=2*wi.border+(wi.item.size()-1)*wi.spacing;
    rep(i,wi.item.size()){
    pll tmp=calc(wi.item[i]);
    w=max(w,tmp.first+2*wi.border);
    h+=tmp.second;
    }
    }
    }
    }

    return memo[name]=make_pair(w,h);
    }

    int main(){
    int n; cin>>n;
    rep(i,n){
    string s; cin>>s;
    if(s[0]=='W'){ // Widget [name]([x],[y])
    cin>>s; s[s.find('(')]=' ';
    char name[16];
    int x,y;
    sscanf(s.c_str(),"%s%d,%d",name,&x,&y);
    f[name]=Widget(x,y,WIDGET);
    }
    else if(s[0]=='H'){ // HBox [name]
    cin>>s;
    f[s]=Widget(0,0,HBOX);
    }
    else if(s[0]=='V'){ // VBox [name]
    cin>>s;
    f[s]=Widget(0,0,VBOX);
    }
    else{
    int p=s.find('.');
    string name=s.substr(0,p);
    s[s.find('(')]=s[s.find(')')]=' ';

    if(s[p+5]=='b'){ // [name].set_border([x])
    int x;
    sscanf(s.c_str(),"%*s%d",&x);
    f[name].border=x;
    }
    else if(s[p+5]=='s'){ // [name].set_spacing([x])
    int x;
    sscanf(s.c_str(),"%*s%d",&x);
    f[name].spacing=x;
    }
    else{ // [name1].pack([name2])
    char name2[16];
    sscanf(s.c_str(),"%*s%s",name2);
    f[name].item.push_back(name2);
    }
    }
    }

    map<string,Widget>::iterator it;
    for(it=f.begin();it!=f.end();++it){
    pll sz=calc(it->first);
    cout<<it->first<<' '<<sz.first<<' '<<sz.second<<endl;
    }

    return 0;
    }

    [ 2011/07/15 追記 ]

    がんばって実装してくださいという問題なので、がんばって実装するしかない。
    各部品のサイズを求めるときは、もちろんメモ化しないといけない。

    C. (時間外)
    int m,n,dir[128];
    char field[5001];

    int prev[5000][4],next[5000][4];

    inline int code(int y,int x){
    if(0<=y && y<m && 0<=x && x<n) return y*n+x;
    return INF;
    }

    int solve(int id,int k){
    int ans=0;
    while(id!=INF){
    int nextdir;
    if(field[id]=='.'){
    nextdir=k; // go straight
    }
    else{
    ans++;
    nextdir=dir[field[id]]; // curve

    // reconnect links
    rep(i,4){
    if(next[id][i]!=INF) prev[next[id][i]][i]=prev[id][i];
    if(prev[id][i]!=INF) next[prev[id][i]][i]=next[id][i];
    }
    }
    id=next[id][nextdir];
    k=nextdir;
    }

    return ans;
    }

    int main(){
    dir['R']=0; dir['U']=1; dir['L']=2; dir['D']=3;

    scanf("%d%d",&m,&n);
    rep(i,m) scanf("%s",field+n*i);

    int ans=0,ans2=0;
    rep(id,m*n) if(field[id]!='.') {
    // make links
    rep(id2,m*n){
    int i=id2/n,j=id2%n;
    rep(k,4){
    prev[id2][k]=code(i-dy[k],j-dx[k]);
    next[id2][k]=code(i+dy[k],j+dx[k]);
    }
    }

    int tmp=solve(id,0);
    if(ans==tmp) ans2++;
    else if(ans<tmp){ ans=tmp; ans2=1; }
    }
    printf("%d %d\n",ans,ans2);

    return 0;
    }

    普通にシミュレーションすると、最悪ケースで 50003 回くらいのイテレーションが起こるので間に合わない。
    2 次元の連結リスト (各方向について、次はどのマスに移るか) を作って、矢印を踏むたびにリストを更新するようにすればいい。

    D.



    E.



    感想

    A.
    開始 40 分くらいで submit できたのに、オーバーフローしていてすぐに Hack された。
    Hack されてもずっと C を考えていたので、再提出したのは終了 10 分前。

    C.
    普通にシミュレーションしても O(n2m2) で終わると思い込んでしまって、あっさり Hack された。
    Div.1 Only の C が書くだけなわけなかった。
    Hack されてからは、上記の連結リスト解法を書こうとがんばっていたけど、A も Hack されて焦っていたせいか、最後までバグがとれなかった。

    上記の解法でもシミュレーションを再帰で書くと TLE になったので、Time Limit はかなり厳しい印象。
    ボトルネック中で呼ばれる関数に inline をつけるかどうかだけで実行時間が 0.6 sec も変わったので、inline も案外ばかにならない。
    スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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