ARC043 B - 難易度
やり直し
B: 難易度 - AtCoder Regular Contest 043 | AtCoder
問題概要
- 難易度Diの問題がN個ある
- 以下の条件を満たす4問を選ぶ選び方は何通りか
- 2 問目の難易度は 1 問目の難易度の 2 倍以上である
- 3 問目の難易度は 2 問目の難易度の 2 倍以上である
- 4 問目の難易度は 3 問目の難易度の 2 倍以上である
部分点
4≦N≦3000
満点
4≦N≦105
解法
選ぶ問題を難易度順にa,b,c,dとする。
- 部分点解法
b,c(b * 2 ≦ c)を固定して考える。
この時aはb/2以下のDiの個数(x個とする)、dは2c以上のDiの個数(y個とする)通りあるのでb,cを固定した時はxy通りある。
これを全てのb,cの組み合わせについて計算して足せばO(N2)で解くことができる。
- 満点解法
D_iを昇順にソートしておき、二分探索で、 部分点解法と同様に全てのD_iについてそれの半分以下のD_jの個数と2倍以上のD_jの個数を保存しておく。
満点解法ではbを固定して考える。
aは部分点と同じ方法で何通りあるかわかっている。
c,dの組み合わせが何通りあるか。
c=D_iの時、dはD_i * 2 ≦ D_j を満たすD_jである。
例えば、cがD_i以上の時、c,dの組み合わせは、
D_iの2倍以上のD_jの個数+D(i+1)の2倍以上のDjの個数+D(i+2)の2倍以上のDjの個数＋・・・
通りある。これは累積和を用いれば高速に求めることができる。
bごとに最小のcを求め累積和でc,dの組み合わせの数を求めaの個数と掛け算すれば良い。
O(Nlog(N))。
コード
#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 = 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(0); int N;cin >> N; vector<int> D(N); FOR(i,0,N) cin >> D[i]; sort(D.begin(), D.end()); int high[N]; CLR(high); int low[N]; CLR(low); FOR(i,0,N) { high[i] = N - (lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin()); low[i] = upper_bound(D.begin(), D.end(), D[i] / 2) - D.begin(); } int sum[N+1]; sum[0] = 0; FOR(i,0,N) sum[i+1] = (sum[i] + high[i]) % MOD; ll ans = 0; FOR(i,0,N) { int j = lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin(); ans += (ll)low[i] * (ll)(sum[N]-sum[j]); ans %= MOD; } cout << ans << endl; return 0; }
ARC009 C - 高橋君、24歳
やり直し
問題概要
N人に手紙をそれぞれの人の宛名で出そうとしたが、K人は自分の宛名ではない手紙がきてしまった。手紙の渡し方は何通りあるか。1,777,777,777で割った余りを求めよ。
2≦N≦777,777,777,777,777,777
2≦K≦777,777
解法
Nがめちゃくちゃ大きい
自分宛ではない手紙が来る人はN_C_Kパターン。これはフェルマーの小定理を用いて求める。
自分の宛名でない手紙が来るK人について、そのK人の手紙の受け取り方のパターンは、 1~nの数列a_1,a_2,...,a_nがあったとしてa_i = iにならないように数列を並び替えるパターンの数(モンモール数というらしい)に等しい。
これは漸化式->f_k = (k-1)*(f(k-1)+f(k-2))で求めることができる。(f_1 = 0, f_2 = 1)
コード
#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 ll MOD = 1777777777; // bの逆元求める ll IE(ll b) { ll ret = 1; ll M = MOD - 2; for (; M; b = (b * b) % MOD, M >>= 1) { if(M & 1) ret = (ret * b) % MOD; } return ret % MOD; } // 組み合わせO(r) ll C(ll n, ll r) { r = min(r, n - r); ll ret = 1; ll rr = r; for (ll i = n; i >= n - r + 1; i--) { ret = (ret * (i % MOD)) % MOD; ret = (ret * IE(rr)) % MOD; rr--; } return ret % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, K; cin >> N >> K; ll ans = C(N, K); // aは1~nの数字を並び替えた数列 a_i != iを満たす数列は何通りあるか 漸化式->f_k = (k-1)*(f_(k-1)+f_(k-2)) ll f[K+1]; f[1] = 0; f[2] = 1; FOR(i,3,K+1) f[i] = (ll)(i-1) * (f[i-1]+f[i-2]) % MOD; cout << ans * f[K] % MOD << endl; return 0; }
モンモール数知らなかった
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; }
