Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2186-cac9f364
この記事にトラックバックする(FC2ブログユーザー)

Round #102 DIV1 C問題/DIV2 E問題 - Help Caretaker (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 C問題 (1500pt)
Codeforces Round #102 DIV2 E問題 (2500pt)
Problem description

問題概要

n*m (9*9以下) のグリッドに,Tの字のピース (問題文の図を参照,90度単位で回転しても良い) を最大で何個置くことが出来るか.
置ける数と,置き方を1つ求める問題.

解法

枝刈り全探索.
既においた数 + まだ見ていないセルのうち空きセルの数/5 が現在見つかってる答え以下なら枝刈り,で十分間に合った.
また,多少間に合わない程度なら答えを埋め込めば良い.
DPでも解けるっぽいのだけど,DPの方が計算時間も長くなるし,実装も複雑.(2行分だけ覚えておけば良いのでO(n*m*2^(2m))程度の状態数)

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x, y;
int mp[10][10];
int res[10][10], opt;

int dx[4][5] = { {0,0,0,1,2}, {0, 1, 1,1,2}, {0,1, 2,2,2}, {0,1,1,1,2} };
int dy[4][5] = { {0,1,2,1,1}, {0,-2,-1,0,0}, {0,0,-1,0,1}, {0,0,1,2,0} };

int is_ok(int a, int b, int k){
  int i,na,nb;
  rep(i,5){
    na = a + dx[k][i];
    nb = b + dy[k][i];
    if(na < 0 || nb < 0 || na >= x || nb >= y || mp[na][nb]>=0) return 0;
  }
  return 1;
}

void go_put(int a, int b, int k, int c){
  int i,na,nb;
  rep(i,5){
    na = a + dx[k][i];
    nb = b + dy[k][i];
    mp[na][nb] = c;
  }
}

void solve(int a, int b, int now){
  int i,j,k;

  if(a==x){
    if(opt < now){
      opt = now;
      rep(i,x) rep(j,y) res[i][j] = mp[i][j];
    }
    return;
  }
  if(b==y){
    solve(a+1,0,now);
    return;
  }

  k = 0;
  REP(i,a,x) rep(j,y){
    if(i==a && j<b) continue;
    if(mp[i][j]==-1) k++;
  }
  if(now + k/5 <= opt) return;

  rep(k,4) if(is_ok(a,b,k)){
    go_put(a,b,k,now);
    solve(a,b+1,now+1);
    go_put(a,b,k,-1);
  }
  solve(a,b+1,now);
}

int main(){
  int i,j,k,l,m,n;

  while(scanf("%d%d",&x,&y)==2){
    rep(i,x) rep(j,y) res[i][j] = mp[i][j] = -1;
    opt = 0;

    solve(0,0,0);
    printf("%d\n",opt);
    rep(i,x){
      rep(j,y){
        if(res[i][j] == -1) putchar('.');
        else                putchar('A'+res[i][j]);
      }
      puts("");
    }
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2186-cac9f364
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。