天下一プログラマーコンテスト 2012 本戦

Algorithm Competition

9月15日に KLab オフィスで行われた天下一プログラマーコンテスト 2012に参加しました。

まとめ

3位でした。やったー。

詳細

A

A問題なのでやるだけに違いない。そこそこの早さでAC。

B

B問題なので簡単に違いない、と思っていたらむずかった。

点の座標が不自然に小さいので自然に直線を全列挙した。直線に沿って累積和をとっていくとヨサゲだった。

ちょっと時間使ったが特にハマることなくAC。

C

B問題が結構頭使ったのでC問題は難しいに違いない、と思っていたら簡単だった。

単なるBFSで、連続する B の個数は 100 まで考えればいいという考察はいるけれどもわりと自明だった。

多少バグらせたりはしたが特にハマらずAC。

D

C問題が簡単だったのでD問題これもう(どんな問題が出るか)わかんねえな、と思っていたらほんとに見たことない問題が出た。おもしろかった。

どうみてもマラソン勢の wata さんとか瞬殺しそうだなあという感じで、逆にマラソンガチ苦手勢のぼくとかはどうしようもなさそうな感じだった。

しかし E が満点は激ムズそうで、部分点も頑張って実装したらボーナス点あげますぐらいの感じだったのでせっかくだから面白い問題を楽しんだほうがよいと思って E は無視して D に全力を尽くすことにした。

まず最初に N <= 18 の DP を書いて送ってみたりした。ここでバグらせて WA を積んだりしていて悲しかった。

DPで得られた厳密解を観察していると、(左下隅の点, 右下隅の点, 上真ん中の点) みたいな三角形がたくさん作られていたので、そういう三角形をたくさん作ることにした。四隅の点を O(N) で探してきて、 左下と右下を決め打ったときに三角形を最大にする3個目の点を普通に O(N) で求めるのを N/3 回繰り返すとちょうど O(N^2) でよさそうだったので書いた。

さすがにサンプル(格子状に並んでいるだけ)ではそこそこの解が得られるが、あんまり点がたくさんあるときにいい解が出せる自信がなかった(外側の点を無限に消費していくので最後のほうは小さい三角形ばっかりになりそう)。しかし送ってみたら通った。

E

読んで、実装を確実にやって確実に点を拾うならこっちで、100点を狙うなら D だなあと思った。

全体
  • A よい
  • B もっと早く解けてもよかった
  • C そこそこ
  • D 運
  • E さて

各問題だけ見るともう少し改善できそうだが、全体で見るとわりと良かった。WAはそこそこ出してしまったがそもそも最後に点が更新されたときの時間がペナルティなのであまり影響はなく、ドハマリして時間を無駄に消費することもあまりなかった。順番もA->B->C->Dと順調に解いていくことができ、しかもDを通したのが終了4分前ぐらいだったので全体を通して充実感があってチョー楽しかった。

戦略的には D, E が残った際に E を忘れて D に全力を傾けようという決断がよかった。どんなコンテストでも問題間を右往左往して解けるものが解けなくなってしまうとかありがちなので、うまい選択が出来たのは強かった。もちろんこれで選択する方を間違えてしまうと悲惨だが、しかしぶっちゃけ選択を間違えるのと右往左往するのとか大して変わんない気がするし、どの問題を解くべきか判断する力はとても重要だと思うので積極的に選択していくほうがよさそう。

ソース

A

はい

#include<cstdio>

typedef long long Int;

int main()
{
  Int X;
  scanf("%lld", &X);

  Int F[60];
  F[0] = 0; F[1] = 1;
  for(int i=2; i<60; ++i)
    F[i] = F[i-1] + F[i-2];

  int res = 0;
  while(X > 0) {
    int x = 0;
    while(F[x] <= X) x++;
    X -= F[x-1];
    res++;
  }

  printf("%d\n", res);
  return 0;
}
B

ちょっと実装頭わるい感じでよくない。実際のコンテスト中でも思いついたら即書き始めてアホなことするより、実装をある程度練ってから書いたほうが全体のコストは小さくできると思うので気をつけたい。

#include<cstdio>
#include<set>

using namespace std;

typedef long long Int;

int P[100][100];
const Int MO = 1000000007;

int gcd(int m, int n)
{
  return n ? gcd(n, m%n) : m;
}

int main()
{
  int N;
  scanf("%d", &N);

  for(int i=0; i<N; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    P[y][x]++;
  }

  Int sub = 0;
  for(int dx=1; dx<=99; ++dx) {
    for(int dy=-99; dy<=99; ++dy) {
      if(dy == 0) continue;
      if(gcd(dx, dy<0 ? -dy : dy) == 1) {
        Int C[100][100] = {}, R[100][100] = {};
        for(int y=dy>0 ? 99 : 0; ; ) {
          if(dy > 0 && y < 0) break;
          if(dy < 0 && y >= 100) break;
          for(int x=0; x<100; ++x) {
            C[y][x] = P[y][x];
            int ny = y+dy, nx = x+dx;
            if(0<=nx && nx<=99 && 0<=ny && ny<=99) {
              C[y][x] += C[ny][nx];
              R[ny][nx] = 1;
            }
          }
          if(dy > 0) y--;
          if(dy < 0) y++;
        }
        for(int y=0; y<100; ++y) {
          for(int x=0; x<100; ++x) {
            if(!R[y][x] && C[y][x] >= 3) {
              sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)/6LL*(N-C[y][x]) % MO;
              if(sub >= MO) sub -= MO;
              sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)*(C[y][x]-3)/24 % MO;
              if(sub >= MO) sub -= MO;
            }
          }
        }
      }
    }
  }
  for(int y=0; y<100; ++y) {
    Int s = 0;
    for(int x=0; x<100; ++x) s += P[y][x];
    if(s >= 3) {
      sub += s*(s-1)*(s-2)/6LL*(N-s) % MO;
      if(sub >= MO) sub -= MO;
      sub += s*(s-1)*(s-2)*(s-3)/24LL % MO;
      if(sub >= MO) sub -= MO;
    }
  }
  for(int x=0; x<100; ++x) {
    Int s = 0;
    for(int y=0; y<100; ++y) s += P[y][x];
    if(s >= 3) {
      sub += s*(s-1)*(s-2)/6LL*(N-s) % MO;
      if(sub >= MO) sub -= MO;
      sub += s*(s-1)*(s-2)*(s-3)/24LL % MO;
      if(sub >= MO) sub -= MO;
    }
  }

  Int all = (Int)N*(N-1)*(N-2)*(N-3)/24 % MO;
  all -= sub;
  if(all < 0) all += MO;
  printf("%lld\n", all);
  
  return 0;
}
C

WA はあったものの細かい条件のミスとかがなかったのは良かった

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

int N, A[32], B[32], C[32];
int dp[31][101][101][101];

struct st {
  int id, ehp, shp, cb;
  st(int a, int b, int c, int d)
    : id(a), ehp(b), shp(c), cb(d) {
    if(cb > 100) cb = 100;
  }
};

const int INF = 1001001001;

inline void checkmin(int& a, int b) { if(a>b) a=b; }

inline void check(queue<st>& q, st x, int f) {
  if(dp[x.id][x.ehp][x.shp][x.cb] > f) {
    dp[x.id][x.ehp][x.shp][x.cb] = f;
    q.push(x);
  }
}

int main()
{
  scanf("%d", &N);
  for(int i=0; i<N; ++i)
    scanf("%d%d%d", &A[i], &B[i], &C[i]);
  A[N] = 0;

  for(int i=0; i<=N; ++i) 
    for(int j=0; j<=100; ++j) 
      for(int k=0; k<=100; ++k)
        for(int x=0; x<=100; ++x)
          dp[i][j][k][x] = INF;

  dp[0][A[0]][100][0] = 0;
  queue<st> q;
  q.push(st(0, A[0], 100, 0));
  while(!q.empty()) {
    st s = q.front(); q.pop();

    if(s.id == N) {
      printf("%d\n", dp[s.id][s.ehp][s.shp][s.cb]);
      return 0;
    }

    int damaged = s.shp - B[s.id];
    if(damaged <= 0) continue;

    int f = dp[s.id][s.ehp][s.shp][s.cb] + 1;

    if(s.ehp <= 5) {
      check(q, st(s.id + 1, A[s.id + 1], damaged, 0), f);
    } else {
      check(q, st(s.id, min(A[s.id], s.ehp - 5 + C[s.id]), damaged, 0), f);
    }

    check(q, st(s.id, min(A[s.id], s.ehp + C[s.id]), min(100, damaged+50), 0), f);

    int k = s.cb + 1;
    if(s.ehp <= k) {
      check(q, st(s.id + 1, A[s.id + 1], damaged, s.cb + 1), f);
    } else {
      check(q, st(s.id, min(A[s.id], s.ehp - k + C[s.id]), damaged, s.cb + 1), f);
    }
  }
  
  puts("-1");
  return 0;
}
D

終了5分前ぐらいに超焦って書いてたのでひどい。

#include<cstdio>
#include<algorithm>
#include<cstdlib>

using namespace std;

typedef long long Int;

int x[3030], y[3030], oid[3030];
Int dp[1<<18];
int prev[1<<18], used[3030];

int N;

int search_left(int a, int b, Int& M)
{
  Int mx = -1;
  int mxc = -1;
  if(a == b) {
    M = -1;
    return -1;
  }
  for(int i=0; i<N; ++i) {
    if(a==i || b==i || used[i]) continue;
    Int x1 = x[a]-x[i], y1 = y[a]-y[i];
    Int x2 = x[b]-x[i], y2 = y[b]-y[i];
    Int A = x1*y2 - x2*y1;
    if(A < 0) A *= -1;
    if(mx < A) {
      mx = A;
      mxc = i;
    }
  }
  M = mx;
  return mxc;
}

int main()
{
  scanf("%d", &N);

  for(int i=0; i<N; ++i)
    scanf("%d%d", &x[i], &y[i]);

  if(N <= 18) {
    dp[0] = 0;

    Int area[18][18][18];
    for(int i=0; i<N; ++i) {
      for(int j=i+1; j<N; ++j) {
        for(int k=j+1; k<N; ++k) {
          Int x1 = x[j]-x[i], x2 = x[k]-x[i];
          Int y1 = y[j]-y[i], y2 = y[k]-y[i];
          area[i][j][k] = x1*y2 - x2*y1;
          if(area[i][j][k] < 0) area[i][j][k] *= -1;
        }
      }
    }
    for(int i=1; i<(1<<N); ++i) {
      int pc = 0;
      for(int j=0; j<N; ++j)
        if(i & (1<<j)) pc++;
      if(pc % 3 == 0) {
        int ps[18], k = 0;
        dp[i] = -1;

        for(int j=0; j<N; ++j)
          if(i & (1<<j))
            ps[k++] = j;

        for(int p=0; p<k; ++p) {
          for(int q=p+1; q<k; ++q) {
            for(int r=q+1; r<k; ++r) {
              int sel = (1<<ps[p])|(1<<ps[q])|(1<<ps[r]);
              Int A = area[ps[p]][ps[q]][ps[r]] + dp[i ^ sel];
              if(dp[i] < A) {
                dp[i] = A;
                prev[i] = sel;
              }
            }
          }
        }
      }
    }

    for(int i=(1<<N)-1, t=0; t<N/3; t++, i^=prev[i]) {
      for(int j=0, k=0; j<N; ++j)
        if(prev[i] & (1<<j))
          printf("%d%c", j, ++k == 3 ? '\n' : ' ');
    }
  } else {
    for(int i=0; i<N/3; ++i) {
      int tl, tr, bl, br;
      for(int j=0; j<N; ++j) {
        if(!used[j]) {
          tl = tr = bl = br = j;
          break;
        }
      }
      for(int j=0; j<N; ++j) {
        if(!used[j]) {
          if(y[tl] - x[tl] < y[j] - x[j]) tl = j;
          if(y[tr] + x[tr] < y[j] + x[j]) tr = j;
          if(-y[bl] - x[bl] < -y[j] - x[j]) bl = j;
          if(-y[br] + x[br] < -y[j] + x[j]) br = j;
        }
      }

      Int M[4] = {0};
      int C[4];
      C[0] = search_left(tl, tr, M[0]);
      C[1] = search_left(tr, br, M[1]);
      C[2] = search_left(br, bl, M[2]);
      C[3] = search_left(bl, tl, M[3]);

      Int mx = -1;
      int mxc = -1;
      for(int j=0; j<4; ++j) {
        if(mx < M[j]) {
          mx = M[j];
          mxc = j;
        }
      }

      if(mx >= 0) {
        if(mxc == 0) printf("%d %d %d\n", tl, tr, C[0]), used[tl] = used[tr] = used[C[0]] = 1;
        if(mxc == 1) printf("%d %d %d\n", br, tr, C[1]), used[br] = used[tr] = used[C[1]] = 1;
        if(mxc == 2) printf("%d %d %d\n", br, bl, C[2]), used[br] = used[bl] = used[C[2]] = 1;
        if(mxc == 3) printf("%d %d %d\n", tl, bl, C[3]), used[tl] = used[bl] = used[C[3]] = 1;
      } else {
        int found = 0;
        for(int j=0; j<N; ++j) {
          if(!used[j]) {
            printf("%d%c", j, found==2 ? '\n' : ' ');
            found++;
            used[j] = 1;
          }
        }
      }
    }
  }

  return 0;
}