POJ 3312 Mahershalalhashbaz, Nebuchadnezzar, and Billy Bob Benjamin Go to the Regionals

問題

n人の人をk人ずつチームにわける。
各チームにおいて、
「チームの全員の名前の長さの平均」と任意の人の名前の長さの差が2を超えてはいけない。

このとき、チーム分けが可能であるかどうか、判定せよ。

制約条件

n≦1000
kはnの約数
各人の名前は80文字以下

方針

名前を長い順にソートして、順にk人ずつわける。

これで可能なことが必要十分である。
らしいのだが、証明をしようとして示せなかった……

（グループの二つの要素を入れ替えてもよいという典型的な証明は無理である。
1 1 5 5 | 3 3 3 3みたいな例があるため）

[追記]
同級生に指摘されたのだが、
1 1 5 5 | 4 6 6 6のような例では、greedyにグループを取ると
上のような並びではダメである。

ということで、これは多分嘘解法。

ソースコード

int n,k,len[1000];
char in[99];

int main(){
  int cs=1;
  while(scanf("%d%d",&n,&k),n){
    rep(i,n){
      scanf("%s",in);
      len[i]=strlen(in);
    }
    sort(len,len+n);
    printf("Case %d: ",cs++);
    int sum=0;
    for(int i=0;i<n;i+=k){
      double ave=0;
      rep(j,k)ave+=len[i+j]*1.0/k;
      rep(j,k)if(abs(len[i+j]-ave)>2+1e-9){
        puts("no"); goto END;
      }
    }
    puts("yes");
    END:puts("");
  }
  return 0;
}
|<

*1320815603*[PKU][再帰]POJ 3316 Snakes on a Plane
** 問題
hxwのグリッドが与えられる。
各マスは'0'または'1'で、「蛇」とは縦または横（のみ）につながった1のかたまりを言う。
グリッド中のmaximalな蛇の数を求めよ。


maximalな蛇とは以下を満たす蛇のことである。
- 蛇に隣接する任意の'0'のマスを、他の蛇や自分の他の部分にくっつかないよう'1'にして、蛇の長さを長くすることができない。

** 制約条件
h,w≦200

** 方針
問題文で与えられた通りに愚直にメモ化再帰して、それぞれの蛇がmaximalであるかどうか判定すればいい。

** ソースコード
>|cpp|
const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w;
char in[200][201];
int memo[200][200];

int maximal(int y,int x){
  if(memo[y][x]>=0)return memo[y][x];
  int &res=memo[y][x];
  res=100;
  
  int one=0;
  rep(d,4){
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=h||nx>=w||in[ny][nx]=='0')continue;
    one++;
    if(memo[ny][nx]==0||memo[ny][nx]<0&&!maximal(ny,nx))return res=0;
  }
  if(one>=3)return res=0;
  
  if(one<=1){
    rep(d,4){
      int ny=y+dy[d],nx=x+dx[d];
      if(ny<0||nx<0||ny>=h||nx>=w||in[ny][nx]!='0')continue;
      int one2=0;
      rep(e,4){
        int my=ny+dy[e],mx=nx+dx[e];
        if(my<0||mx<0||my>=h||mx>=w||in[my][mx]!='1')continue;
        one2++;
      }
      if(one2==1)return res=0;
    }
  }
  return res=1;
}
int main(){
  while(scanf("%d%d",&h,&w),h){
    rep(i,h)scanf("%s",in[i]);
    rep(i,h)rep(j,w)memo[i][j]=-1;
    int ans=0;
    rep(i,h)rep(j,w)if(in[i][j]=='1'&&memo[i][j]<0){
      if(maximal(i,j))ans++;
    }
    printf("%d\n",ans);
  }
  return 0;
}