はじめてDiv1 Med を解けた.
oo- 528.29pts 13th.
1514 -> 1688(+174).
Easy (250) InterleavingParenthesis
TopCoder Statistics - Problem Statement
問題概要
‘(’ と ‘)’ からなる文字列 が与えられる.
のそれぞれの文字は順番を変えずに, 好きなように組み合わせて文字列をつくる.
このうち valid なカッコ列の個数を で割ったあまりで求めよ.
解法
の 文字目以降かつ の 文字目以降の文字列で valid なカッコ列の個数
として, メモ化再帰.
遷移は, か を使うかのどちらか.
カッコがどれだけ開いているかの情報も必要だが, これは と が定まれば一意なので, これを状態に加える必要はないことがわかる.
.
ソース
解法も実装も問題概要がわかればはいだった.
典型っぽい.
#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int dp[2555][2555]; class InterleavingParenthesis { public: int rec(int a, int b, int c, string& latte, string& malta) { if(a == latte.size() && b == malta.size()) return(c == 0); if(~dp[a][b]) return(dp[a][b]); int ret = 0; if(a < latte.size()) { int add1 = latte[a] == '(' ? 1 : -1; if(c + add1 >= 0) (ret += rec(a + 1, b, c + add1, latte, malta)) %= mod; } if(b < malta.size()) { int add2 = malta[b] == '(' ? 1 : -1; if(c + add2 >= 0) (ret += rec(a, b + 1, c + add2, latte, malta)) %= mod; } return(dp[a][b] = ret); } int countWays(string s1, string s2) { memset(dp, -1, sizeof(dp)); return(rec(0, 0, 0, s1, s2)); } };
Med (500) CircleCity
TopCoder Statistics - Problem Statement
問題概要
個の建物が円環に並んでいて, は 番目の建物と時計回りに隣接する建物間の距離を表す.
個のテレポーターを好きな場所に設置でき, ワープ地点間では相互にワープできる.
を建物 と建物 を移動するときの最短距離とする. また, 街の直径を の最大値と定義する.
街の直径の最小値を求めよ.
解法
最大値の最小化なので二分探索したくなる.
街の直径を にするときの, テレポーターの最小個数
とすれば, 解の二分探索ができるのはそう.
ぐっと睨むと は, すべての建物を長さ の区間で覆うときの, 区間の最小個数と同じことがわかる.
それぞれの区間の中央, すなわち の地点にテレポーターを設置する. 別々の区間で覆われた つの建物を考えると, それぞれの建物からテレポーターの距離が 以下になっていることより, 建物間の距離が 以下になっていることがわかる.
区間の最小個数というのは 個の始点を決め打ちして, 前から見ていけばできるので解けてしまう(えぇ…
全体の計算量は なのでいえい.
ソース
#include <bits/stdc++.h> using namespace std; const int64 INF = 1LL << 55; int64 N, K, X[4444]; bool beet(int s, int v) { int64 tail = s; int64 ret = 0; while(tail < s + N) { int64 curr = X[tail] + v; while(tail < s + N && X[tail] <= curr) ++tail; ++ret; } return(ret <= K); } bool C(int v) { for(int i = 0; i < N; i++) { if(beet(i, v)) return(true); } return (false); } class CircleCity { public: int findMin(vector<int> dist, int k) { N = dist.size(); K = k; X[0] = 0; int64 L = 0; for(int i = 0; i < dist.size(); i++) { L += dist[i]; } X[N] = L; for(int i = 1; i < dist.size(); i++) { X[i] = dist[i - 1]; X[i] += X[i - 1]; X[i + N] = X[i] + L; } int low = -1, high = L; while(high - low > 1) { int mid = (low + high) >> 1; if(C(mid)) high = mid; else low = mid; } return (high); } };