AOJ2642 Dinner
問題ページ
Dinner | Aizu Online Judge
考えたこと
- すべての日で自炊するとする
- このときの幸福度は簡単に求まる
- ある日を自炊から外食に変えると変化する幸福度は(外食の幸福度)-(その日の自炊の分)-(その日以降で自炊する日数)*(定数)
- i日目以降で自炊をj回するときの幸福度の最大値をdp
- これはO(N^2)で無理
- 自炊をi回するときに最適な選び方は何か
- 連続で選ぶとマイナスされる前に自炊で稼げる
- できるだけ外食が低いときに自炊したい
- 自炊の回数と幸福度について単調性→ない
- 凸性→なさそう
- i日目までで最後に自炊をしたのがj日目でDP
- これもN^2で無理ゲー
- i日目に得られる幸福度が高い行動をする貪欲
- 1回目の自炊よりは外食が高いけど後々のために自炊しといた方がいいパターン
- i回自炊をするときの日付の集合がi+1回自炊をするときの日付の部分集合になってて貪欲に選べるみたいな?
- 1回自炊をするときは3日目を選ぶけど2回自炊をするときは1日目と4日目を選んだほうが最適みたいなのが存在しない気持ちになる
- i回自炊するときの幸福度をi-1回自炊するときの幸福度を元にそれぞれO(1)で求められればO(N)でできそう
- 0回自炊をするときの幸福度はO(N)で簡単に求まる
- 自炊の回数を0回→1回にするときでi日目を自炊に変化させるときの幸福度の変化を考える
- これは -(外食の幸福度) + (自炊パワーの初期値+i)*(定数) になる
- これも各日についてO(N)あれば求まる
- i日目を自炊にするとき他の日の幸福度の変化がどう変わるか
- i日目より後の日→自炊パワーが-1されていた状態から+1される状態になる→+2P
- i日目より前の火→i日目の自炊で得られる幸福度がプラスされる→上と同じで+2P
- したがって一回自炊をする日を増やすと他の日の幸福度の変化に+2Pされる
- 外食→自炊に変化させる日は幸福度の変化が最大の日を貪欲に選べばよい
- ソートする部分が一番重くO(NlogN)で間に合いそう
やることは最終的にソートして貪欲だけど考察が大変
複数の操作があるときに全ての項目に対してある片方の操作をすると考えてもう片方に変えるときにどう変化するか
昔やったつるかめ算を思い出す
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, p, q; cin >> n >> p >> q; VI c(n); REP(i, n) cin >> c[i]; int ret = 0; REP(i, n) ret += c[i]; VI v; int now = q; REP(i, n) { v.PB(p*now-c[i]); now--; } sort(ALL(v), greater<>()); now = 0; int ans = ret; REP(i, n) { ret += v[i] + now; chmax(ans, ret); now += 2*p; } cout << ans << endl; return 0; }
AOJ2310 薔薇園の魔女
問題ページ
Rose Garden Witch | Aizu Online Judge
考えたこと
- 左下からの線分の偏角を微小量dtごとに変化させて全部試すみたいな解法を考える
- 判定部分でdfsでO(HW)かかるのでとてもじゃないけど精度がたりなさそう
- 線分を引く位置はどうせ少ないとかがないと不可能そう
- 格子点の前後以外で連結成分数が変動することはなさそう
- 各格子点を通る線分を列挙するのにO(HW)
- 連結成分数を愚直に数えるとdfsでO(HW)で全体O(H^2W^2)でだめそう
- 連結成分数を数えるパートをO(H+W)とかにしてO(HW(H+W))みたいな方針を考える
- 線分が通るマスの数がO(max(H,W))とかなのでこのマスだけをうまく見るみたいなの
- 出来る方法が何も思い浮かばないしそもそも3乗はどうなのか
- 格子点は(i,j)が互いに素な部分だけを気にすればいいのでちょっと枝刈りできそう
- 偏角が小さい格子点から順に試していくと気にする頂点がだんだん増えていってうれしいみたいなのを考える
- 新たに増えた頂点で連結成分数の変動がどうかを高速に判定できる方法がわからない
- どう考えてもO(H^2W^2)から落ちない
-----解説を見た----- - 直線を偏角順で動かしていくことを考えると連結成分数が変動するのは条件を満たす2*2マスの盤面を通過したとき
- 連結成分数が変動する場所の(偏角,+1 or -1)を全て列挙して偏角順に見ていく
- 連結成分数が最大になるタイミングの連結成分数を出力
学び
- 2*2マスの局所的な範囲で区切ると連結成分数が+1 or -1のタイミングを特定できる。
- 条件が変化するタイミングに着目
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int h, w; cin >> h >> w; vector<string> v(h+2, string(w+2, '.')); FOR(i, 1, h+1) { cin >> v[i]; v[i] = '.' + v[i] + '.'; } vector<pair<double,int>> eve; REP(i, h+1) REP(j, w+1) { // (h-i, j+1) の偏角 double ang = atan2(h-i, j); if(v[i][j] == '#' && v[i+1][j] == '.' && v[i][j+1] == '.' && v[i+1][j+1] == '.') { eve.PB({ang, 1}); } if(v[i][j] == '.' && v[i+1][j] == '#' && v[i][j+1] == '#' && v[i+1][j+1] == '#') { eve.PB({ang, 1}); } if(v[i][j] == '.' && v[i+1][j] == '.' && v[i][j+1] == '.' && v[i+1][j+1] == '#') { eve.PB({ang, -1}); } if(v[i][j] == '#' && v[i+1][j] == '#' && v[i][j+1] == '#' && v[i+1][j+1] == '.') { eve.PB({ang, -1}); } } sort(ALL(eve)); int num = 1, ans = 2; for(auto i: eve) { num += i.second; chmax(ans, num); } cout << ans << endl; return 0; }
AGC023 B - Find Symmetries
問題ページ
B - Find Symmetries
考えたこと
- とりあえずよい盤面を書いてみる
- 斜めにずらしたとしてもよい盤面であるのは絶対に変わらない
- したがってB=iとしたときによい盤面であれば斜めにずらしてもよい盤面
- O(N^3)なので書くとサンプルが通らない
- 対称な位置の座標で変なことになってる
- よくわからなかったので実際にずらしたあとの盤面を毎回つくることにしたら通った
(i,j+k)の反転を(j+k,i)にしていた(は?
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<string> s(n); REP(i, n) cin >> s[i]; int ret = 0; REP(i, n) { vector<string> t(n); REP(j, n) t[j] = s[j].substr(i+1) + s[j].substr(0, i+1); bool flag = true; REP(j, n) REP(k, n) { if(t[j][k] != t[k][j]) { flag = false; } } if(flag) ret += n; } cout << ret << endl; return 0; }
AGC023 A - Zero-Sum Ranges
問題ページ
A - Zero-Sum Ranges
考えたこと
- 問題を読むと200点に見えないので真面目に考える
- とりあえず累積和を取ってみる
- i番目を左端とする区間で部分和が0になる区間はa[i]=a[j]となる
- したがってiより右でa[i]と等しいものの数を数える
- mapで現れた頻度を持ちながら右から見ていくとi番目を左端とする区間で条件を満たすものの数がわかる
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; VI a(n); REP(i, n) cin >> a[i]; VI b(n); b[0] = a[0]; FOR(i, 1, n) b[i] = a[i] + b[i-1]; int ret = 0; map<int,int> mp; for(int i=n-1; i>=0; --i) { ret += mp[b[i]]; // b[i]の個数 mp[b[i]]++; } cout << ret+mp[0] << endl; return 0; }
ARC096 F - Sweet Alchemy
問題ページ
F - Sweet Alchemy
解法
問題の整理
d[i] = c[i] - c[p[i]] とするとドーナツをつくれる個数の条件である c[p[i]] <= c[i] <= c[p[i]] + D を 0 <= d[i] <= D と言い換えることができる。ただし根に関してはdに制限はなく 0 <= d[0] となる。
頂点iを根とする部分木について全ての頂点について1つずつドーナツを作る操作を考える。この操作は頂点iを根とする部分木の頂点jについてm[j]の総和のコストがかかり、部分木の頂点数分のドーナツをつくることができる。また、この操作を行うとd[i]が1増える。したがってこの操作は各部分木についてd[i]の上限までしか行うことができない。
ここまでをまとめると、重さがX[i]=(頂点iを根とする部分木の頂点jについてm[j]の総和)で価値がY[i]=(部分木の頂点数分)、個数の上限がZ[i]=(根はINF、それ以外の頂点でD)となるアイテムがN個存在するナップザック問題に帰着できる。
ナップザック問題
まず貪欲に考える。そのアイテムのコスパをY[i]/X[i]で定義し降順にソートする。
p<qであるような2つのアイテムに着目する。もしアイテムqからY[p]個取り出すことができ、アイテムpにY[q]個加算することができれば、この操作は必ず得になる。価値はY[p]d[p] + Y[q]d[q] → Yp + Yq = Y[p]d[p] + Y[q]d[q]で変動なし。重さは X[p]d[p] + X[q]d[q] >= Xp + Xq = X[p]d[p] + X[q]d[q] + X[p]Y[q] - X[q]Y[p] となり小さくなっている。Y[i]<=50なのでpに50個以上まだ取れる余裕があり、qが50個以上なら必ずこの操作は行える。
各アイテムを50個と残りに2分割する。すると、50個の方から一部選び、残りの方はgreedyに選べばいいことがわかる。50個の方はDP、残りは貪欲で解ける。
DP
蟻本P302に載っている個数制限付きナップザックをします。価値の最大値は50^3、個数がNでO(N^4logN)になります。蟻本とは重さと価値が逆ですが本質は同じです。
貪欲
コスパがよいものから取れるだけ取っていく貪欲をします。DPの方でi個取ったとするとX-dp[i]グラムでつくれるだけつくります。
全体でO(N^4logN)で解けました。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; VI g[55]; int m[55]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, x, d; cin >> n >> x >> d; cin >> m[0]; FOR(i, 1, n) { int p; cin >> m[i] >> p; g[p-1].PB(i); } // 頂点iの部分木を取ったときのコストXと価値Yを求める VI X(n), Y(n); function<void(int)> dfs = [&](int v) { X[v] = m[v], Y[v] = 1; for(int i: g[v]) { dfs(i); X[v] += X[i]; Y[v] += Y[i]; } }; dfs(0); VI idx(n); REP(i, n) idx[i] = i; // Y[x]/X[x] >= Y[y]/X[y] ⇔ Y[x]*X[y] >= Y[y]*X[x] でソート sort(ALL(idx), [&](int x, int y){return Y[x]*X[y]>Y[y]*X[x];}); // dp[i] = (価値がiのときの最小の重さ) VI dp(50*50*50+5, INF); // i番目のアイテムについて重さと価値がそれぞれ(X[i],Y[i])(2X[i],Y[i])…(2^kX[i],2^kY[i])が一つずつ存在すると考える dp[0] = 0; REP(i, n) { int num = idx[i]?min(50LL,d):50; for(int k=1; num; k<<=1) { int mul = min(k, num); for(int j=50*50*50; j>=0; --j) { if(j+mul*Y[idx[i]] <= 50*50*50) { chmin(dp[j+mul*Y[idx[i]]], dp[j] + mul*X[idx[i]]); } } num -= mul; } } int ans = 0; REP(i, 50*50*50+1) { // i個作ったとして残りをgreedyに決める if(dp[i]>x) continue; int ret=i, w = x-dp[i]; REP(j, n) { // cnt個取る int cnt = idx[j]?max(0LL, d-50):INF; chmin(cnt, w/X[idx[j]]); ret += cnt*Y[idx[j]]; w -= cnt*X[idx[j]]; } chmax(ans, ret); } cout << ans << endl; return 0; }
ARC096 D - Static Sushi
問題ページ
D - Static Sushi
考えたこと
- 何か既視感を感じる
- どうせ引き返すのは高々1回
- 時計回り or 反時計回りに一方向に回るだけならO(N)で簡単に求まる
- dp1[i] = ([0,i]で得られる最大のカロリー、時計回り)
- dp2[i] = ([i,n-1]で得られる最大のカロリー、反時計回り) とする
- dp1[i] まで行った後に引き返すなら [i+1,n-1]で得られる最大のカロリーまで行くのが最善
- 反時計回り側で得られるカロリーはdp2[i+1]を見ればわかる
- dp2[i] まで行った後に引き返すときも同様にO(1)で求まる
- したがってO(N)で解ける
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, c; cin >> n >> c; VI x(n), v(n); REP(i, n) cin >> x[i] >> v[i]; VI dp1(n); dp1[0] = v[0] - x[0]; FOR(i, 1, n) dp1[i] = dp1[i-1] + v[i] - (x[i] - x[i-1]); FOR(i, 1, n) chmax(dp1[i], dp1[i-1]); VI dp2(n); dp2[n-1] = v[n-1] - (c - x[n-1]); for(int i=n-2; i>=0; --i) { dp2[i] = dp2[i+1] + v[i] - (x[i+1] - x[i]); } for(int i=n-2; i>=0; --i) { dp2[i] = max(dp2[i], dp2[i+1]); } int ans = max(0LL, dp2[0]); REP(i, n) { // i番目まで時計回りで取る int tmp = dp1[i]; // [i+1, n-1] の最大 if(i+1<n && dp2[i+1] - x[i] > 0) tmp += dp2[i+1] - x[i]; chmax(ans, tmp); } for(int i=n-1; i>=0; --i) { int tmp = dp2[i]; if(i >= 1 && dp1[i-1] - (c - x[i]) > 0 ) tmp += dp1[i-1] - (c - x[i]); chmax(ans, tmp); } cout << ans << endl; return 0; }
ARC096 C - Half and Half
問題ページ
C - Half and Half
考えたこと
- 頑張って数学O(1)もありそうだけど絶対つらい
- 制約を見ると10^5なのでO(max(X,Y))できる
- ABピザを2i枚使ったとするとAピザ、Bピザの枚数は一意に定まる
- 全探索をする
ソースコード
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int a, b, c, x, y; cin >> a >> b >> c >> x >> y; int ans = LLINF; REP(i, max(x, y)+1) { // i*2枚をAB pizza int tmp = i*c*2; if(x > i) tmp += (x-i)*a; if(y > i) tmp += (y-i)*b; chmin(ans, tmp); } cout << ans << endl; return 0; }