Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2009-03-15

2009 TopCoder Open Algorithm Elimination Round 2 11:27 2009 TopCoder Open Algorithm Elimination Round 2 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 2009 TopCoder Open Algorithm Elimination Round 2 - nodchipのTopCoder日記 2009 TopCoder Open Algorithm Elimination Round 2 - nodchipのTopCoder日記 のブックマークコメント

2009 TopCoder Open Algorithm Elimination Round 2の参加記録です。

Easy 250 PlaneFractal

格子状でフラクタル図形を描いていく。s回展開を繰り返した後、指定した範囲の図形の内容を求めよ。

見た瞬間に面倒そうな問題だと感じました。

始めに全て展開できるかを考えてみたのですが、8^10^2≒1e18となりどう見ても無理です。本当に有難うございました。

次に必要な部分だけ展開していってはどうかと考えました。とりあえずこれで書き始めました。

この問題だけでえらい時間を食ってしまいました。

ソースは以下の通りです。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <fstream>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;

static bool prev[1024][1024];
static bool next[1024][1024];

class PlaneFractal {
public:
  vector <string> getPattern(int s, int N, int K, int r1, int r2, int c1, int c2) {
    ll power[16];
    power[0] = 1;
    for (int i = 1; i <= s; ++i){
      power[i] = power[i - 1] * N;
    }

    memset(prev, 0, sizeof(prev));
    prev[0][0] = true;

    for (int loop = 0; loop < s; ++loop){
      memset(next, 0, sizeof(next));
      const ll offsetR = r1 / power[s - loop];
      const ll offsetC = c1 / power[s - loop];
      r1 -= offsetR * power[s - loop];
      r2 -= offsetR * power[s - loop];
      c1 -= offsetC * power[s - loop];
      c2 -= offsetC * power[s - loop];

      for (int r = 0; r * power[s - loop] <= r2; ++r){
        for (int c = 0; c * power[s - loop] <= c2; ++c){
          if (prev[offsetR + r][offsetC + c]){
            //white;
            for (int rr = r * N; rr < (r + 1) * N; ++rr){
              for (int cc = c * N; cc < (c + 1) * N; ++cc){
                next[rr][cc] = true;
              }
            }
            for (int rr = r * N + N / 2 - K / 2; rr < r * N + N / 2 + (K + 1) / 2; ++rr){
              for (int cc = c * N + N / 2 - K / 2; cc < c * N + N / 2 + (K + 1) / 2; ++cc){
                next[rr][cc] = false;
              }
            }
          } else {
            //black;
          }
        }
      }

      memcpy(prev, next, sizeof(prev));
    }

    vector <string> result(r2 - r1 + 1, string(c2 - c1 + 1, ' '));
    for (int r = r1; r <= r2; ++r){
      for (int c = c1; c <= c2; ++c){
        result[r - r1][c - c1] = prev[r][c] ? '0' : '1';
      }
    }
    return result;
  }
}; 

Midium 600 ExtendableTriangles

面倒そうだったので問題文ごと忘れました。

Hard 900 ConnectingAirports

A国にN箇所、U国にM箇所の空港がある。それぞれの空港には容量がある。これらの空港の間に便を設けたい。条件として「便はA国の空港とU国の空港を1対1で結ぶ」「空港間には高々1つまでの便を結ぶ」「空港の許容量と完全に一致しなければならない」「複数のスケジュールが立てられる場合は辞書順で最も早いものを選ばなければならない」とする。

見た感じで二部マッチングなのは分かったのですが、辞書順のやり方がわかりませんでした。とりあえず普通の二部マッチングを書いてみたところ、ぜんぜん辞書順になりませんでした。点の順番をreverseしたりしても駄目。

最小費用流にして優先的に使用する枝を決め打ちしてやればどうだろうと考え、残り数分で書き換えを始め、残り7秒でsubmitしました。

撃墜フェーズ

250の解き方が他の人とまったく違っていたことにびっくりしました。この問題は数論の問題として解くとスマートに解けるようです。実装系の問題として解いていたのは自分だけでした。

900は撃墜祭りのようでしたが、自分にはまったくついていけませんでした。

結果

o x x 900は最大ケースのときにコストがdoubleで表現可能な範囲を下回ってしまい、辞書順で出なくなってしまうというバグがあったようです。

2241->2151 予定通り赤→黄陥落しました。

まとめ

600点という点数を見た瞬間にいやな予感がしていたのですが、見事に的中してしまいました。もう少しフローを勉強すべきなのだと思います。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20090315
 |