Hatena::Grouptopcoder

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

 | 

2014-08-23

天下一プログラマーコンテスト2014予選B 23:14 天下一プログラマーコンテスト2014予選B - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 天下一プログラマーコンテスト2014予選B - nodchipのTopCoder日記 天下一プログラマーコンテスト2014予選B - nodchipのTopCoder日記 のブックマークコメント

A - HAGIXILE

  • HAGIYAがちょうど1回出現するという一文を見落としそうになって、Javaに走ろうとした
  • AC
const string SRC = "HAGIYA";
const string DST = "HAGIXILE";

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

  string s;
  cin >> s;
  int i = s.find(SRC);
  cout << s.substr(0, i) << DST << s.substr(i + SRC.size()) << endl;
}

B - エターナルスタティックファイナル

  • 配るDP
int main() {
	std::ios::sync_with_stdio(false);

  int N;
  string S;
  cin >> N >> S;
  vector<string> T;
  REP(n, N) {
    string t;
    cin >> t;
    T.push_back(t);
  }

  int dp[1024] = { 0 };
  dp[0] = 1;
  REP(i, S.size()) {
    for (const auto& t : T) {
      if (S.substr(i, t.size()) == t) {
        dp[i + t.size()] += dp[i];
        dp[i + t.size()] %= 1000000007;
      }
    }
  }
  cout << dp[S.size()] << endl;
}

C - 天下一王国の歴史

  • 問題文を一目見てライフゲームのPターン先を出力する問題だと思って行列ライブラリをコピペしはじめる
  • 問題文を改めてみると全く違う問題だった
  • 満点解法は全くわからない
  • 55点解法は上2段を全探索して残りは一意に決めるというやり方でO(2^{2N}*N^2)かな?
  • 仕方ないのでこれで出す・・・
  • WA 55
bool check(int N, bool original[16][16], bool board[16][16]) {
  for (int y = 0; y < N; ++y) {
    for (int x = 0; x < N; ++x) {
      bool cell = false;
      if (x > 0) {
        cell ^= board[y][x - 1];
      }
      if (x + 1 < N) {
        cell ^= board[y][x + 1];
      }
      if (y > 0) {
        cell ^= board[y - 1][x];
      }
      if (y + 1 < N) {
        cell ^= board[y + 1][x];
      }

      if (original[y][x] != cell) {
        return false;
      }
    }
  }

  return true;
}

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

  int N;
  cin >> N;

  if (N == 1) {
    cout << "#" << endl;
    return 0;
  }

  if (N > 10) {
    assert(false);
    return 0;
  }

  bool original[16][16];
  REP(y, N) REP(x, N) {
    char ch;
    cin >> ch;
    original[y][x] = ch == '#';
  }

  for (int bits = 0; bits < (1 << (N * 2)); ++bits) {
    bool board[16][16] = { false };
    for (int y = 0; y < 2; ++y) {
      for (int x = 0; x < N; ++x) {
        board[y][x] = (bits & (1 << (y * N + x))) != 0;
      }
    }

    for (int y = 2; y < N; ++y) {
      for (int x = 0; x < N; ++x) {
        bool cell = false;
        if (x > 0) {
          cell ^= board[y - 1][x - 1];
        }
        if (x + 1 < N) {
          cell ^= board[y - 1][x + 1];
        }
        cell ^= board[y - 2][x];
        cell ^= original[y - 1][x];

        board[y][x] = cell;
      }
    }

    if (check(N, original, board)) {
      REP(y, N) {
        REP(x, N) {
          cout << (board[y][x] ? '#' : '.');
        }
        cout << endl;
      }
      break;
    }
  }
}

D - 天下一芸術

  • 昔似たような問題を見たことがある
  • あっちは濃度が無くて塗りつぶせるかだけだった気がする。
  • とりあえず各色について上下左右の端を求めて
  • 他の色と比較してどちらを先に塗るべきかで半順序関係使って
  • グラフ作ってトポロジカルソートして・・・
  • ・・・
  • DP・・・?
  • ・・・
  • DP嫌いなのでgreedyにやってみる
  • WA 35
  • うむむ・・・5個だけWA
  • なんか悔しいのでトポロジカルソート中にたどる辺の順番をシャッフルしてみる
  • WA 35
  • 3個だけWA
  • ・・・
  • 諦めて全探索する
  • WA 75
struct Area {
  int left, top, right, bottom;
};

bool dfs(const Graph &g, const vector<int>& order, int depth, const multiset<int>& A, int densities[32]) {
  if (order.size() == depth) {
    return true;
  }

  int current = order[depth];
  int lastA = -1;
  for (const auto& a : A) {
    if (a == lastA) {
      continue;
    }
    lastA = a;

    bool go = true;
    for (const auto& edge : g[current]) {
      assert(densities[edge.dst] != -1);
      if (a <= densities[edge.dst]) {
        go = false;
        break;
      }
    }

    if (!go) {
      continue;
    }

    densities[current] = a;
    multiset<int> nextA = A;
    nextA.erase(nextA.find(a));
    if (dfs(g, order, depth + 1, nextA, densities)) {
      return true;
    }
  }

  densities[current] = -1;

  return false;
}

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

  int N;
  cin >> N;
  multiset<int> A;
  REP(n, N) {
    int a;
    cin >> a;
    A.insert(a);
  }

  bool used[32] = { false };
  int H, W;
  cin >> H >> W;
  int B[256][256];
  REP(y, H) REP(x, W) {
    cin >> B[x][y];
    used[B[x][y]] = true;
  }

  Area initialArea = { INT_MAX, INT_MAX, INT_MIN, INT_MIN };
  vector<Area> areas(N, initialArea);
  REP(y, H) REP(x, W) {
    Area& area = areas[B[x][y]];
    MIN_UPDATE(area.left, x);
    MIN_UPDATE(area.top, y);
    MAX_UPDATE(area.right, x);
    MAX_UPDATE(area.bottom, y);
  }

  Graph graph(N), rev(N);
  REP(n, N) {
    if (!used[n]) {
      continue;
    }

    for (int y = areas[n].top; y <= areas[n].bottom; ++y) {
      for (int x = areas[n].left; x <= areas[n].right; ++x) {
        if (B[x][y] == n) {
          continue;
        }
        graph[n].push_back(Edge(n, B[x][y], 0));
        rev[B[x][y]].push_back(Edge(B[x][y], n, 0));
      }
    }
  }

  vector<int> order;
  if (!topologicalSort(graph, used, order)) {
    cout << 0 << endl;
    return 0;
  }

  int densities[32] = { -1 };
  if (dfs(rev, order, 0, A, densities)) {
    cout << 1 << endl;
  }
  else {
    cout << 0 << endl;
  }
}

E - カラオケランキング

  • 全く分かりませんでした

結果

順位ユーザ名HAGIXILEエターナルスタティックファイナル天下一王国の歴史天下一芸術カラオケランキング得点 / Total
36nodchip20 01:4260 06:5555 107:2975 (7) 113:48-210 (7) 148:48

練習不足がたたって残念な成績になってしまいました。これからはもう少し参加頻度を上げていきたいと思います。

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