Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

天下一プログラマーコンテスト2013予選B C - 天下一ジグソーパズルふたたび (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

縦$N$マス,横$M$マス,全体で$NM$ピースのジグソーパズルを考える.
上下左右に隣り合うピースは,片方が凹で,片方が凸,端の辺は直線.
KLabのマークであるKっぽい,1辺が直線,3辺が凹のピースの数を最大がしたい.
ただし,4辺とも凹のピースを$A$個以上使って,4辺とも凸のピースが最大でも$B$個までしか使えない.
$2 \leq N, M \leq 8$.
部分点もある.(原文を参照)

解法

DPする.
左上から順番にピースを決めて行って,
 今の場所,4辺凹のピースを使った数,4辺凸のピースを使った数,過去1列分の下向きに接する面は凸か凹か?,一つ左のピースの右側の辺は凸か凹か?
を状態として,K型のピースの最大値をメモする.
状態数は多く見積もっても$1.2 \times 10^7$以下程度だが,配列で愚直にメモリ確保するとMLEに引っかかる可能性があるのに注意する.
いろいろ頑張って枝刈りすれば全探索も可能らしい.

C++によるスパゲッティなソースコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
#include<cassert>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll read_int(ll mn, ll mx, char next){
  ll c, fg = 1, res = 0;
  c=getchar();
  if(c=='-') fg = -1, c = getchar();
  assert('0'<=c && c<='9');
  res = c - '0';
  for(;;){
    c = getchar();
    if(c==next) break;
    assert(res!=0);
    assert('0'<=c && c<='9');
    res = res * 10 + (c - '0');
  }
  res *= fg;
  assert(mn<=res && res<=mx);
  return res;
}


#define ull unsigned ll
signed char memo[13000000];

int mp[10][10];
int UP=1, RT=2, DN=4, LF=8;
int IN_A, IN_B;

int solve_slow(int X, int Y, int a, int b, int A, int B){
  int i, j, k, pre, p1, p2, mask, inner, edge;
  int nA, nB, nn;
  int res = -1, tmp;
  int hs;

  hs = a * (Y + 1) + b;
  hs = hs * (IN_A + 1) + A;
  hs = hs * (IN_B + 1) + B;

  hs *= 2;
  if(b && (mp[a][b-1]&RT)) hs++;
  rep(i, Y){
    j = a;
    if(i >= b) j--;
    hs *= 2;
    if(j >= 0 && mp[j][i]&DN) hs++;
  }

  assert(hs < 13000000);

  if(memo[hs] != -2) return memo[hs];

  if(a == X){
    if(A > 0) return memo[hs] = -1;
    return memo[hs] = 0;
  }

  if(b==Y){
    return memo[hs] = solve_slow(X, Y, a+1, 0, A, B);
  }

  pre = 0;
  if(a && !(mp[a-1][b]&DN)) pre += UP;
  if(b && !(mp[a][b-1]&RT)) pre += LF;

  rep(p1,2) rep(p2,2){
    mask = pre;
    if(p1) mask += DN;
    if(p2) mask += RT;
    
    if(a==X-1 && (mask & DN)) continue;
    if(b==Y-1 && (mask & RT)) continue;

    mp[a][b] = mask;
    inner = 1;
    if(a==0 || a==X-1 || b==0 || b==Y-1) inner = 0;

    edge = 1-inner;
    if( (a==0&&b==0) || (a==X-1&&b==0) || (a==0&&b==Y-1) || (a==X-1&&b==Y-1) ) edge = 0;

    nA = A; nB = B; nn = 0;
    if(inner && mask == 0) nA--;
    if(inner && mask ==15) nB--;
    if(nA < 0) nA = 0;
    if(nB < 0) continue;

    if(edge && mask==0) nn++;

    tmp = solve_slow(X, Y, a, b+1, nA, nB);
    if(tmp==-1) continue;

    if(res < tmp + nn) res = tmp + nn;
  }

  return memo[hs] = res;
}

int main(){
  int N, M, A, B;
  int i, res;

  N = read_int(2, 8, ' ');
  M = read_int(2, 8, ' ');
  IN_A = A = read_int(0, (N-2)*(M-2), ' ');
  IN_B = B = read_int(0, (N-2)*(M-2), '\n');
  assert( A + B <= (N-2)*(M-2) );

  rep(i,13000000) memo[i] = -2;

  if(M > N) swap(M, N);
  res = solve_slow(M, N, 0, 0, A, B);
  assert(res != -1);
  printf("%d\n",res);

  {
    char c;
    assert( scanf("%c",&c)!= 1 );
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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