解いた問題のソースコードと解説など。


POJ 2287 Tian Ji -- The Horse Racing

問題文

長さnの数列が2つ与えられる(a,bとする)。この2つの数列の数字同士を全てカップリングさせてaの方の数字が大きれば+200点。bの方が大きければ-200点。得点を最大化せよ、という問題。

DP強化週間のつもりが貪欲。=の時をうまく扱えずに人の答えを見てしまった。
コードと自分なりの解説を載せておく。

int main(int argc, char **argv){
  int n;
  while(cin >> n, n){
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int ans = 0;
    int la = 0, lb = 0, ra = n - 1, rb = n - 1;
    for(int i = 0; i < n; i++){
      if(a[la] > b[lb]){
	ans += 200;
	la++;
	lb++;
      }else if(a[ra] > b[rb]){
	ans += 200;
	ra--;
	rb--;
      }else{
	if(a[la] < b[rb])
	  ans -= 200;
	la++;
	rb--;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

まず数列をソートするところまではいい。
if文とelse if文の中は数列の左側と右側から今注目してるインデクス同士でaの方が大きいか調べているだけ。これもまあいい。
else文の中は下の図のような状況を想定すると分かりやすい。ここでかならず
a[la] <= b[rb]が成り立つが、a[la] == b[rb]であり続ける限りは-200になるようなマッチングは避けられる。
f:id:Area1:20130208233806p:plain:w100
しかしこんな↓状況(つまりa[la] < b[rb])であれば
f:id:Area1:20130208234939p:plain:w100
いずれ-200になるマッチングが発生するのでそれならなるべく弱いaの対抗馬をなるべく強いbの馬と合わせて-200してしまおう、という考え。

なるほどねえ。ただ、なるべく強いaの馬を僅差で勝てる程度のbの馬にあてがおうという考えのみでいくと両側からマッチングしていこうという発想になりにくいかもしれないな。

Get up! 明日のSUPER ST@R!