TCO13 Round1B

Easy:
２人組みを作る。１組の能力は２人の能力の合計。
一人ひとりの能力の配列が与えられるので、一番能力が高いペアと低いペアとの能力差の最小値を求めよ。

一番能力が高い奴は一番能力が低い奴とペアを組むべき。
ソートしてそれぞれに求めて最大値-最小値が答え。

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
class EllysPairs {
public:
  int getDifference(vector <int> in) {
    sort(in.begin(),in.end());
    int n=in.size();
    int _min = 1<<30;
    int _max = 0;
    rep(i,n/2){
      int k = in[n-1-i] + in[i];
      _min = min(_min,k);
      _max = max(_max,k);
    }
    return( _max - _min );
  }
};

Mid:
vector boardが与えれる。これは'.'と'X'の2つで構成される。
'X'を全て取り除きたい。
1手につき、連続したR行又はC列に含まれている'X'を取り除く事ができる。
最小何手で'X'を全て取り除けるかを求めよ。

ある'X'は最終的に消されなければならないので、今の盤面の中の'X'1つに注目し、それを取り除くようなすべての行および列の選び方を子ノードにするようにBFS。

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
class EllysFigurines {
public:
  int getMoves(vector <string> board, int R, int C) {
    int w = board[0].size();
    int h = board.size();

    queue<pair<int,vector<string> > > Q;
    Q.push(make_pair(0, board));

    while(true){
      int step = Q.front().first;
      vector<string> F = Q.front().second;
      Q.pop();

      bool ok = true;
      int r,c;
      rep(i,h){
        rep(j,w){
          if(F[i][j] == 'X'){
            r = i;
            c = j;
            ok = false;
          }
        }
      }
      if(ok) return step;

      rep(dx,C){
        vector<string> f = F;
        for(int j=c-dx; j<c-dx+C; ++j){
          if(j<0 || j>=w)continue;
          rep(i,h) f[i][j] = '.';
        }
        Q.push(make_pair(step+1, f));
      }

      rep(dy,R){
        vector<string> f = F;
        for(int i=r-dy; i<r-dy+R; ++i){
          if(i<0 || i>=h)continue;
          rep(j,w) f[i][j] = '.';
        }
        Q.push(make_pair(step+1, f));
      }
    }
  }
};