玉
シンプルな深さ優先探索。全通り試してOK。
int tama[11];
bool solve(int i, int n) {
if (i == 10) {
int al=-1, bl=-1;
for (int j = 0; j < 10; j++) {
if ((1<<j)&n) {
if (al < tama[j])
al=tama[j];
else
return false;
} else {
if (bl < tama[j])
bl=tama[j];
else
return false;
}
}
return true;
}
bool a = solve(i+1, n|(1<<i));
bool b = solve(i+1, n);
return a || b;
}
int main() {
while (1) {
int N; cin >> N;
for(int i = 0; i < N; i++) {
for (int j = 0; j < 10; j++) {
cin >> tama[j];
}
if (solve(0, 0)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
break;
}
return 0;
}
SRM 659 Div1 ApplesAndOrangesEasy
ほぼ1ヶ月ぶりの更新か...。久しぶりすぎてTopCoderの提出法忘れていた...。
BITかなと一瞬思ったが、リンゴを1とおくと簡単にサブリストのリンゴの数を計算できるので、事前に合計を計算してから単純に左端、右端を引いたり足したりしていくことにした。
class ApplesAndOrangesEasy {
public:
int maximumApples(int N, int K, vector <int> info) {
int arr[2005] = {};
int k2 = K/2;
for (int i : info) {
arr[i-1]=1;
}
for (int i = 0; i < N; i++) {
if (arr[i]==1)continue;
arr[i]=1;
int left = max(0, i-K+1);
int right = min(N-1, i+K-1)-K+1;
int sum = 0;
for (int j = 0; j < K; j++) {
sum += arr[left+j];
}
bool f = true;
for (int j = left; j <= right; j++) {
if (sum > k2){
f=false;
break;
}
sum -= arr[j];
sum += arr[K+j];
}
if(!f)
arr[i]=0;
}
int cnt =0;
for (int i = 0; i < N; i++) {
if (arr[i])
cnt+=arr[i];
}
return cnt;
}
};
AOJ Lupin The 4th
Lupin The 4th | Aizu Online Judge
巡回セールスマン問題。経路復元が必要。 経路復元は、それ用に配列をもう一つ用意しておいて、最短の移動順序を記録しておく。
double dp[100000][20];
int pos[100000][20];
int n;
int kura[20], d[20], sen[20];
double solve(int S, int v, int weight) {
if (S == ((1 << n) - 1)) return dp[S][v] = 0;
if (dp[S][v] >= 0) return dp[S][v];
double res = 1000*1000*1000;
for (int i = 0; i < n; i++) {
if (!(S & (1 << i))) {
double td = abs(d[i]-d[v]);
double ts = 2000.0/(double)(70+weight);
double tres = solve(S | (1 << i), i, sen[i]*20 + weight) + td/ts;
if (res > tres) {
res = tres;
pos[S][v] = i;
}
}
}
return dp[S][v] = res;
}
int main() {
cin >> n;
for (int i = 0; i < 100000; i++) fill(dp[i], dp[i]+20, -1);
for (int i = 0; i < n; i++) {
cin >> kura[i] >> d[i] >> sen[i];
}
d[n] = 0;
solve(0, n, 0);
int S = 0, cur = n;
vector<int> r;
for (int i = 0; i < n; i++) {
int next = pos[S][cur];
r.push_back(next);
S = (S | (1 << next));
cur = next;
}
for (int i = 0; i < n-1; i++) cout << kura[r[i]] << ' ';
cout << kura[r[n-1]] << endl;
return 0;
}
Patisserie | Aizu Online Judge
Patisserie | Aizu Online Judge
巡回セールスマン問題。
dp[すでに並べたケーキの集合][最後に置いたケーキ]としてメモ化再帰で解く。
グラフはG[ケーキv][ケーキu]として、ケーキvの次にケーキuを置く時、どれほど長さが増えるかで事前に作っておく。
同じサイズのケーキじゃない限り、ちょっとめりこむのでその数値を事前に計算しておく（シンプルな算数でOK）。
ケーキを一つも置いてない状態->新たにケーキを置く状態もノードに加えておく。
入力ケースが特殊なのでC++での方法が分からずちょっと手間取った。
double dp[10000][15];
double d[15][15];
double r[13];
int n;
double solve(int S, int v) {
if (S == ((1<<n)-1)) {
return dp[S][v] = 0;
}
if (dp[S][v] >= 0) return dp[S][v];
double res = 1000*1000*1000;
for (int i = 0; i < n; i++) {
if (!((1 << i) & S)) {
double ds = d[v][i];
res = min(res, solve(S | (1 << i), i) + ds);
}
}
return dp[S][v] = res;
}
int main() {
while (1) {
string s;
getline(cin, s);
stringstream ss(s);
if (s == "") break;
double m; ss >> m;
n = 0;
for (int i = 0; i < 13; i++) {
ss >> r[i];
if (!r[i]) break;
n++;
}
for (int i = 0; i < 10000; i++)
for (int j = 0; j < 15; j++)
dp[i][j] = -1;
for (int i = 0; i < 15; i++)
for (int j = 0; j < 15; j++)
d[i][j] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (r[i] == r[j]) {
d[i][j] = r[i]*2;
d[j][i] = r[i]*2;
} else {
int a = abs(r[i] - r[j]);
int c = r[i] + r[j];
double b = sqrt(c*c-a*a);
d[i][j] = b + r[j] - r[i];
d[j][i] = b + r[i] - r[j];
}
}
}
for (int i = 0; i < n; i++) {
d[i][n] = 0;
d[n][i] = r[i]*2;
}
if (solve(0, n) <= m) {
cout << "OK" << endl;
} else {
cout << "NA" << endl;
}
}
return 0;
}
Russian Dolls
DP。最長増加部分列。
int main() {
while (1) {
vector< pair<int, int> > vp;
int dp[205];
int n; cin >> n; if (n == 0) break;
for (int i = 0; i < n; i++) {
int h, r; cin >> h >> r;
vp.push_back(pair<int, int>(h, r));
}
int m; cin >> m;
for (int i = 0; i < m; i++) {
int h, r; cin >> h >> r;
vp.push_back(pair<int, int>(h, r));
}
sort(vp.begin(), vp.end());
for (int i = 0; i < vp.size(); i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (vp[j].first < vp[i].first && vp[j].second < vp[i].second) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < vp.size(); i++) {
res = max(res, dp[i]);
}
cout << res << endl;
}
return 0;
}
At Boss's Expense
一発で書けた。素数とナップザック問題。
bool dp[35][1000005];
bool pt[1000005];
int main() {
memset(pt, 1, sizeof(pt));
pt[0] = 0; pt[1] = 0;
for (int i = 2; i * i < 1000005; i++) {
if (pt[i]) {
for (int j = i*2; j < 1000005; j+=i) {
pt[j] = 0;
}
}
}
while (1) {
int n, x; cin >> n >> x;
if (n == 0 && x == 0) break;
int v[35]; memset(v, 0, sizeof(v));
for (int i = 0; i < n; i++) cin >> v[i];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= x; j++) {
if (j - v[i] >= 0)
dp[i + 1][j] |= dp[i + 1][j - v[i]];
dp[i + 1][j] |= dp[i][j];
}
}
int res = -1;
for (int i = 2; i <= x; i++) {
if (dp[n][i] && pt[i]) {
res = max(res, i);
}
}
if (res != -1)
cout << res << endl;
else
cout << "NA" << endl;
}
return 0;
}
A Thief
int main() {
int cas = 1;
while (1) {
int N, W;
int v[1005], w[1005], dp[1005][1005];
cin >> W; if (!W) break;
cin >> N;
for (int i = 0; i < N; i++) {
char c;
cin >> v[i] >> c >> w[i];
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
int res = 0, resw = 1000*1000*1000*2;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= W; j++) {
if (j - w[i] >= 0) {
dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
} else {
dp[i + 1][j] = dp[i][j];
}
if (dp[i+1][j] == -1) continue;
if (dp[i + 1][j] > res) {
res = dp[i + 1][j];
resw = j;
} else if (dp[i + 1][j] == res) {
resw = min(resw, j);
}
}
}
cout << "Case " << cas << ":" << endl;
cout << res << endl;
cout << resw << endl;
cas++;
}
return 0;
}
