UVa : 10364 - Square - Respect2Dの日記

問題概要

M本(4以上20以下)の長さが様々な棒が与えられる。
これらM本の棒を使って正方形の4つの辺を作ることができるか答えよ。
棒は折ったり曲げたりしてはいけません。

解法

まず、正方形を絶対作れない場合を考えましょう。
棒の長さを全部足し合わせて、もしこの数字が4で割り切れなければ絶対に正方形を作れないですよね。もし、4で割り切れるならば、正方形になる可能性を持っています。
ここで、(棒の長さの合計 / 4)をlenと置きます。

さて、本当に正方形を作れるかどうかは、以下のDPで解けます。

dp[正方形の辺を何本作ったか(4)][どの棒を使用したか(2^M)] = このようなパターンを作れるか否か(0 or 1)

dp[4][2^M]が1になっていれば答えはyesです。

dp[i][j]からの遷移は以下のようになります。

jに含まれない新たな棒kを追加しようとするときのことを考える
- kを追加することで、使用している棒の長さの合計が、lenの倍数になるならば
  - dp[i + 1][j | (1 << k)]が1になる
  - これは、lenの倍数になると、正方形の辺が１本増えるため
- kを追加することで、使用している棒の長さの合計が、len*(i+1)より小さくなるならば
  - dp[i][j | (1 << k)]が1になる
- もし、長さの合計がlen*(i+1)より大きくなってしまう場合は、棒を折り曲げたりしないと、正方形の辺を増やすことができないので無視

プログラム

#include <iostream>
#include <cstring>
using namespace std;

int n;
int t[21];
bool dp[5][1 << 21];

void solve(){
  int sum = 0;
  for(int i = 0; i < n; i++){
    sum += t[i];
  }

  if(sum % 4 != 0){
    cout << "no" << endl;
    return;
  }

  int len = sum / 4;
  int maxBit = 1 << n;

  memset(dp, 0, sizeof(dp));
  dp[0][0] = true;

  for(int i = 0; i < 4; i++){
    for(int j = 0; j < maxBit; j++){
      if(!dp[i][j]) continue;

      //使用している棒の長さの合計を求める
      sum = 0;
      for(int k = 0; k < n; k++){
        if(!(j & (1 << k))) continue;
        sum += t[k];
      }

      //現在構築中の辺の長さだけ取得
      sum -= i * len;

      for(int k = 0; k < n; k++){
        if(j & (1 << k)) continue;
        if(sum + t[k] == len){ //今構築中の辺が完成する場合
          dp[i + 1][j | (1 << k)] = true;
        }
        else if(sum + t[k] < len){ //今構築中の辺がまだ完成しない場合
          dp[i][j | (1 << k)] = true;
        }
      }
    }
  }

  cout << (dp[4][maxBit - 1] ? "yes" : "no") << endl;
}

int main(){
  int T;
  cin >> T;

  while(T--){
    cin >> n;
    for(int i = 0; i < n; i++){
      cin >> t[i];
    }
    solve();
  }
}