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; } };