SRM 2回目

o x x 173.96pt でレーティングが1116 -> 1041となった。相変わらずひどい。

Div2 Easy: Archery

アーチェリーの得点の期待値を計算する問題。

class Archery {
public:
  double expectedPoints(int N, vector <int> ringPoints) {
    double prob = 0;
    for (int i = 0; i <= N; ++i) {
      prob += ringPoints[i] * ((i+1)*(i+1) - i*i);
    }
    return prob / ((N+1)*(N+1));
  }
};

(includeしてる行がやたらいっぱいあってうっとうしいのでincludeの行は省いた)

Div2 Medium: AgeEncoding

0と1だけからなる文字列candlesLineが与えられる。この文字列をb進数と見たときcandlesLineがageと等しくなるようなbを求めよ。もし、そのようなbが存在しないのなら-1を、複数存在するのなら-2を出力せよ。という問題。

age=1, candlesLine="111111111111111111111111" のような場合は-1を出力するのが正解だけど0を出力してて通らなかった。

以下、本番後に書いたコード。

class AgeEncoding {
public:
  double calc(string candlesLine, double b) {
    double value = 0;
    for (int i = 0; i < candlesLine.size(); ++i) {
      value += (candlesLine[i] - '0') * pow(b, (double)(candlesLine.size() - i - 1));
    }
    return value;
  }

  double getRadix(int age, string candlesLine) {
    for (int i = 0; i < candlesLine.size()-1; ++i)
      if (candlesLine[i] == '1')
        goto ok;
    if (candlesLine[candlesLine.size()-1] == '1' && age == 1)
      return -2;
    else
      return -1;

ok:
    double lo = 0, hi = 101;
    for (int k = 0; fabs(hi - lo) > 1e-10 && k < 1000; ++k) {
      double mid = (lo + hi) / 2;
      double value = calc(candlesLine, mid);
      if (value < age) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    return lo <= 100 && lo >= 1e-9 ? lo : -1;
  }
};

Div2 Hard: SteeplechaseTrack

有向グラフが与えられるので、頂点数がN以下のウォークのうち最大の長さをもつウォークの長さを答えよ。という問題。(正確にはちょっと違うけど)

Bellman Ford法のような動的計画法で解こうとしてたけど時間が足りなかった。

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)

const int INF = 100000;

class SteeplechaseTrack {
public:
  int maxComplexity(vector <string> fences, vector <string> tracks, int N) {
    REP(i, tracks.size()) REP(j, tracks[i].size()) tracks[i][j] -= '0';
    REP(i, fences.size()) REP(j, fences[i].size()) fences[i][j] -= '0';

    int n = fences.size();
    vector<vector<int> > dp(N, vector<int>(n, -INF));
    REP(i, n)
      if (fences[i][1] != 0)
        dp[0][i] = fences[i][0] + fences[i][1];
    FOR(k, 1, N) REP(i, n) REP(j, n)
      if (tracks[i][j] != 0)
        dp[k][j] = max(dp[k][j], dp[k-1][i] + fences[j][0] + tracks[i][j]);

    int result = -INF;
    REP(k, N) REP(i, n)
      if (fences[i][2] != 0)
        result = max(result, dp[k][i] + fences[i][2]);
    return result < 0 ? -1 : result;
  }
};