Hatena::Grouptopcoder

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

 | 

2013-07-06

京都大学プログラミングコンテスト2013 18:13 京都大学プログラミングコンテスト2013 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 京都大学プログラミングコンテスト2013 - nodchipのTopCoder日記 京都大学プログラミングコンテスト2013 - nodchipのTopCoder日記 のブックマークコメント

A - 旧総合研究7号館

  • 京都大学ネタ?
  • やるだけ
  • AC
int main() {
	std::ios::sync_with_stdio(false);

  int N, Q;
  cin >> N >> Q;
  string answer = "kogakubu10gokan";
  REP(n, N) {
    int year;
    string name;
    cin >> year >> name;
    if (year <= Q) {
      answer = name;
    }
  }
  cout << answer << endl;
}

B - ライオン

  • 全探索
  • ・・・のはずなのになぜかWA
  • よく分からない
  • 再帰をfor文に展開してみる
  • まだWA
  • ・・・?
  • lとrが1-basedなの忘れてたorz
  • AC
int main() {
  std::ios::sync_with_stdio(false);

  int N, X, M;
  int L[16], R[16], S[16];
  cin >> N >> X >> M;
  REP(m, M) {
    cin >> L[m] >> R[m] >> S[m];
    --L[m];
    --R[m];
  }

  int lions[16];
  int answer[16];
  int bestSum = -1;
  for (lions[0] = 0; lions[0] <= X; ++lions[0]) {
    for (lions[1] = 0; lions[1] <= X; ++lions[1]) {
      for (lions[2] = 0; lions[2] <= X; ++lions[2]) {
        for (lions[3] = 0; lions[3] <= X; ++lions[3]) {
          for (lions[4] = 0; lions[4] <= X; ++lions[4]) {
            for (lions[5] = 0; lions[5] <= X; ++lions[5]) {
              bool ok = true;
              for (int m = 0; ok && m < M; ++m) {
                int sum = accumulate(lions + L[m], lions + R[m] + 1, 0);
                ok = (S[m] == sum);
              }

              if (!ok) {
                continue;
              }

              int sum = accumulate(lions, lions + N, 0);
              if (bestSum < sum) {
                bestSum = sum;
                copy(lions, lions + N, answer);
              }
            }
          }
        }
      }
    }
  }

  if (bestSum == -1) {
    cout << -1 << endl;
  } else {
    REP(n, N) {
      if (n) {
        cout << " ";
      }
      cout << answer[n];
    }
    cout << endl;
  }
}

C - チョコレート

  • 見た感じ上の行から順にやれば良いようにみえる
  • 各行では左右の端からしか食べられないのと、最後に食べるやつが決まっていれば食べる順番は答えに影響しないので、最後に食べるやつを全探索
  • AC
int solve(const vector<int>& row) {
  int bestSum = 0;
  int N = row.size();
  REP(middle, N) {
    vector<int> temp = row;
    int sum = 0;
    for (int i = 0; i < middle; ++i) {
      sum += temp[i];
      if (i + 1 < N) {
        temp[i + 1] ^= 1;
      }
    }
    for (int i = N - 1; i >= middle; --i) {
      sum += temp[i];
      if (i - 1 >= 0) {
        temp[i - 1] ^= 1;
      }
    }

    MAX_UPDATE(bestSum, sum);
  }
  return bestSum;
}

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

  int M, N;
  cin >> M >> N;
  int answer = 0;
  REP(m, M) {
    vector<int> row;
    REP(n, N) {
      int a;
      cin >> a;
      if (m != 0) {
        a ^= 1;
      }
      row.push_back(a);
    }
    answer += solve(row);
  }
  cout << answer << endl;
}

D - カーペット

  • スタック使って線形な気がする
  • aをスタックに詰んでいって・・・
  • 前より小さいのが出てきたらスタック取り出していって・・・
  • 等号の当たりは適当に処理
  • AC
int main() {
	std::ios::sync_with_stdio(false);

  int N;
  cin >> N;
  stack<int> stk;
  stk.push(-1);
  int answer = 0;
  REP(n, N) {
    int a;
    cin >> a;
    while (stk.top() > a) {
      ++answer;
      stk.pop();
    }
    while (stk.top() == a) {
      stk.pop();
    }
    stk.push(a);
  }
  answer += stk.size() - 1;
  cout << answer << endl;
}

E - すごろく

  • KUPCおなじみのインタラクション問題キタ
  • ゴールになるべく近づくような動き方をしたいので、ゴールからスタートに向かって幅優先探索をして、理想的にあと何回で上がれるかをメモしておく
  • あとはゴールに近づけるような都合の良い面が来るのを待って移動させる
  • AC
int main() {
	std::ios::sync_with_stdio(false);

  int M, a[6], s, g, N[512];
  cin >> M >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> s >> g;
  --s;
  --g;
  REP(m, M) {
    cin >> N[m];
  }

  int rank[512];
  fill_n(rank, 512, INT_MAX);
  rank[g] = 0;
  deque<int> q;
  q.push_back(g);
  while (!q.empty()) {
    int now = q.front();
    q.pop_front();

    REP(next, M) {
      if (next + N[next] != now) {
        continue;
      }
      REP(surface, 6) {
        for (int leftRight = -1; leftRight <= 1; leftRight += 2) {
          int nextNext = next + a[surface] * leftRight;
          if (nextNext < 0 || M <= nextNext) {
            continue;
          }
          if (rank[nextNext] != INT_MAX) {
            continue;
          }
          rank[nextNext] = rank[now] + 1;
          q.push_back(nextNext);
        }
      }
    }
  }

  assert(rank[s] != INT_MAX);

  int now = s;
  while (now != g) {
    int surface;
    cin >> surface;
    --surface;
    int bestLeftRight = 0;
    int bestRank = rank[now];
    int bestNow = now;

    for (int leftRight = -1; leftRight <= 1; leftRight += 2) {
      int next = now + a[surface] * leftRight;
      if (next < 0 || M <= next) {
        continue;
      }
      next = next + N[next];
      if (next < 0 || M <= next) {
        continue;
      }
      if (bestRank < rank[next]) {
        continue;
      }
      bestRank = rank[next];
      bestNow = next;
      bestLeftRight = leftRight;
    }

    cout << bestLeftRight << endl << flush;
    now = bestNow;
  }
}

F - 7歳教

  • 満点はダイクストラ頑張る計に見えるけどよく分からない
  • 部分点は数直線上の区間併合やるだけ
  • AC 50
int main() {
	std::ios::sync_with_stdio(false);

  int n, s;
  cin >> n >> s;
  vector<pair<int, int> > events;
  REP(i, n) {
    int l, r;
    cin >> l >> r;
    events.push_back(MP(l, 1));
    events.push_back(MP(r, -1));
  }

  sort(ALL(events));

  int answer = 0;
  int counter = 0;
  int last = 0;
  REP(i, events.size()) {
    if (events[i].second == 1) {
      if (++counter == 1) {
        last = events[i].first;
      }
    } else {
      if (--counter == 0) {
        answer += events[i].first - last;
      }
    }
  }

  cout << answer << endl;
}

G - 自由研究

int main() {
	std::ios::sync_with_stdio(false);
 
  int N = 40;
  cout << N << endl;
  REP(i, N) {
    REP(j, N) {
      if (i == j) {
        cout << 'N';
      } else if (i == 0 || j == 0) {
        cout << 'Y';
      } else {
        cout << 'N';
      }
    }
    cout << endl;
  }
}

H - N and K

  • 適当な全探索を出してみる
  • TLE
  • 手元で試したら確かにTLEだったorz

I - σ

  • よく分からない

J - タイル置き

  • 部分点は全探索でおk
  • 満点はよく分からない
  • AC 50
int H, W, N;
set<ll> answer;

ll calculateHash(char dp[8][8]) {
  ll h = 0;
  REP(y, H) REP(x, W) {
    h *= 31;
    h += dp[y][x];
  }
  return h;
}

void dfs(int n, int pos, char dp[8][8]) {
  if (n == N) {
    answer.insert(calculateHash(dp));
    return;
  }

  for (int p = pos; p < H * W; ++p) {
    int x0 = p % W;
    int y0 = p / W;
    if (dp[y0][x0] != '.') {
      continue;
    }

    if (x0 + 1 < W) {
      int x1 = x0 + 1;
      int y1 = y0;
      if (dp[y1][x1] == '.') {
        dp[y0][x0] = '-';
        dp[y1][x1] = '-';
        dfs(n + 1, pos + 1, dp);
        dp[y0][x0] = '.';
        dp[y1][x1] = '.';
      }
    }
    if (y0 + 1 < H) {
      int x1 = x0;
      int y1 = y0 + 1;
      if (dp[y1][x1] == '.') {
        dp[y0][x0] = '|';
        dp[y1][x1] = '|';
        dfs(n + 1, pos + 1, dp);
        dp[y0][x0] = '.';
        dp[y1][x1] = '.';
      }
    }
  }
}

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

  cin >> H >> W >> N;
  char dp[8][8];
  memset(dp, '.', sizeof(dp));
  dfs(0, 0, dp);
  cout << answer.size() << endl;
}

K - encode/decode

  • 部分点はABとCBを組み合わせるだけなので簡単
  • 満点はよく分からない
  • AC 50
int main() {
	std::ios::sync_with_stdio(false);

  string command, S;
  cin >> command;
  int N;
  cin >> N >> S;
  if (command == "encode") {
    REP(i, S.size()) {
      if (S[i] == '0') {
        cout << "AB";
      } else {
        cout << "CB";
      }
    }
    cout << endl;

  } else {
    REP(i, S.size() / 2) {
      if (S[i * 2] == 'A') {
        cout << "0";
      } else {
        cout << "1";
      }
    }
    cout << endl;
  }
}
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20130706
 |