5001 - Making Quadrilaterals

ACM-ICPC live archive

5001 - Making Quadrilaterals
Asia - Kuala Lumpur - 2010/2011
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5001

問題概要

長さが整数の棒をn本もっているときに、
四角形が作れない持ち方でかつ、
最も長い辺の最小値を求めよ。

解法

DP?
四角形ができない条件として、

  • ある棒sについて、sの長さよりそれ以下の長さの棒3本の長さを足しあわせても、

sの長さより大きくならないこと。

  • 上記の条件が全ての棒について当てはまること。

である。
今n本の解を求めたい場合、

  • もし、n本の解でn-1本の解を含まない解の方が、n-1本の解より小さいものが存在すれば、その最大の辺を取り除いても四角形がつくれないはずであるので、n-1本の解についても最適なものが見つかってしまうので矛盾。

よって、n-1本の解に棒を足していくことで最適ケースが作れる。その棒の足し方は、

  • n-1本の解の最大の辺より小さな辺を追加できると仮定すると、n-1本の解がより良い解が見つかるということになり矛盾。
  • n-1本の解の最大の辺と同じ長さの辺を追加できると仮定すると、その追加した辺が
    • ある棒sについて、sの長さよりそれ以下の長さの棒3本の長さを足しあわせても、

sの長さより大きくならないこと。
という条件に当てはまらないので解に適さない。

  • n-1本の解の最大の辺より長い辺は、n-1本の解で作れる最大の3本の合計（つまり長い方から三本）以上の辺を加えられる。

よって、n-1本の解の長い方から3本を足しあわせたものがn本の解の最大の長さの辺である。

ソース

#include<iostream>
#include<cstdio>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)

using namespace std;
typedef unsigned long long lli;
const int N = 61;

lli t[N][3];

void solve(){
  t[4][0] = 1;
  t[4][1] = 1;
  t[4][2] = 3;
  REP(i, 5, N){
    t[i][0] = t[i-1][1];
    t[i][1] = t[i-1][2];
    t[i][2] = t[i-1][0] + t[i-1][1] + t[i-1][2];
  }
}

int main(){
  solve();
  int n;
  int tc = 0;
  while(cin >> n){
    if( n == 0)break;
    tc++;
    printf("Case %d: %Ld\n",tc, t[n][2]); 
  }
  return 0;
}