Hatena::Grouptopcoder

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

 | 

2012-12-01

TopCoder Single Round Match 562 Div 1 14:32  TopCoder Single Round Match 562 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク -  TopCoder Single Round Match 562 Div 1 - nodchipのTopCoder日記  TopCoder Single Round Match 562 Div 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 CheckerFreeness

  • T<=1,000,000,000なので周期性を見つけてあとで掛け合わせるに違いない
  • とりあえず書いてみる
  • なんか答えが合わない
  • 既に色が塗られている場合は"."で上書きしないのか・・・
  • 書き直し
  • ・・・
  • まだ合わない
  • "."で上書きしてたorz
  • Passed System Test
class PastingPaintingDivOne {
public:
  vector<long long> countColors(vector <string> clipboard, int T) {
    static char board[256][256];
    memset(board, '.', sizeof(board));
    int Y = clipboard.size();
    int X = clipboard[0].size();
    for (int loop = 0; loop < 100 && T > 0; ++loop, --T) {
      REP(y, Y) {
        REP(x, X) {
          if (clipboard[y][x] == '.') {
            continue;
          }
          board[y + loop][x + loop] = clipboard[y][x];
        }
      }
    }

    map<char, int> dic;
    dic['R'] = 0;
    dic['G'] = 1;
    dic['B'] = 2;
    dic['.'] = 3;
    vector<long long> result(4);

    for (int y = 0; y < 150; ++y) {
      for (int x = 0; x < 150; ++x) {
        ++result[dic[board[y][x]]];
      }
    }

    if (T) {
      vector<ll> repeated(4);
      for (int y = 0; y < Y; ++y) {
        ++repeated[dic[board[y + 99][0 + 99]]];
      }
      for (int x = 1; x < X; ++x) {
        ++repeated[dic[board[0 + 99][x + 99]]];
      }
      REP(i, 4){
        result[i] += repeated[i] * T;
      }
    }


    result.pop_back();

    return result;
  }
};

Middle 500 CheckerFreeness

  • N <= 50だから4重ループの全探索でいいよね? (<=すでに違う!)
  • 凸包書いて
  • できた
  • ・・・
  • サンプルでTLEしてる
  • 定数倍高速化してみる
  • doubleをlong longに変更
  • vectorを配列に変更
  • 凸包の判定で枝刈りを入れる
  • どうだろう・・・
  • Failed System Test
  • そもそもN<=222な上にWrongAnswerだったというorz
  • writerのir5氏によると、黒の凸包と白の凸包が交わらなければYESだそうです
  • 暇な時に考えてみます

System Test

oxx 146.61 202位 ratedだったら即死でした

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