Ritsumeikan University Programming Camp 2012 (Day 1)

立命館大学プログラミング合宿Day1、問題A,B,Fの詳細な解説を書きます。
C,D,E,Gの解説は@shioshiotaが書いてくれます。

Problem A

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1084
1~9までの数字がどれかひとつ書かれたn枚のカードを横に並べる。このときk枚の連続したカードに書かれている積の最大値をCkとする。また並べられた時点のCkをCk'とおく。2枚のカードを一回だけ交換して、Ck-Ck'を最大化せよ。

  • n<=100
  • k<=5
例

3,9,4,7でk=2の場合
3*9=27,9*4=36,4*7=28よりC2=36。
4と7を交換して
3,9,7,4
3*9=27,9*7=63,7*4=28よりC2=63。
この場合63が答えになります。なぜなら並べたカードが3,9,4,7でk=2のとき、どの2枚を交換してもC2を63より大きくすることは出来ないからです。

方針

カードの交換をすべて試して、Ckを求めるコードを書きましょう。
交換の仕方が(n*(n-1))/2、Ckの計算がn*k、テストケースの数が100なので、100*(100*99)/2*(100*5) = 247,500,000。少し多いですがなんとかなります。

解答例
#include<iostream>
#include<climits>
#include<cassert>
#include<algorithm>

using namespace std;

const int N = 100;

int getMaximum(int c[N], int n, int k)
{
  int maxi = INT_MIN;
  for(int st = 0; st <= n-k; ++st){
    int prod = 1;
    // cout << st << " : ";
    for(int i = 0; i < k; ++i){
      // cout << c[st+i] << ' ';
      prod *= c[st+i];
    }
    // cout << endl;
    maxi = max( maxi, prod );
  }
  return maxi;
}

int main()
{
  int tc=0;
  int n,k;
  while(true){
    cin>>n>>k;
    if( n == 0 && k == 0 ) break;

    ++tc;

    assert(2<=n && n<=100);
    assert(1<=k && k<=5);
    assert(k<=n);
    assert(tc<=100);

    int c[N];
    for(int i = 0; i < n; ++i){
      cin >> c[i];
      assert(1<=c[i]&&c[i]<=10);
    }
    int C_k;
    int res = INT_MIN;
    res = max(res, getMaximum(c,n,k));
    C_k = res;

    for(int i = 0; i < n; ++i){
      for(int j = i+1; j < n; ++j){
        swap(c[i],c[j]);
        /*
          for(int l = 0; l < n; ++l){
          cout << c[l] << ' ';
          }
          cout << endl;
        */
        res = max( res, getMaximum(c,n,k) );
        swap(c[i],c[j]);
      }
    }
    assert(res-C_k >= 0);
    cout << res-C_k << endl;
  }
  return 0;
}
補足

Ckを小さくすることしかできない場合"NO GAME"を出力せよ、と問題文にはありますが実際にそのようなケースを作ることは出来ません。なぜなら、k=1のときは交換操作はCkの最大値に関して意味をなさず、k>=2のときはCkを保つ自明な交換(そのk枚の中で交換)が存在するからです。つまりどんな場合でもCk'以上の値が保証されます。

Problem B

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1085
n個の(区別可能な)数から2つ選んで、その和がある値Sより大きくなるような選び方はいくつあるか。

例

5,9,9,8という4つの数があり、ここから2つ選んでその和が16より大きくなるような選び方は
(9,9)
(9,8) (ひとつめの9)
(9,8) (ふたつめの9)
の3つです。

方針

まず簡単な方法としてAと同様に2つの選び方を全て試す方法があります。この場合の計算量は選び方がn*(n-1)/2、テストケースの数が100なので、(20000*19999/2)*100 = 19,999,000,000 (約200億)。この量は3秒では少し厳しいところがあります。
この問題はn個の数の中のある数pに注目したとき、p+x>Sを満たすxが、n個の数の中にいくつ存在するかを聞いています。xはS-pより大きい数です。n個の数をソートすることで、S-pより大きい数を2分探索によって見つけることができます。また、そのxがある場所よりあとにある数はすべてS-pより大きいか等しいことがソートによって保証されます。

上の例ではソートすると5,8,9,9で、5に注目したとき16-5=11より大きい値を2分探索によって見つけなければなりません。しかしそのような数は存在しないので5はどんな数とペアにしても16より大きくならないことがわかります。8に注目した場合16-8=8より大きい値を見つけます。これには9が該当します。

2分探索に関してはhttp://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2を参照してください。探索とありますが、もちろんこの問題はS-pという数自体を見つける問題ではありません。2分探索で見つからない場合に、探索を打ち切った位置を答えに応用することを求めています。

またC++の場合、2分探索はlower_boundあるいはupper_boundというテンプレート関数を使用することで簡単に実装することができます。

解答例
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
  int n,S;
  while(true){
    cin >> n >> S;
    if( n == 0 && S == 0 ) break;

    int res = 0;
    int r[n];
    for(int i = 0; i < n; ++i){
      cin >> r[i];
    }
    sort(r,r+n);
    for(int i = 0; i < n; ++i){
      int *low = upper_bound(r,r+n,S-r[i]);
      //low = max(low, r+i+1);
      int x = (r+n) - low;
      if( r[i] + r[i] > S ) --x;
      //cout << r[i] << ' ' << x << endl;
      res += x;
    }
    cout << res/2 << endl;
  }
  return 0;
}
補足

約200億では厳しいと書きましたが実際には100ケースすべて2万個の数字があるわけではなくゴリ押しでも通ってしまいます。この件に関してはご迷惑をおかけしました。

Problem F

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089
凸多角形を、原点を通る直線で2等分せよ。

方針

凸多角形(ケーキ)を上から見たときの面積をDとします。また、点Cの座標を(1,0)とし、原点Oと∠AOC=fとなる点Aを通る直線でケーキを切ったとき、直線の左側に残る凸多角形の面積をA(f)とします。直線の左側という表現については補足を参照してください。B(f)=D/2-A(f)とすると、常に B(f) * B(f+π) <= 0 です。なぜなら角度f+πを持つ直線でケーキを切った場合 A(f+π) は、角度fを持った直線で凸多角形を切った時に右側に残る凸多角形の面積と等しいからです。つまり A(f+π) = D - A(f) より B(f+π) = D/2-(D-A(f)) で、 B(f) * B(f+π) = (D/2-A(f)) * (D/2-(D-A(f)) = (D/2-A(f)) * (A(f)-D/2) = -(A(f)-D/2)2。 A(f)-D/2 は実数であることから B(f)*B(f+π) <= 0 とわかります。したがってfに関する関数Aと閉区間[f,f+π]について二分法を適用して条件を満たす直線を求めることができます。二分法についてはhttp://next1.cc.it-hiroshima.ac.jp/MULTIMEDIA/numeanal1/node6.htmlを参照してください。

計算量は反復数を200回程度、凸多角形をきるのにn2 (nでも可能です)、テストケースの数が1000なので、200 * 20 * 20 * 1000 = 80,000,000となります。これは8秒なら十分に間に合う量です。

解答例
const double eps = 1e-11;
double Af(const vector<point> &v, double f){
  vector<point> left;
  convexCut(v,line(point(0,0),point(20*cos(f),20*sin(f))),left);
  return areaOfPolygon(v)/2. - areaOfPolygon(left);
}

int main()
{
  int N;
  while(1){
    scanf("%d", &N);
    if( N == 0 ) break;
    vector<point> K;
    point res;
    double hi = pi;
    double low = 0;
    // int cnt = 0;
    double A_hi, A_low, A_m;

    for(int i = 0; i < N; ++i){
      int x,y;
      scanf("%d%d", &x, &y);
      K.push_back( point(x,y));
    }

    while(1){
      double m = (hi+low)/2.;
      
      A_hi = Af(K,hi);
      A_low = Af(K,low);
      A_m = Af(K,m);
      
      if( abs(A_m) <= eps ){
        res = point(20*cos(m),20*sin(m));
        break;
      }
      
      if( A_hi * A_m > 0 ) hi = m;
      else low = m;
    }
    printf("%.15lf %.15lf\n", res.real(), res.imag());
  }
  return 0;
}

convexCut関数は凸多角形(1番目の引数)をある直線(2番目の引数)で切り、その左側の凸多角形を3番目の引数に格納します。コードはすべて載せると少し長くなるので割愛します。
areaOfPolygon関数は凸多角形の面積を返す関数です。幾何ライブラリについてはたとえばhttp://www.prefield.com/algorithm/index.htmlを参照してください。
ここでいう直線の左側とは、直線が通る異なる2点A,Bになんらかの順序(たとえば座標)をつけたとき、三角形ABCの符号付き面積が負になるような点Cの集合です。右側とはABCの符号付き面積が正になるような点Cの集合です。直線をπ回転させることで左側と右側が入れ替わるような感じになります。

補足

この問題は他にひとつ解法があります。それは凸多角形をその頂点と原点を結ぶ直線で細かく分割し、三角形の集合にしてから原点をはさむような(対頂角が存在する)2つの三角形について、直線が通る凸多角形の辺上の点をベクトルを用いて解く方法です。