ABC034 D - 食塩水
やり直し
解説
平均を最大化する問題->二分探索
wiグラムの濃度pi%の食塩水をk個混ぜた時の濃度は、
これがp以上となる時は
を満たす。
変形すると、
濃度がp以上の食塩水を作れるかどうかは、
の値が大きい容器からK個選んで0以上となっていれば作れるとわかる。
pの値で二分探索すればOK。
今回pは実数なので、探索する区間が十分小さくなるようにforで回せばOK。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; // 平均最大化 int N, K; double w[1000], p[1000]; bool calc(double pp) { vector<double> v; FOR(i,0,N) { v.push_back((p[i] - pp) * w[i]); } sort(v.rbegin(), v.rend()); double m = 0; FOR(i,0,K) m += v[i]; return m >= 0; } int main() { cin >> N >> K; FOR(i,0,N) cin >> w[i] >> p[i]; double l = -1, r = 1000; FOR(i,0,100) { double m = (l + r) * 0.5; if(calc(m)) l = m; else r = m; } printf("%.10lf\n",l); return 0; }
平均最大化の問題だと気がつかなかった
ARC046 C - 掛け算
やり直し
解法
Bが109乗なので愚直にシミュレーションするとTLEになってしまう。aを昇順に並び替えつつ、何回かシミュレーションをすると a[0] * A >= a[N-1] となる時が来る。こうなったらN周期で同じ列が現れる状態になる。周期的になるまでは高々N*log(max(a))回シミュレーションすれば良い。
周期的になる状態ができたら(残りB'回とする)あとはi < B' % Nを満たすa[i]はB'/N+1回、i >= B' % Nを満たすa[i]はB'/N回、Aをかければ良いとわかる。
愚直にAを掛け算するとTLEする可能性があるので、高速累乗すればACできる。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const int mod = 1e9 + 7; int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, A, B; cin >> N >> A >> B; ll a[N]; FOR(i,0,N) cin >> a[i]; sort(a, a + N); if(A == 1) { FOR(i,0,N) cout << a[i] % mod << endl; return 0; } ll k = 0; while(B) { sort(a, a + N); if(a[0] * A >= a[N-1]) break; a[0] *= A; B--; } sort(a, a + N); // 周期的になる前に終わる if(B == 0) FOR(i,0,N) cout << a[i] % mod << endl; // 周期的になる else { FOR(i,0,N) a[i] %= mod; // B / N 回 A倍する FOR(i,B%N,N) { ll C = B / N; ll AA = A % mod; while(C) { if(C&1) a[i] = (a[i] * AA) % mod; AA = (AA * AA) % mod; C >>= 1; } } FOR(i,0,B%N) { ll C = B / N + 1; ll AA = A % mod; while(C) { if(C&1) a[i] = (a[i] * AA) % mod; AA = (AA * AA) % mod; C >>= 1; } } FOR(i,0,N) { cout << a[(i+B%N)%N] << endl; } } return 0; }
ARC038 B - マス目と駒
やり直し
解法
メモ化再帰
trueが返ってきたら負けとして再帰で解く
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int H, W; vector<string> vs(100); // falseが帰ってきたらかち int memo[111][111][2]; bool dfs(int h, int w, bool who) { if(memo[h][w][who] != -1) return memo[h][w][who]; if(h < 0 || h >= H || w < 0 || w >= W) return false; if(vs[h][w] == '#') return false; bool ret = false; ret |= dfs(h, w + 1, who^1); ret |= dfs(h + 1, w + 1, who^1); ret |= dfs(h + 1, w, who^1); return memo[h][w][who] = ret^1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> H >> W; FOR(i,0,H) { cin >> vs[i]; } FOR(i,0,H+1) FOR(j,0,W+1) FOR(k,0,2) memo[i][j][k] = -1; if(!dfs(0, 0, 0)) cout << "First" << endl; else cout << "Second" << endl; return 0; }
ABC038 D - プレゼント
やっぱり昔のABC-Dは難しい abc038.contest.atcoder.jp 自分用に解法メモなので日本語汚いです。
問題概要
・箱がN個ある
・i番目の箱の大きさは縦hi[cm],wi[cm]
・なるべく多くの箱を入れ子にする時最大で何重にすることができるか
・ある箱は縦、横がともに大きいサイズの箱にのみ入れることができる
※ある箱は1つまでしか他の箱を入れることができない
※箱は回転できない
N, h, w は105以下
解法
dp[i] := i番目の箱が一番外側の時に入れ子にできる最大値
とする
dp[i] = max{dp[j] | hj < hi かつ wj < wi} + 1
である
--全ての箱の縦の長さhが全て異なる場合
縦の長さが小さい箱からdpを更新するようにする
dp[i] = max{dp[j] | j < i かつ wj < wi} + 1
つまりdp[i]を求める時にそれ以前に求めたdp[j]の中でwj<wiを満たすdp[j]の最大値が求まれば良い
wj < wiを満たす区間での最大値を求めれば良い
区間の最大値(最小値)を高速に求めるにはsegment treeを用いる
--同じhの箱がある場合
同じhで一番大きいwの箱のみ使えば良い
これで計算量がO(Nlog(max(w)))となって100点を取れる
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; typedef pair<int, int> P; // セグメント木 [i,j)のmaxをlognで const int NMAX = 1 << 18; int N; struct segment_tree_max { int n; vector<ll> v; segment_tree_max(int _n) { for (n = 1; n < _n; n *= 2); v = vector<ll>(n * 2 - 1, -1e9); } void set(int i, ll x) { int k = i + n - 1; v[k] = max(v[k], x); while (k > 0) { k = (k - 1) / 2; v[k] = max(v[k * 2 + 1], v[k * 2 + 2]); } } ll _get(int i, int j, int k, int l, int r) { if (r <= i || j <= l) return -1e9; if (i <= l && r <= j) return v[k]; ll vl = _get(i, j, k * 2 + 1, l, (l + r) / 2); ll vr = _get(i, j, k * 2 + 2, (l + r) / 2, r); return max(vl, vr); } ll get(int i, int j) { return _get(i, j, 0, 0, n); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; vector<P> vp(N); FOR(i,0,N) { cin >> vp[i].first >> vp[i].second; vp[i].second *= -1; // wでは降順に並び替えるため } sort(vp.begin(), vp.end()); segment_tree_max st(100005); st.set(0, 0); FOR(i,0,N) { int h = vp[i].first, w = -vp[i].second; st.set(w, st.get(0, w) + 1); } cout << st.get(0, 100005) << endl; return 0; }
segment tree強い
Tenka1 Programmer Contest 参加記録
CD解けたのにunratedになり悲しいコンテストでした
C - 4/N
3変数あるが式変形して2変数の値を全探索O(N2)
int main() { ios::sync_with_stdio(false); cin.tie(0); ll N; cin >> N; FOR(n,1,3501) { FOR(w,1,3501) { if(4 * n * w > N * (w + n)) { if((N * n * w) % (4 * n * w - N * (w + n)) == 0) { cout << (N * n * w) / (4 * n * w - N * (w + n)) << " " << n << " " << w << endl; return 0; } } } } }
D - IntegerotS
bitwise orがKのビットが立っているとこだけ1になるようにする。もしくはKのビットが立っているところ1つは1にならないようにするとそのビットより下位のビットを全て1にできるので有利かもしれない。1にならないようにする桁を全て試せばOK。
int main() { ll N, K; cin >> N >> K; ll A[N], B[N]; FOR(i,0,N) cin >> A[i] >> B[i]; ll ans = 0; FOR(j,0,32) { // jより上は1のとこしかだめ if((K>>j)&1) { ll mx = 0; FOR(l,0,N) { bool ok = true; FOR(i,j,32) { if((!((K>>i)&1)||(i==j)) && (A[l]>>i)&1) ok = false; } if(ok) mx += B[l]; } ans = max(ans, mx); } } ll mx = 0; FOR(l,0,N) { bool ok = true; FOR(i,0,32) { if(!((K>>i)&1) && (A[l]>>i)&1) ok = false; } if(ok) mx += B[l]; } ans = max(ans, mx); cout << ans << endl; return 0; }
SRM602 div2 Med PilingRectsDiv2
問題読み間違えて詰んでた
問題概要
・幅Xi高さYiの長方形がN個ある
・面積がlimit以上となるように長方形を重ねる(はみ出して良い、はみ出したらいけないと思っていた)
・90度回転して良い
・最大で何枚重ねられるか
方針
まず幅>高さとなるようにし、幅で昇順に並び替える。重ねる長方形の最小の幅を固定し重ねた時にlimitを超えるかどうか調べる。超えるなら重ねる。
最小の幅がO(N)。それぞれの最小の幅について幅が最小の幅以上の長方形についてlimitを超えるかどうかの計算でO(N)。よって計算量はO(N2)。
コード
typedef pair<int, int> P; class PilingRectsDiv2 { public: int getmax(vector <int> X, vector <int> Y, int limit) { int n = X.size(); vector<P> v(n); FOR(i,0,n) { if(X[i] < Y[i]) swap(X[i], Y[i]); v[i] = P(X[i], Y[i]); } sort(v.begin(), v.end()); int ans = -1; FOR(i,0,n) { int cnt = 0; FOR(j,i,n) if(v[i].first * min(v[i].second, v[j].second) >= limit) cnt++; if(cnt) ans = max(ans, cnt); } return ans; } };
英語難しい
SRM601 div2 Med WinterAndCandies
問題概要
・i番目のキャンディーのタイプはa_i
・タイプが1,2,3...,Kまで1つずつになるようにキャンディーを選ぶ選び方は何通りか
方針
・K = 1の時
1の個数
・K = 2の時
1の個数×2の個数
・K = xの時
1の個数×2の個数×...×xの個数
となるのでこれらを全て足した値が答え。
コード
class WinterAndCandies { public: int getNumber(vector <int> type) { int ret = 0; int num[51]; CLR(num); FOR(i,0,(int)type.size()) { num[type[i]]++; } int t = 1; FOR(i,1,51) { t *= num[i]; ret += t; } return ret; } };
