TopCoderOpen Algorithm 2014 Round 2A EASY - SixteenBricks

Source

TopCoderOpen Algorithm 2014 Round 2A EASY (250pt)
Problem Statement

問題概要

幅,奥行きのサイズが $1$ で高さ $H_k$ の直方体のブロック($k=1,2,\ldots,16$)が $1$ 個ずつ,合計 $16$ 個ある.
各マスの幅,奥行きのサイズが $1$ の$4$ 行 $4$ 列の盤面の各マスにブロックを置く.
できたブロックから成る物体の表面積の最大値を求める問題.
ブロックの上の面は表面積に含めるが,下の面(テーブルに面する面)は表面積に数えない.

解法

Greedy.
他のブロックと接する面積(消える表面積)を最小化すれば良い.
$4 \times 4$ の盤面を市松模様に塗り分け,その片方に高い方から $8$ 個のブロックを,もう片方に小さい方の $8$ 個のブロックを置く.
大きいブロックを適当においた後,小さいブロックを置いた時に消える表面積を考える.
それは,大きいブロックの置き方に依存せず,置く場所と接するブロックの数と,置くブロックの高さ(の積)に依存する.
よって,接するブロックが多い真ん中には最も小さいブロックを,接する部分の少ない角には,小さい $8$ 個のブロックの中でも大きい物を置くようにする.
大きい方から置く,小さい方から置くとして,すでに置かれているマスの集合を状態としてDPすることもできる(らしい).

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

class SixteenBricks {
public:
int maximumSurface(vector <int> h) {
  int i, j, k, n = 16;
  int mp[6][6] = {};
  int res = 0;

  sort(h.begin(), h.end());

  k = 0;
  mp[2][2] = h[k++];
  mp[3][3] = h[k++];
  mp[1][3] = h[k++];
  mp[2][4] = h[k++];
  mp[3][1] = h[k++];
  mp[4][2] = h[k++];
  mp[1][1] = h[k++];
  mp[4][4] = h[k++];
  rep(i,4) rep(j,4) if(mp[i+1][j+1]==0) mp[i+1][j+1] = h[k++];

  rep(i,4) rep(j,4){
    res += 1;
    res += max(0, mp[i+1][j+1] - mp[i][j+1]);
    res += max(0, mp[i+1][j+1] - mp[i+1][j]);
    res += max(0, mp[i+1][j+1] - mp[i+1][j+2]);
    res += max(0, mp[i+1][j+1] - mp[i+2][j+1]);
  }

  return res;
}

}

Current time: 2024年03月29日21時53分05秒
Last modified: 2014年05月18日19時14分47秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_2A
トップページに戻る

Logged in as: unknown user (not login)

ログイン: