UVa 12520 : Square Garden

問題リンク:http://uva.onlinejudge.org/external/125/12520.html

問題概要：
L*Lの1*1のセルからなる正方形がある
自分はそのセルの中からN個選んで色をつける
色がついたセルの周囲の長さの最大値を求めよ

解法：
※画像が死んで見えない場合はクリック
市松模様に塗ってから残りを貪欲に塗っていく

正方形の一辺の長さが偶数か奇数かで計算方法が異なるので注意

・Lが偶数の場合
NがL*L/2以下の場合は明らかに市松模様にセルを塗ったほうが良い
そうでない場合、市松模様に塗った後にできるだけ周囲が減らないように貪欲に色を塗っていくと良い
以下はNがL*L/2より大きい場合を考える
市松模様にセルを塗る　
塗り方は2通りあるが左右反転させただけで同一のものなので実際は１通りだけ
以下の画像のように塗る

次に残った分の色を塗っていくのだが、
色を塗った時に一番影響が少ないところから貪欲に塗っていく
以下の画像のセルに書いてある数字は、そこに色を塗った場合現在の周囲からどの位周囲が変化するかを表す
そのセルに隣接する赤い線の数だけ周囲が減り、青い線の数だけ周囲が増加する

このセルの数字が大きいほう(0から)から順番に色を塗っていくと周囲の減少が少なくてすむ

・Lが奇数の場合
奇数の場合、市松模様に塗る方法が2通り存在し、両方とも異なる形をしているためその2通りについて考え、周囲の大きいほうが答えとなる
１つ目の塗り方とその時の周囲の変化は以下の通り

２つ目の塗り方とその時の周囲の変化は以下の通り

画像の意味は偶数の時の画像と同じ

今年のTCOのラウンド２のAのeasyがこれの下位互換(?)だった
大きいものから市松模様に配置していき、
残ったものを小さい方からセルの数字の小さいものとマッチさせるようにしながらやる
引く数 * 縦の長さ　とすれば同様の方法で解く事ができる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

inline void calc(ll &N,ll &ret,ll zero,ll two,ll four){
  ret -= min(zero,N) * 0LL;
  N -= min(zero,N);
  ret -= min(two,N) * 2LL;
  N -= min(two,N);
  ret -= min(four,N) * 4LL;
  N -= min(four,N);
}

inline ll compute(ll len,ll N){
  if( len & 1LL ){
    ll ans = 0LL;
    // Pattern 1
    ll half = (len*len) / 2LL + 1LL;
    if( half >= N ) return 4LL * N;
    ll ret = 4LL * half;
    N -= half;

    ll N_tmp = N;
    half--;
    ll zero = 0LL;
    ll two  = ( ( len - 2LL ) / 2LL + 1LL) * 4LL;
    ll four = half - ( zero + two );
    calc(N,ret,zero,two,four);
    ans = ret;

    // Pattern 2
    ret = 4LL * half;
    half++;
    N = N_tmp+1;
    zero = 4LL;
    two  = ( ( len - 2LL ) / 2LL ) * 4LL;
    four = half - ( zero + two );
    calc(N,ret,zero,two,four);
    ans = max(ans,ret);
    return ans;
  } else {
    ll half = (len*len) / 2LL;
    if( half >= N ) return 4LL * N;
    ll ret = 4LL * half;
    N -= half;
    ll zero = 2LL;
    ll two  = ( ( len - 2LL ) / 2LL ) * 4LL;
    ll four = half - ( zero + two );
    calc(N,ret,zero,two,four);
    return ret;
  }

}

int main(){
  ll L,N;
  while( cin >> L >> N, L | N ) cout << compute(L,N) << endl;
  return 0;
}