Codechef - Country Tour [CTOUR]
Encoderっていうコンテストの最後の問題
何気なく参加してみたけどこの問題は個人的に面白かった
問題
n頂点の木が与えられ、根は頂点1である
辺iは頂点a[i]とb[i]を繋ぎ、通る時c[i]円貰える
(c[i]が負のこともあり、そういうときは逆に-c[i]円払わないといけない)
q個のクエリが与えられるので、頂点a[i]からb[i]に行くまでに得られる金額の最大値 or 払わないといけない金額の最小値を求めよ
ただし、頂点aからbに移動する最中、向きを変えることが出来るのは一度だけである
※向きってのは根に向かって進む方向と根から離れる方向の2通りだけ考える
例えば1-2-3って木で3から2に向かう場合、1まで進んでから向きを変えて2に戻るって動きが出来る
解法
一直線にaからbに移動する場合のコストは、事前に頂点1と各頂点のパス上のコストの和を求めておき、aとbのLCAを求めることでO(logn)で求められる
向きを1度だけ変えられるってのを上手く利用して更にコストを増やしたい
始点aと終点bのLCAをvとする
・a=vのとき
aから根方向に進んで、コストが最大になるところで向きを変え、bまでまっすぐ進む
or bまで進んでから更に根と反対方向に進み続け、コストが最大になるところで向きを変え、bに戻る
・b=vのとき
aから根と反対方向に進んで、〜、bまで進む
or bまで進んでから更に根方向に進み続け、〜、bに戻る
・どちらでもないとき
aからvに進んでから更に根方向に進み続け、〜、vに戻り、そのままbまで進む
この3通りが考えられる
あとは各頂点から「根方向に進むときのコストの和の最大値」と「根と逆方向に進むときのコストの和の最大値」を求められれば解ける
これらはどちらも累積和っぽい再帰で求められる
int n, Q, a, b, c, pa[100100], ch[100100], s[100100]; vector<pair<int,int> > e[100100]; LCA lc; int rec(int v, int p, int sum, int mn) { s[v] = sum, pa[v] = sum - mn; each(i,e[v]) if (i.first!=p) { int tsum = sum + i.second; int mx = rec(i.first, v, tsum, min(mn, tsum)); chmax(ch[v], mx + i.second); } return ch[v]; } signed main() { cin >> n >> Q; rep(i,n-1) { cin >> a >> b >> c; a--, b--; e[a].push_back({b,c}), e[b].push_back({a,c}); lc.add(a,b); } rec(0,-1,0,0); lc.init(n,0); while (Q--) { cin >> a >> b; a--, b--; int v = lc.lca(a,b); int res = s[a] + s[b] - s[v]*2; if (a==v) res += max(pa[a], ch[b])*2; else if (b==v) res += max(ch[a], pa[b])*2; else res += pa[v]*2; cout << res << endl; } }
SRM574 Div1 Easy - TheNumberGame
問題
先手が数字a、後手がbを持っており、どちらも0の桁はない
各ターンで各プレイヤーは自分の数字を反転するか最後の桁を消すかを選ぶ
途中で両者の数字が一致したら先手の勝ちで、いつまでも一致しない場合は後手の勝ちになる
両者が最善を尽くすときどちらが勝つか判定せよ
1 <= a, b < 10^9
解法
aか反転したaの連続する部分列にbが存在すれば先手が勝ち、そうでなければ後手の勝ち
前者のときはaの両端を削ってbに近付ければいつかは必ず一致する
(bが逃げるには数字を削るしかなく、最終的に数字が空になって一致する)
後者のときは後手は毎ターン数字を反転させてればいい
class TheNumberGame { public: string determineOutcome(int a, int b) { string x = to_string(a), y = to_string(b); int n = x.size(), m = y.size(); if (n<m) return "Manao loses"; rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins"; reverse(all(x)); rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins"; return "Manao loses"; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12474&rd=15494
SRM573 Div1 Easy - TeamContest
問題
大学に人が3n人いて、i人目の強さはa[i]である
これらの3n人から3人チームをn組作る
3人チームの強さは3人の強さの最大値と最小値の和で決まる
0〜2人目が一緒にチームを組むことはもう決まっている
他の3n-3人のチーム分けを工夫すると、このチームより強いチームは最大何組作れるか
1 <= n <= 16
1 <= a[i] <= 10^6
解法
貪欲
ややこしいから最初の3人のチームの強さをkとし、その3人は除外して、残った人数を3nとする
まだ組になっていない人のうち最も強い人をチームの最大値担当として1人選ぶ
この人の強さをxとする
次にk-xを超える最小の強さを持つ人を1人探し、居たらその人を最小値担当として選ぶ
この人の強さはyとする
y以上x以下の強さを持つ人がいれば、そのうち最も弱い人を選び、この3人をチームにする
↑この流れを繰り返すのが最善
class TeamContest { public: int worstRank(vector<int> a) { int k = max(a[0],max(a[1],a[2])) + min(a[0],min(a[1],a[2])); rep(i,3) a.erase(a.begin()); sort(a.rbegin(), a.rend()); int n = a.size(), res = 1, r = n-1; rep(l,n) { while (r>=0 && a[l]+a[r]<=k) r--; if (l+2<=r) res++, r -= 2; } return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12470&rd=15493
SRM572 Div1 Easy - NewArenaPassword
問題
topcoderのパスワードをsにしていた
ある日「パスワードの最初のk文字と最後のk文字は一致していないといけない」という新ルールが出来た
新ルールを守るようなパスワードに変更するとき、sから変更する文字数の最小値を求めよ
1 <= |s| <= 50
1 <= k <= |s|
解法
sの長さをnとすると、条件は
「i文字目とi+n-k文字目が一致する (0<=i
class NewArenaPassword { public: int minChange(string s, int k) { int n = s.size(), res = 0; rep(i,k) { int a[26] = {}, sz = 1; for (int j=i; j<n; j+=n-k, sz++) a[s[j]-'a']++; res += sz - *max_element(a,a+26); } return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12386&rd=15492
ARC081 F - Flip and Rectangles
問題
h*wのマス目があり、各マスの色は黒か白である
「ある行[列]を選び、その行[列]の全てのマスの色を反転する」という操作を任意の回数行える
黒いマスのみを内側に含む長方形の面積の最大値を求めよ
2 <= h, w <= 2000
解法
タテかヨコの長さが1の長方形は明らかに自由に選べる
そうでない場合は？
2*2マスの正方形のうち黒マスを偶数個含むようなものは、操作によって4マスとも黒マスにすることができる
そういう正方形のみからなる任意の長方形も全部黒マスにできる (具体的には解説pdfの通り)
逆に奇数個含むような正方形はどう操作をしても無理
よって後者の正方形を内側に含まないような長方形のうち面積最大のものを求めればいい
これは蟻本p298のヒストグラムの最大長方形をスタックで求めるやつとほぼ同じようにできる
蟻本のやつ一回読んで理解できなくて投げたのは覚えてた
そろそろ上級編も読んだ方がいいかも・・
int h, w, ng[2020][2020], x[2020], res; string s[2020]; signed main() { cin >> h >> w; res = max(h,w); rep(i,h) cin >> s[i]; rep(i,h) { rep(j,w-1) { if (i && !(s[i-1][j]^s[i-1][j+1]^s[i][j]^s[i][j+1])) x[j]++; else x[j] = 1; } stack<int> s; rep(r,w) { while (!s.empty() && x[s.top()]>=x[r]) { int t = s.top(); s.pop(); int l = (s.empty() ? -1 : s.top()); chmax(res, x[t]*(r-l)); } s.push(r); } } cout << res << endl; }
EducationalCF53 E - Segment Sum
かなり残念な落とし方をした
4完でもhighest更新したからこれも通ってれば・・😠
問題
L以上r以下の整数のうち、各桁の数字の種類がk以下であるものの和を求めよ
1 <= L <= r < 10^18
1 <= k <= 10
解法
とりあえず求めるものは (r以下の条件を満たす数字の和) - (L-1以下の〜) としてok
1桁ずつ考える
まず1の位に注目し、
Σ (条件を満たし、かつ1の位がxになるような数字の個数) * x (1 <= x <= 9)
を求める
これはありふれた桁dpを、1の位の遷移だけxに絞るようにちょっと書き換えるだけで求められる
10の位以上も同様に求め、それらを足し合わせることで答えが得られる
桁dpのテーブルは
dp[i][j][L][b]: 上からi桁目まで決まり、nより小さいことが確定し(j=1)、leading-zeroは終了し(L=1)、使った数字の組み合わせがbであるような数字の個数
とすればいい
leading-zeroに気を付けないと、例えばnが3桁のとき、11って数字が0と1の2種類の数字を使った数字として扱われてしまう(011)
実装
時間制限が1sで割とギリギリだから無駄な処理はなるべく削った
気を付けたことは
・0〜2^10のpopcountを事前に求めておく(cnt)
・10の0〜18乗も事前に求めておく(ten)
・dp[〜]が空のときはcontinueする
本番では最後のcontinueをしてなくてTLEした
これ書き足しただけで10倍くらい速くなった
これ書かないと無駄な処理が結構増えるのはわかってたけど、そこまで速度に差が出るとは知らなかった & 別にcontinueしなくても答えは変わらないから、別に書かなくてもいいものだと自分の中で思ってた
もう一生continueを省略することはないと思う
関係ないけどコドフォはコードに長めの日本語のコメントが含まれるとJudgement Failedってエラーが出るらしい
ジャッジが詰まってる系だと思ってイラついて連投してたら注意された
#define int long long int l, r, k, cnt[1<<10], ten[33]; int dig(const string &s, int x, int y) { int n = s.size(), dp[22][2][2][1<<10] = {}; dp[0][0][0][0] = 1; rep(i,n) rep(j,2) rep(l,2) rep(b,1<<10) if (dp[i][j][l][b]) { if (i==x) { if (cnt[b|(1<<y)]>k) continue; if (j==0 && s[i]-'0'<y) continue; (dp[i+1][j|(s[i]-'0'>y)][1][b|(1<<y)] += dp[i][j][l][b]) %= mod; } else { rep(t,(j ? 10 : (s[i]-'0')+1)) { int bit = (l==0 && t==0 ? b : b|(1<<t)); if (cnt[bit]>k) continue; (dp[i+1][j|(s[i]-'0'>t)][l|(t!=0)][bit] += dp[i][j][l][b]) %= mod; } } } int res = 0; rep(i,2) rep(l,2) rep(j,1<<10) (res += dp[n][i][l][j]) %= mod; return res; } int ans(int n) { string s = to_string(n); int res = 0, m = s.size(); rep(i,m) reps(j,1,10) { if (i==0 && s[i]-'0'<j) continue; (res += dig(s,i,j) * ten[m-i-1] %mod * j) %= mod; } return res; } signed main() { rep(i,1<<10) cnt[i] = __builtin_popcount(i); ten[0] = 1; reps(i,1,33) ten[i] = ten[i-1]*10 %mod; cin >> l >> r >> k; cout << (ans(r) - ans(l-1) + mod) %mod << endl; }
CF518 Div2 D - Array Without Local Maximums
これ割とあからさまなdpじゃない？
問題
いくつかの要素が-1になっている長さnの数列が与えられる
↓の条件を満たすように-1を1〜200に変えるとき、何通りの数列が作れるか
1) a[1] <= a[2]
2) a[n-1] >= a[n]
3) a[i] <= max(a[i-1], a[i+1]) (1 < i < n)
2 <= n <= 10^5
解法
dp[i][j][k]: i-1番目まで埋め終わってて、a[i-1]をjに変えて、a[i-1]とa[i-2]の関係がkであるような数列の個数
k=0) a[i-2] > a[i-1]
k=1) a[i-2] = a[i-1]
k=2) a[i-2] < a[i-1]
条件3よりk=0,1のときはa[i]は自由に決められる
k=2のときはa[i-1] <= a[i]となるようにしないといけない
よってdp[1][j][2]のみ1にしておけば条件1は勝手に満たせる
また条件2より答えは Σ dp[n][j][0,1]
遷移はa[i]≠-1のときは普通に
dp[i+1][a[i]][〜] += dp[i][j][k] (1 <= j <= 200)
そうじゃないときはまともにやると
dp[i+1][j'][〜] += dp[i][j][k] (1 <= j <= 200, 1 <= j' <= 200)
でTLEするけど、imos法を使えばj'のループが必要なくなる
実装
メモリ制限は512mbだから節約しなくても足りる
int n, a[100100], dp[100100][222][3]; signed main() { cin >> n; rep(i,n) cin >> a[i]; if (a[0]!=-1) dp[1][a[0]][2] = 1; else reps(i,1,201) dp[1][i][2] = 1; reps(i,1,n) { if (a[i]==-1) { reps(j,1,201) rep(k,3) { if (k!=2) { if (j>=2) (dp[i+1][1][0] += dp[i][j][k]) %= mod, (dp[i+1][j][0] += mod-dp[i][j][k]) %= mod; (dp[i+1][j][1] += dp[i][j][k]) %= mod; if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod; } else { (dp[i+1][j][1] += dp[i][j][k]) %= mod; if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod; } } rep(k,3) if (k!=1) reps(j,1,201) (dp[i+1][j][k] += dp[i+1][j-1][k]) %= mod; } else { reps(j,1,201) rep(k,3) { if (k!=2) (dp[i+1][a[i]][a[i]==j ? 1 : (j<a[i] ? 2 : 0)] += dp[i][j][k]) %= mod; else if (j<=a[i]) (dp[i+1][a[i]][(a[i]==j ? 1 : 2)] += dp[i][j][k]) %= mod; } } } int res = 0; reps(i,1,201) rep(j,2) (res += dp[n][i][j]) %= mod; cout << res << endl; }
