CS Academy BST Fixed Height
リンク : https://csacademy.com/contest/archive/task/bst-fixed-height/statement/
問題概要
Nこの頂点を持ち、深さHの完全二分木の一部を使った木は何通りあるか求めよ。
解説
正直自分にはこの解説はかけない。最初、dp[i][j][k]:深さiのときの頂点をj個をすでに使い、i-1の頂点がk個あるときと考えたが、到底間に合わない。そこで求めるべきdpは[i][j]でi個すでに使い、深さjのときの通り数である。そこで、dp[i][j]の通り数は右の部分木と左の部分木のどちらかがj-1であればよい。両方j-1のときと、片方がj-1でありもう片方はj-1未満であるときを求めればよい。
両方j-1のときは
dp[i][j]+=sum{k=0,1..i}{dp[k][j-1]×dp[i-k][j-1]}
片方j-1のときは
dp[i][j]+=sum{k=0,1...i}{dp[k][j-1]×sum{l=0,1...j-2}{dp[i-k][l]}}
ここで計算量を減らすために、sum{l=0,1...j-2}{dp[i-k][l]}の部分は別で値を持っておく必要がある。これでO(H*N2)で解けた。
しかし実は、このまま実装すると数ケースでTLEするので自明に必要のないforの範囲を縮めたりする必要がある。
LL n, h, dp1[600][600], dp2[600][600]; LL DP(int x, int y, int flag) { if (flag == 1) { if (y < 0)return 0; if (x < y)return 0; if (y == 1)return x == 1; if (dp1[x][y] != -1)return dp1[x][y]; LL ret = 0; for (int i = y - 1; x - i - 1 >= y - 1; i++) { ret += DP(i, y - 1, 1)*DP(x - i - 1, y - 1, 1); ret %= MOD; } for (int i = y - 1; i < x; i++) { ret += DP(i, y - 1, 1)*DP(x - i - 1, y - 2, 2) * 2; ret %= MOD; } return dp1[x][y] = ret; } else { if (dp2[x][y] != -1)return dp2[x][y]; if (x == 0)return 1; if (x < 0||y < 0)return 0; LL ret = 0; ret += DP(x, y, 1) + DP(x, y - 1, 2); ret %= MOD; return dp2[x][y] = ret; } } int main() { cin >> n >> h; rep(i, n + 1)rep(j, h + 1)dp1[i][j] = -1; rep(i, n + 1)rep(j, h + 1)dp2[i][j] = -1; cout << DP(n, h, 1) << endl; return 0; }
CS Academy Subarray Removal
リンク : https://csacademy.com/contest/archive/task/subarray_removal/submissions/
問題概要
長さNの数列が与えられる。この数列から空でないかつ最大N-1個の連続した数列を取り除く。そのときの区間の和が最大のときの値を求めよ。
解説
まず、5つの区間に分けられる。(全部取らない)→(全部取る)→(取り除かれる)→(全部取る)→(全部取らない) となる。これに対応するようにdp[i][j]をつくるとできる。(j=0のとき取らない、j=1のとき取る...)
「空」でない数列を取り除くを読めなくてごめんなさい。
あと類題として、
atcoder.jp
がある。
LL n, a[110000], ans = -INF , dp[110000][3]; int main() { cin >> n; rep(i, n) { cin >> a[i]; } rep(i, n + 1)rep(j, 3)dp[i][j] = -INF; //0:排除区間でない、1:排除区間、2:排除区間でない rep(i, n) { dp[i + 1][0] = max({ dp[i + 1][0],dp[i][0] + a[i],a[i] }); dp[i + 1][1] = max({ dp[i + 1][1],dp[i][1],dp[i][0] }); dp[i + 1][2] = max({ dp[i + 1][2],dp[i][2] + a[i],dp[i][1] + a[i] }); } for(int i=1;i<=n;i++)for(int j=1;j<3;j++)ans = max(ans, dp[i][j]); cout << ans << endl; return 0; }
CS Academy And Closure
リンク : https://csacademy.com/contest/archive/task/and-closure/statement/
問題概要
長さNの数列が与えられて、個の部分集合のすべてをandで計算したときの数字の種類は何種類か求めよ。
解説
一見簡単そうに見えたが実は罠。dp[i]をiの集合を部分集合としてもつ数字をすべて&したときの数と置くと、dp[i]=iのときはiが答えに含まれることになる。そこで、それぞれの数字の部分集合を列挙して計算しようとすると、それぞれ、x<=106よりΣ[k=0~20]{2k20Ck}かかり、これは3.5×109くらいになりTLEとなる。そこでiを部分集合としてもつdpをしたいと考えると、高速ゼータ変換にたどり着く。高速ゼータ変換の解説はここではできないので省略する。簡単に話すと、1??を4を部分集合としてもつ集合とあらわすとすると、A[i]のすべてのiについて求まっているとき、dp[i] (iは1と?の集合)に関して計算がO(n2n)(nはビット数)でできるということ。
急に問題の難易度上がってびっくりした。あと海外でこれはSOS dpっていうのかもしれない。
LL n, a[110000], ans, dp[1<<21]; int main() { cin >> n; rep(i, n) { cin >> a[i]; dp[a[i]] = a[i]; } rep(i, 1<<21) { if(dp[i]==0) dp[i] = (1 << 21) - 1; } dp[0] = 0; rep(i, 21) rep(b, 1 << 21) if (0 == (b & (1 << i))) dp[b] &= dp[b | (1 << i)]; rep(i, 1100000)if (dp[i] == i)ans++; cout << ans << endl; return 0; }
CS Academy To Front - To Back
リンク : https://csacademy.com/contest/archive/task/to-front-to-back/statement/
問題概要
長さNの1～Nを一つずつ含む数列が与えられる。この数列をソートしたい。任意の数字を先頭か後尾に移動させることによってソートする。ソートし終わったときのこの操作の最小回数とその操作の内容を出力せよ。
解説
まず、数字iのindexをindex[i]とおく。index[i]<index[i+1] である連続の整数の最長の長さを求める。この最長に含まれる数字は、移動させずにほかを移動させることで最小の回数になる。l～rがその範囲であるとすると、l-1,l-2...1までを順番に先頭に移動させてから、r+1,r+2...nを後尾に持っていくことで最小の回数となる。
LL n, dp[110000]; Pll a[110000], mx; int main() { cin >> n; rep(i, n) { cin >> a[i].fir; a[i].sec = i; } sort(a, a + n); rep(i, n - 1) { if (a[i].sec < a[i + 1].sec) { dp[i + 1] = dp[i] + 1; if (dp[i + 1] > mx.fir) { mx.fir = dp[i + 1]; mx.sec = i + 2; } } } cout << n - mx.sec + mx.sec - mx.fir - 1 << endl; for (int i = mx.sec + 1; i <= n; i++) cout << i << " " << 1 << endl; for (int i = mx.sec - mx.fir - 1; i > 0; i--) cout << i << " " << 0 << endl; return 0; }
CS Academy Surrounded Rectangle
リンク : https://csacademy.com/contest/archive/task/surrounded-rectangle/statement/
問題概要
N*Mの行列が与えられる。これは0,1から成る。0で完全に囲まれた1のみからなる長方形の面積を求めよ。完全に囲まれるとは、入力例を参照してほしい。
解説
やるだけ。
N,M<=1000より嫌な予感がしたが、実装するだけだった。1しかない長方形を探し、その外側がしっかり0で囲まれていることを確認してから、答えを更新する。
LL h, w, ans = -1, a[1100][1100]; LL dfs(int x, int y) { LL z = x, v = y; while (a[z + 1][y]) { z++; if (a[z][y - 1] != 0)return -1; if (z == h-1)return -1; } while (a[x][v + 1]) { v++; if (a[x - 1][v] != 0)return -1; if (v == w-1)return -1; } for (int i = x; i <= z; i++) for (int j = y; j <= v; j++) { if (a[i][j] != 1)return -1; } for (int i = x; i <= z; i++) if (a[i][v + 1] != 0)return -1; for (int i = y; i <= v; i++) if (a[z+1][i] != 0)return -1; if (a[z + 1][v + 1] !=0)return -1; if (a[z+1][y - 1] != 0)return -1; if (a[x - 1][v+1] != 0)return -1; return (z - x + 1)*(v - y + 1); } int main() { cin >> h >> w; rep(i, h) rep(j, w) cin >> a[i][j]; rep(i, h) rep(j, w) if (i != 0 && j != 0 && i != h - 1 && j != w - 1) if (a[i - 1][j - 1] == 0 && a[i - 1][j] == 0 && a[i][j - 1] == 0) ans = max(ans, dfs(i, j)); cout << ans << endl; return 0; }
CS Academy Lightbulbs
リンク : https://csacademy.com/contest/archive/task/lightbulbs/statement/
問題概要
01から成る文字列が入力される。i番目が0の場合電球iがついてなくて、i番目が1の場合電球iがついているとする。電球iの操作できる条件が電球i+1がついていて、電球i+2,i+3,i+4...がすべて消えているときである。このとき、すべての電球を消すための最小回数を求めよ。
解説
1のとき、1回、10のとき、3回、100のとき、7回...1と0がn-1個のとき、2n-1回必要ということが実験するとわかる。そこでdp[i][j]を後ろからi番目の電球がjであり(j=0,1)、iより後ろが全部消えているときの最小回数とする。すると遷移は
if(i番目の状態が0)
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1]+1(i番目を消す)+{(2i)-1}(i-1番目を消す)
else
dp[i][1]=dp[i-1][0];
dp[i][0]=dp[i-1][1]+1+{(2i)-1}(上と同様)
で、実装できる。
n<=50に騙されてどうしようかわからず公式解説よんだ・・・
LL dp[60][2]; string str; int main() { cin >> str; reverse(str.begin(), str.end()); dp[0][str[0]-'0'] = 0; dp[0][1-(str[0]-'0')] = 1; for (int i = 1; i < n; i++) { if (str[i]-'0') { dp[i][0] = dp[i-1][1] + 1 + pow(2, i) - 1; dp[i][1] = dp[i-1][0]; } else { dp[i][1] = dp[i-1][1] + 1 + pow(2, i) - 1; dp[i][0] = dp[i-1][0]; } } cout << dp[n-1][0] << endl; return 0; }
CS Academy Expected Merge
リンク : https://csacademy.com/contest/archive/task/expected-merge/statement/
問題概要
マージソートのアルゴリズムと同様の関数を考えた時に、数列を半分にすることを繰り返す。奇数長の場合、区切られる場所は一意に定まらない。そこで、一様にランダムで分割する場合、各indexのiに関して、関数でiを含む数列の区間の長さの合計の期待値を求めよ。
解説
下の図は、入力が5の場合を考えている。4が含む数列の長さの合計の期待値を求めるときに(3,4,5)と(4,5)を見ることは、(1,2,3)と(1,2)を見ることが同じであることがわかる。
そこでdp[i][j]を長さiの数列のj番目を含む数列の区間の長さの期待値とすると、次の関数に行くときのindexの変化のみ計算すればよい。しかし、これでは空間時間ともにO(n2)になると思うかもしれないが、n→n/2→n/4と変化するため間に存在する多くは巡らない。よってO(n logn)となる。配列も前もって静的に用意してしまうとMLEになってしまう。
LL n; vector<double>dp[110000]; double func(int i, int j) { if (i == 1)return 1; if (dp[i].size() == 0)dp[i].resize(i+1); if (dp[i][j] != 0)return dp[i][j]; double ret = 0; if (i % 2 == 0) { ret += func(i / 2, j % (i / 2)); } else { if (j == (i + 1) / 2) { ret += func((i + 1) / 2, j); ret += func((i + 1) / 2, 1); } else { if (j > (i + 1) / 2) { ret += func(i / 2, j - (i+1) / 2); ret += func((i + 1) / 2, j - (i) / 2); } else { ret += func(i / 2, j); ret += func((i + 1) / 2, j); } } ret /= 2.0; } ret += i; return dp[i][j] = ret; } int main() { cin >> n; rep(i, n) { if (i)cout << " "; printf("%.15f", func(n, i+1)); } cout << endl; return 0; }
