Hatena::Grouptopcoder

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

 | 

2011-12-04

Codeforces Beta Round #96 (Div. 1) 10:52 Codeforces Beta Round #96 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #96 (Div. 1) - nodchipのTopCoder日記 Codeforces Beta Round #96 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

Problem A. Turing Tape

  • 問題を読み終えた瞬間、@kinaba先生の「CodeForcesはA,Bにきっちり面倒くさい問題を仕込んでくる」という発言を思い出す
  • さて、面倒くさい
  • 入力される整数をo\[i\]、出力される文字列をs\[i\]、ビットを逆順にする関数をrと置くと、o\[i\]=r(r(o\[i-1\])-s\[i\])が成り立つ
  • んじゃ、@nico_shindannin先生のおすすめ通り全数精査で行きますか
  • ということでループを書いておしまい。面倒くさいコードはなし。
  • Accepted
int rev(int in) {
  int out = 0;
  REP(i, 8) {
    if (in & (1 << i)) {
      out |= (1 << (7 - i));
    }
  }
  return out;
}

int main() {
  assert(rev(72) == 18);
  std::ios::sync_with_stdio(false);

  string in;
  getline(cin, in);

  REP(i, in.size()) {
    int current = in[i];
    int prev = i == 0 ? 0 : in[i - 1];

    REP(ch, 256) {
      if (current == rev((rev(prev) - ch + 256) % 256)) {
        cout << ch << endl;
        break;
      }
    }
  }
}

Problem B. Piet

  • これまた面倒くさいシミュレーション
  • そして英文が色々バグっとる
  • まず「CC」はロシア語の文章から推測すると「CP」かな。
    • 訂正きた
  • あと、「It the next pixel is black or outside of the program,」は「If the next pixel is black or outside of the program,」ということにしておく
  • 微妙に罠があるとしたら、次に進むタイルを毎回探索するとTLEするかもしれない点か
  • これはあらかじめメモっておく
  • あとは問題分をソースコードにコピペしつつガリガリ書くだけ
  • Accepted
enum {
  EAST,
  SOUTH,
  WEST,
  NORTH
};

const char* DIRECTION_STRINGS[] = {
  "EAST",
  "SOUTH",
  "WEST",
  "NORTH",
};

const int DR[] = {0, 1, 0, -1};
const int DC[] = {1, 0, -1, 0};

bool in(int r, int c, int R, int C) {
  return 0 <= r && r < R && 0 <= c && c < C;
}

int main() {
  std::ios::sync_with_stdio(false);

  int M, N;
  cin >> M >> N;
  vector<string> maze;
  REP(r, M) {
    string in;
    cin >> in;
    maze.push_back(in);
  }

  int R = maze.size();
  int C = maze[0].size();

  static char table[64][64];
  REP(r, R) {
    REP(c, C) {
      table[r][c] = maze[r][c];
    }
  }

  static pair<int, int> furthest[64][64][4];
  REP(startR, R) {
    REP(startC, C) {
      if (table[startR][startC] == '0') {
        continue;
      }

      REP(dir, 4) {
        pair<int, int> current = MP(startR, startC);
        for (;;) {
          pair<int, int> next = current;
          next.first += DR[dir];
          next.second += DC[dir];
          if (!in(next.first, next.second, R, C)) {
            break;
          }

          if (table[current.first][current.second] != table[next.first][next.second]) {
            break;
          }

          current = next;
        }

        furthest[startR][startC][dir] = current;
      }
    }
  }

  pair<int, int> bp;
  int dp = EAST;
  int cp = NORTH;
  REP(n, N) {
    //cerr << "(" << bp.first << "," << bp.second << ") dp:" << DIRECTION_STRINGS[dp] << " cp:" << DIRECTION_STRINGS[cp] << endl;

    // The interpreter finds the furthest edge of the current color block in the direction of the DP.
    pair<int, int> furthestDp = furthest[bp.first][bp.second][dp];

    // From all pixels that form this edge, the interpreter selects the furthest one in the direction of CP.
    pair<int, int> furthestCp = furthest[furthestDp.first][furthestDp.second][cp];

    // After this, BP attempts to move from this pixel into the next one in the direction of DP.
    // If the next pixel belongs to a colored block,
    pair<int, int> nextPixel = furthestCp;
    nextPixel.first += DR[dp];
    nextPixel.second += DC[dp];
    if (in(nextPixel.first, nextPixel.second, R, C) && table[nextPixel.first][nextPixel.second] != '0') {
      // this block becomes the current one, and two other parts of IP stay the same.
      bp = nextPixel;
      continue;
    }

    // It the next pixel is black or outside of the program, BP stays the same but two other parts of IP change.
    // If CP was pointing to the left,
    if (cp == (dp + 3) % 4) {
      // now it points to the right, and DP stays the same.
      cp = (dp + 1) % 4;
      continue;
    }

    // If CP was pointing to the right, now it points to the left, and DP is rotated 90 degrees clockwise.
    dp = (dp + 1) % 4;
    cp = (dp + 3) % 4;
  }

  cout << table[bp.first][bp.second] << endl;
}

Problem C. Logo Turtle

  • ロゴなつかしい
  • これ二次元座標上を動くんだよね? (<-違う!)
  • 距離を出力って言ってるけどマンハッタン距離かな (<-合っているけど違う!)
  • DPでやるならdp[コマンド番号][x座標][y座標][向き][変更回数]か (<-違う!)
  • とりあえずsetに突っ込んで書いてみる
  • ・・・
  • 書いてみた
  • 最悪ケースを投入してみる
  • ・・・
  • 13sec・・・!?
  • だめだこりゃ
  • DPで書きなおしてみる
  • ・・・
  • 4sec・・・
  • 枝刈りを入れてみる
  • 1sec・・・ (<-無駄な努力)
  • 出してみた
  • Wrong answer on pretest 4
  • ・・・
  • ほへ・・・?
  • ・・・
  • ・・・
  • 1次元座標だった・・・ (<-遅い!)
  • 書きなおしてみた
  • ・・・
  • Wrong answer on pretest 4
  • だめだこりゃorz

Problem D. Constants in the language of Shakespeare

  • 読んでいません

Problem E. Bits of merry old England

  • 読んでいません

Hack

  • やっていません

System Test

#Who=ABCDE
161nodchip1616470 00:151146 00:59-4

1840->1868。DPはやはり鬼門のようです。

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