トップ > PKU > 今日解いた問題(PKU1915, 1917, 1941, 2312)

今日解いた問題(PKU1915, 1917, 1941, 2312)

PKU C++

久し振りにPKU JudgeOnlineの問題をC++で解いてみた．

今日解いたのは以下の比較的簡単と思われる4題．

ソースは以下にありマス．ただ，如何に素早く書き上げるかに重点を置いたソースなので，実用的なプログラムを作る上での参考にはならないと思う．

Problem 1915 - Knight Moves

http://acm.pku.edu.cn/JudgeOnline/problem?id=1915

チェスのナイトをある位置からある位置まで移動させる時の最短手数を求める問題．計算量の見積もりを誤ったのか，最初に適当に幅優先で書いたコードがTLE(Time Limit Exceeded)だった．仕方がないので枝刈りのコードをいろいろ追加していたらカオスなことに…．一応解けたけどソースコードは見るに堪えないので割愛．

問題を読み始めてからsubmitまでにかかった時間は60分程度．2ミス．

Problem 1917 - Automatic Poetry

http://acm.pku.edu.cn/JudgeOnline/problem?id=1917

単に文字列をほげほげするだけ．問題の指定通りに実装して終わり．文字列を区切る処理については，本当はistringstreamを使ってdelimiterを指定して分解するようにした方が良かったかも．

15分程度．

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char const* argv[]) {
  int n;
  cin >> n;
  string dummy;
  getline(cin, dummy);
  while (n--) {
    string l1, l2; 
    getline(cin, l1);
    getline(cin, l2);

    string l, s2, s3, s4, s5; 
    int m = 0;
    int pos = 0;
    for (int i = 0; i < l1.size(); i++) {
      if (m == 0 && l1[i] == '<') {
        l = l1.substr(0, i); 
        pos = i + 1;
      }   
      else if (m == 0 && l1[i] == '>') {
        l += l1.substr(pos, i - pos);
        s2 = l1.substr(pos, i - pos);
        m = 1;
        pos = i + 1;
      }   
      else if (m == 1 && l1[i] == '<') {
        l += l1.substr(pos, i - pos);
        s3 = l1.substr(pos, i - pos);
        pos = i + 1;
      }   
      else if (m == 1 && l1[i] == '>') {
        l += l1.substr(pos, i - pos);
        s4 = l1.substr(pos, i - pos);
        if (i != l1.size() - 1) {
          l += l1.substr(i+1);
          s5 = l1.substr(i+1);
        } else {
          s5 = ""; 
        }   
      }   
    }   

    cout << l << endl;
    cout << l2.substr(0, l2.size()-3) << s4 << s3 << s2 << s5 << endl;
  }
  return 0;
}

Problem 1941 - The Sierpinski Fractal

http://acm.pku.edu.cn/JudgeOnline/problem?id=1941

フラクタル図形？っぽいのを描画する問題．これも普通に実装して終わり．

23分程度．

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char const* argv[]) {
  int n;
  string tri[11][1024];
  tri[1][0] = " /\\";
  tri[1][1] = "/__\\";

  int h[11] = {0};
  h[1] = 2;
  for (int i = 2; i <= 10; i++) {
    int w = h[i-1];

    for (int j = 0; j < w; j++) {
      for (int k = 0; k < w; k++) {
        tri[i][j] += " ";
      }

      tri[i][j] += tri[i-1][j];
    }

    for (int j = 0; j < w; j++) {
      tri[i][j+w] += tri[i-1][j];

      for (int k = 0; k < w - j - 1; k++) {
        tri[i][j+w] += " ";
      }

      tri[i][j+w] += tri[i-1][j];
    }

    h[i] = h[i-1] * 2;
  }

  while (cin >> n && n) {
    for (int i = 0; i < h[n]; i++) {
      cout << tri[n][i] << endl;
    }
    cout << endl;
  }
  return 0;
}

Problem 2312 - Battle City

http://acm.pku.edu.cn/JudgeOnline/problem?id=2312

フィールド上の障害物を避けたり壊したりしながら目的地まで移動するのに必要な最小ターン数を求める．フィールド上の位置とステップ数(ターン数)を保持する構造体を用意し，setをpriority_queueのように使って幅優先探索．本当はちゃんとpriority_queueを使った方が速くなるらしい．INT_MAXを使っているのにclimitsをincludeし忘れて一度だけコンパイルエラーに…．

28分程度．1ミス．

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <climits>
using namespace std;

struct state {
  int step;
  int x, y;
  state(int step, int x, int y) : step(step), x(x), y(y) {}
  bool operator <(const state& rhs) const {
    if (step != rhs.step) { return step < rhs.step; }
    if (x != rhs.x) { return x < rhs.x; }
    else return y < rhs.y;
  }
};

int main(int argc, char const* argv[]) {
  int m, n;
  while (cin >> m >> n && (m || n)) {
    string field[300];
    int x0, y0, x1, y1;

    for (int i = 0; i < m; i++) {
      cin >> field[i];
      for (int j = 0; j < n; j++) {
        if (field[i][j] == 'Y') {
          x0 = i;
          y0 = j;
        }
        else if (field[i][j] == 'T') {
          x1 = i;
          y1 = j;
        }
      }
    }

    set<state> que;
    int table[300][300];
    fill(&table[0][0], &table[299][299]+1, INT_MAX);
    que.insert(state(0, x0, y0));
    table[x0][y0] = 0;

    bool flag = true;
    while (!que.empty()) {
      state s = *(que.begin());
      que.erase(que.begin());
      int x = s.x, y = s.y;

      if (x == x1 && y == y1) {
        cout << s.step << endl;
        flag = false;
        break;
      }

      int dx[] = {-1, 0, 1, 0};
      int dy[] = {0, -1, 0, 1};
      for (int i = 0; i < 4; i++) {
        int x2 = x + dx[i];
        int y2 = y + dy[i];

        if (x2 < 0 || x2 > m-1) { continue; }
        if (y2 < 0 || y2 > n-1) { continue; }

        if ((field[x2][y2] == 'E' || field[x2][y2] == 'T') && s.step + 1 < table[x2][y2]) {
          que.insert(state(s.step+1, x2, y2));
          table[x2][y2] = s.step + 1;
        }
        else if (field[x2][y2] == 'B' && s.step + 2 < table[x2][y2]) {
          que.insert(state(s.step+2, x2, y2));
          table[x2][y2] = s.step + 2;
        }
      }
    }

    if (flag) {
      cout << -1 << endl;
    }
  }
  return 0;
}

以上

2時間強で簡単な問題を4問解けたので，久し振りにやった割にはまあまあの出来か．