初めてSRMに参加した

SRM

初めてSRMに参加しました。結果は o x x で 230.12pt 510位 という残念なものでした。次回に向けて今回の問題について書いておきます。(ソースコードは本番後に清書したもの)

Div2 Easy: TrappingRabbit

一番近い罠までのマンハッタン距離を求める問題。普通に求めて終了。この問題はできた。

#include <vector>
#include <algorithm>
using namespace std;

class TrappingRabbit {
public:
  int findMinimumTime(vector<int> trapX, vector<int> trapY) {
    int result = 100000;
    for (int i = 0; i < trapX.size(); ++i)
      result = min(result, abs(trapX[i] - 1) + abs(trapY[i] - 1));
    return result;
  }
};

Div2 Medium: ColoringRectangle

長方形が一つと、赤と青の円盤が何枚か与えられるので、ある条件を満たしながら、長方形全体を円盤で覆うのに必要な円盤の最低枚数を求めよという問題。

条件から円盤は半径が大きい順に使えばいいことが分かり、さらに条件から赤と青を交互に使わないといけないので、結局、最初に赤い円盤を使う場合と青い円盤を使う場合の2通りしかないことが分かる。よって両方の場合について計算してminをとればいい。

本番では条件を一部誤解していて撃墜されてしまった。

#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

const double eps = 1e-5;

class ColoringRectangle {
public:
  int attempt(int width, int height, vector<int>& disk1, vector<int>& disk2) {
    vector<int> disk[2] = { disk1, disk2 };
    double dist = 0;
    for (int i = 0; ; ++i) {
      int j = i >> 1;
      int k = i & 1;
      if (j >= disk[k].size())
        break;
      dist += sqrt(disk[k][j]*disk[k][j] - height*height);
      if (dist >= width - eps)
        return i+1;
    }
    return -1;
  }

  int chooseDisks(int width, int height, vector<int> red, vector<int> blue) {
    sort(red.begin(), red.end(), greater<int>());
    sort(blue.begin(), blue.end(), greater<int>());
    return (int)min((unsigned)attempt(width, height, red, blue),
                    (unsigned)attempt(width, height, blue, red));
  }
};

disk[k][j] < height の場合の処理を書いてないけど、この場合は sqrt(disk[k][j]*disk[k][j] - height*height) がNaNになり、NaNと何かを比較すると必ずfalseになるので、特に処理を書かなくても上手くいく。

Div2 Hard: NameInput

予測文字列と名前が与えられるので、予測文字列を使って名前を入力するのに何ステップいるかという問題。

n = name.size(), m = predictionSequence.size() とすると、インプットをn*mのサイズの地図とみなして幅優先探索すれば、O(nm)で最短経路が求まる。

本番では問題の規模を誤解してて(またかい)、O(nm^2)のDPで解いててTLE.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

class NameInput {
public:
  int dist[2501][2500];

  int countUpDownKeyPresses(vector<string> predictionSequence, vector<string> names) {
    string pred;
    for (int i = 0; i < predictionSequence.size(); ++i)
      pred += predictionSequence[i];
    string name;
    for (int i = 0; i < names.size(); ++i)
      name += names[i];

    memset(dist, -1, sizeof(dist));

    queue<pair<int, int> > Q;
    Q.push(make_pair(0, 0));
    dist[0][0] = 0;

    while (!Q.empty()) {
      int n = Q.front().first;
      int p = Q.front().second;
      Q.pop();

      if (n < name.size() && name[n] == pred[p] && dist[n+1][p] == -1) {
        dist[n+1][p] = dist[n][p];
        Q.push(make_pair(n+1, p));
      }

      int up = (p - 1 + pred.size()) % pred.size();
      if (dist[n][up] == -1) {
        dist[n][up] = dist[n][p] + 1;
        Q.push(make_pair(n, up));
      }

      int down = (p + 1) % pred.size();
      if (dist[n][down] == -1) {
        dist[n][down] = dist[n][p] + 1;
        Q.push(make_pair(n, down));
      }
    }

    unsigned result = (unsigned)-1;
    for (int i = 0; i < pred.size(); ++i)
      result = min(result, (unsigned)dist[name.size()][i]);
    return (int)result;
  }
};


ついでにDiv1にも挑戦してみた。Div1のEasyはDiv2のMediumと同じ問題っぽいので省略。Hardは解き方分からなかった。

Div1 Medium: BuildingCities

二次元平面上の街の集合が与えられる。街と街はその間のユークリッド距離がmaxDirect以下の時にその二つの街をつなぐ道が存在する。ここで、街0から街n-1までの最短経路の長さをmaxTravel以下にするように新たな街をいくつか作りたい。最低いくつの街を作ればよいか求めよという問題。

新たに作る街の数kに対してk回のDijkstra法を行うことで解いた。

#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class BuildingCities {
public:
  double dp[3001][50];
  bool visited[3001][50];

  int euclid2(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return dx*dx + dy*dy;
  }

  double euclid(int x1, int y1, int x2, int y2) {
    return sqrt(euclid2(x1, y1, x2, y2));
  }

  int findMinimumCities(int maxDirect, int maxTravel, vector<int> cityX, vector<int> cityY) {
    int n = cityX.size();

    if (euclid2(cityX[0], cityY[0], cityX[n-1], cityY[n-1]) > maxTravel*maxTravel)
      return -1;

    for (int i = 0; i <= 3000; ++i) {
      fill(visited[i], visited[i] + n, false);
      fill(dp[i], dp[i] + n, 1e10);
    }

    priority_queue<pair<double, int> > Q[3001];
    Q[0].push(make_pair(0, 0));
    dp[0][0] = 0;

    for (int k = 0; ; ++k) {
      while (!Q[k].empty()) {
        double cost = -Q[k].top().first;
        int city = Q[k].top().second;
        Q[k].pop();

        if (visited[k][city])
          continue;
        visited[k][city] = true;

        for (int i = 0; i < n; ++i) {
          if (!visited[k][i]) {
            double dist = euclid(cityX[city], cityY[city], cityX[i], cityY[i]);
            int need = dist <= maxDirect ? 0 : (int)ceil(dist / maxDirect) - 1;
            double new_cost = cost + dist;
            if (k+need <= 3000 && new_cost < dp[k+need][i]) {
              dp[k+need][i] = new_cost;
              Q[k+need].push(make_pair(-new_cost, i));
            }
          }
        }
      }

      if (dp[k][n-1] <= maxTravel)
        return k;
    }
  }
};