[PGBattle2021] せんべい反省会
[Q] https://products.sint.co.jp/q_list_2021
TOPSIC > 使い方 > 練習問題
https://pgbattle2022.topsic.org/practice
から提出できます。
[A] 7番勝負
・考察
次の4通りの総和だと思う。
p^4 * op^3 * 7C4+
p^5 * op^2 * 7C5+
p^6 * op^1 * 7C6+
p^7 * op^0 * 7C7
p = P/100なので、これをdoubleで7回やってもいいのか迷う。精度壊れる？
doubleは15桁まで保証される、と思っていて、6桁まであっていればいいなら、大丈夫な気がする。
念のため途中計算はlong long にするなどした。
ll DP[110][110];
// 二項定理
void nck() {
DP[0][0] = 1;
rep(i, 100) {
rep(j, i + 1) {
DP[i + 1][j] += DP[i][j];
DP[i + 1][j + 1] += DP[i][j];
}
}
}
int main() {
cincout();
nck();
ll P;
cin >> P;
ll O = 100 - P;
ll E[8]{};
ld ans = 0;
ll denominator = 1;
rep(i, 6) denominator *= 100; // 百分率の*100を前もって相殺
for (ll i = 4; i <= 7; ++i) {
ll p = 1; // doubleでとると精度壊れる？
rep(j, i) { p *= P; }
rep(j, 7 - i) { p *= O; }
ld add = p;
add /= denominator;
add *= DP[7][i];
ans += add;
}
cout << ans << endl;
}[B] 連結成分数の見積もり
・考察
連結成分が最小 = 無駄なく橋を架ける。
連結成分が最大 = 無駄に橋を架ける。
1. 最小はたぶん簡単。N-1本の橋があれば、全部の島を連結にできるから、逆算。
2. 最大について。もし島が4つあったとしたら、橋は最大で4C2=6本無駄遣いできる。
3. sqrtl(M*2)で、使う橋を網羅する島数を、大まかに求められるはず。
4. そこから、橋を全消費できる最小の島の数を導く。この島で橋を消化しきると仮定する。
int main() {
cincout();
ll T, N, M;
cin >> T;
rep(i, T) {
cin >> N >> M;
ll mx = 0;
ll mn = oo;
// 最小
mn = max(1LL, N - M);
// 最大
// 1塊にできる島の数
// 3C2=3
// sqrt(3*2) = 2....
// 3*2/2=3 <= 3
// 3が、消化するのに必要な島の数
ll mxblock = sqrtl(M * 2);
while (mxblock * (mxblock - 1) / 2 < M) {
++mxblock;
}
mx = min(N, N - mxblock + 1);
cout << mn << " " << mx << endl;
}
}[C] トーナメント表
・考察
こんなふうに配置したい。
3
8 8 2 1 8 4 4 8
1 X 2 X 5 X 8 X %2==0
6 X 7 X %4==1
3 X %8==3
4 %16==7
---------------
1 6 2 3 5 7 8 4 という感じで配置・実装
ll ans[(1 << 16) + 10];
ll memo[(1 << 16) + 10];
vector<ll> G[17];
int main() {
cincout();
ll N;
cin >> N;
{ // 2^m を mに変換
ll n = 1;
rep(i, N + 1) {
memo[n] = i;
n *= 2;
}
}
rep(i, (1 << N)) {
ll a;
cin >> a;
ll m = memo[a]; // 2^mで処理
G[m].emplace_back(i);
}
// ベストNが必要数あるか
rep(i, N + 1) {
ll check = 1 << (i - 1);
if (check == 0) check = 1;
if (G[i].size() != check) {
cout << -1 << endl;
return 0;
}
}
// ansに配置
ll loop = 2;
rep(i, N + 1) {
ll remainder = loop / 2 - 1;
ll cnt = 0;
rep(j, (1 << N)) {
if (j % loop == remainder) {
ans[j] = G[N - i][cnt];
++cnt;
}
}
loop *= 2;
}
rep(i, (1 << N)) { cout << ans[i] + 1 << " \n"[i == (1 << N) - 1]; }
}[D] [リ[[スー]バ][ズパ]ル]
・考察
1. 包含された幅のうち、最も深くにある場所から処理していきそう。dfsで探索しようと思う。
2. 与えられた範囲の中でできることがreverseしかない。
3. reverseしたときに辞書順で小さくなるならするし、ならないならしない。でいけるかとエスパー。
4. 包含の中に包含が含んでいるときを考える。外包含を反転したときに、中包含も再度反転するような処理が必要。それはTLEなので、処理を高速化したい。
5. 包含する値は、先頭の値だけとっておきさえすれば、以降の探索に関係ない気がする。復元できるようにしておけばよさそう。
6. どう処理していこう
例
[1,
2, [3, 4], [5, [6, 7]], 8]
[1, 8]の気持ちを考える。
以下の塊に分かれる。
[1, 2, [X, X], [Y, [Z, Z]], 8]
1. [X, X]を処理する。[3, 4]
[1, 2, [3, 4], [Y, [Z, Z]], 8]
ここで、[3, 4]で管理するのは数字が多いので、メモして別の箱に格納する。
G[3] = {3, 4}
[1, 2, [3], [Y, [Z, Z]], 8]
2. [Z, Z] を処理する。[6, 7]
[1, 2, [3], [Y, [6, 7]], 8]
ここで、[6, 7]で管理するのは数字が多いので、メモして別の箱に格納する。
G[3] = {3, 4}
G[6] = {6, 7}
[1, 2, [3], [Y, [6]], 8]
2. [Y, 6] を処理する。[5, 6]
[1, 2, [3], [5, [6]], 8]
ここで、[5, [6]]で管理するのは数字が多いので、メモして別の箱に格納する。
G[3] = {3, 4}
G[6] = {6, 7}
G[5] = {5, 6}
[1, 2, [3], [5], 8]
4. [1, 8] が処理できる。
[1, 2, 3, 5, 8]
[1, 2, 3, 5, 8]は数字が多いので、メモ。
G[1] = {1, 2, 3, 5, 8}
G[3] = {3, 4}
G[6] = {6, 7}
G[5] = {5, 6}
最終的に先頭は[1]とわかる。
5. 解答の復元
[1]
G[1] = {1, 2, 3, 5, 8}
G[3] = {3, 4}
G[6] = {6, 7}
G[5] = {5, 6}
G[1]から、
{1, 2, {3, 4}, {5, {6, 7}}, 8}
を復元。ll P[200020];
ll N, M;
vector<pll> V; // [L, -R]
vector<ll> G[200020]; // G[1] = {1,5,3,6...} 先頭の数字から始まる、それ以降の塊をメモ
ll dfs(ll d) { // Vのindex0-M
vector<ll> ret;
auto [L, R] = V[d];
R = -R; // この範囲を調べる
++d;
ll i = L;
// 子供がいるか
// L<=nL && nR<=R なら深く潜っていく
while (d <= M) {
auto [nL, nR] = V[d];
nR = -nR;
if (R < nL) break;
for (; i < nL; ++i) {
ret.emplace_back(P[i]);
}
ll s = dfs(d);
if (s >= 0) ret.emplace_back(s);
i = nR + 1;
pair<ll, ll> p = {i, -R};
auto it = lower_bound(all(V), p);
d = it - V.begin();
}
for (; i <= R; ++i) {
ret.emplace_back(P[i]);
}
vector<ll> U = ret;
reverse(all(U));
if (U < ret) {
swap(U, ret);
}
if (ret.empty()) return -1; // 多分ない
// 上書きしてしまうことがある
if (G[ret[0]].empty()) {
G[ret[0]] = ret;
} else {
for (ll j = 1; j < (ll)ret.size(); ++j) {
G[ret[0]].emplace_back(ret[j]);
}
}
return ret[0];
}
// 再帰的に復元
void restore_ans(ll s, vector<ll> &ans) {
rep(i, (ll)G[s].size()) {
ll g = G[s][i];
if (i == 0 || G[g].empty()) {
ans.emplace_back(g);
} else {
restore_ans(g, ans);
}
}
}
int main() {
cincout();
cin >> N >> M;
rep(i, N) {
cin >> P[i];
--P[i];
}
V.emplace_back(0, -(N - 1));
rep(i, M) {
ll a, b;
cin >> a >> b;
--a, --b;
// (1,3), (1,2)が優先
V.emplace_back(a, -b);
}
sort(all(V));
ll start = dfs(0);
vector<ll> ans;
restore_ans(start, ans);
rep(i, (ll)ans.size()) {
cout << ans[i] + 1 << " \n"[i == (ll)ans.size() - 1];
}
}