第3ラウンド#1.

更新後初めての練習でした.
まず時間を3時間に延長し,問題数を4個に減らしたため,難易度が向上した.
もう3人ですが、個人差がちょっと大きいので、次は1~金3くらいの銀を出します.

わたしは3位になった
B号は問題を読むのに時間がかかり、理解しても分からないのでスキップしました.
D号の提出を間違えたのは、いったい何か別の方法があるのだろうか.そしてMJHに聞いたら
もとは練習する時直したコードCtrl+Cはよく押していませんこれ以上提出すればいいです.(私の片手で責任を負います.指ですね)
コード質問メッセージかDiscord DMでお願いします~!!!

A.部分数列の和2（1208）

+)無理でも解ける

物語のあらすじ

すべての要素の和を所与の値SSSとする部分数列の個数を探し出す.
「部分数列」の定義が混同される可能性があります.
一般に、部分配列とは、arr[1...n]がある場合、arr[i...j](1≦i≦j≦n)のように連続する部分をいう.
逆に、一部の数列は連続する必要はありません.円配列の一部の要素を消去して作成した新しい配列と考えられます.

方法

部分配列であればNNNは小さく,累加配列でも無邪気に実施できる.
しかし、このような状況は違います.
まず、一部の数列で任意の要素が削除されているかどうかを確認します.
例外はない.
しかし2 n 2^n 2 nの計算は絶対に不合理である.
それまで解けていた4つのゼロと整数のアイデアを利用しましょう.
思い出したら!もしやったら、帰って解いてみることをお勧めします.
したがって、一部の数列を前のN2rfloorN2後ろのNNNNNN2rfloornN2N2NNNN2NNN2NNN2NN
さて、先の数列では、任意の部分の数列を捉え、これをLiL iLiと呼ぶ.
同様に、後にRir iRiも作成します.
では,各要素LiL iLIについて,Rj=S,LiR j=S−L iRj=S,LIがどれだけ存在するかを計算すると,答えが得られる.
しかしこのi,ji,ji,jを全てマッチングするとTLEが現れる.
だから.バイナリ検索で素早く見つけましょう!
2n/2lfolor n/2rfloor}2n/2および後のn/n/2lfolor n/2rfloor\n\n\n\n\n\n\nn\2nnnn\nnn\nnnnnnnnnnnnnnnnnnnnnnnn
時間複雑度O×log⁡22N−⌊N/2⌋)=O(2N/2×(N−⌊N/2⌋))=O(N⋅2N/2)O(2^{\lfloor N/2\rfloor}\times\log_22^{N-\lfloor N/2\rfloor}) = O(2^{N/2}\times (N-\lfloor N/2\rfloor)) = O(N\cdot 2^{N/2})O(2⌊N/2⌋×log2​2N−⌊N/2⌋)=O(2N/2×(N⌊N⌊)=O(N⌊N/2).NNを挿入すると、O(20220)=O(107)O(20cdot 2^)=O(20cdot 10^6)=O(10^7)O(20\220)=O(20\106)=O(107)となり、時間内に問題を解決できます.

コード#コード#

int n, s, arr[40], L[1<<20], R[1<<20];

void pre(int b, int i, int s, int e, int* sum) {
    if (s == e) return;
    *(sum+( b|(1<<i) )) = *(sum+ b ) + arr[s];
    
    pre(b|(1<<i), i+1, s+1, e, sum);
    pre(b,        i+1, s+1, e, sum);
}

void solve() {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) cin >> arr[i];
    pre(0, 0, 0, n/2, L); pre(0, 0, n/2, n, R);

    sort(R, R+(1<<(n-n/2)));

    long long ans = 0;
    for (int i = 0; i < 1<<(n/2); ++i) {
        ans += 
        upper_bound(R, R+(1<<(n-n/2)), s-L[i])
        -lower_bound(R, R+(1<<(n-n/2)), s-L[i]);
    }
    cout << ans - (s == 0);
}

D.ソート(17432)

物語のあらすじ

Bubble Sotの過程の中で発生するswapの回数を少し求めます.
Bubble Sotの順番に少し注意しましょう

方法

これは観察が必要な問題です.
各要素をaia iaiと呼び、aj(1≦jこのとき,質問の答えはΣGi=msumG i=mΣGi=mのある数列である.
a=[1,2,3,4,5]a=[1,2,3,4,5]a=[1,2,3,4,5]
iii12345aia_iai​12345GiG_iGi​00000
∴∑Gi=0\therefore\sum G_i=0∴∑Gi​=0
a=[5,4,3,2,1]a=[5,4,3,2,1]a=[5,4,3,2,1]
iii12345aia_iai​54321GiG_iGi​01234
∴∑Gi=10\therefore\sum G_i=10∴∑Gi​=10
この二つの状況を観察すると、少し分かる.
1、i≦nは1 G ileq n−1 G i≦n 1である.
2.これにより、GnG nGnの値を調整し、n21 n-1 n哳1の問題に縮小することができる.これは真法に似た原理である.縮小後も大小関係の属性のみを考慮すると,集団は存在しないことが分かる.
では、あるm◈m≦n(n◈1)2 ms.t.\;mleqfrac{n(n-1)}m.t.m≦2 n(n1)、m=0b 1+1b 2+(n1)cnb 1+1cdots(n-1)(m=0⋅b 1+1ͻb 2+(nέ1)89 bn(ただし、bi={0,1})b i={0,1})は、bi={0,1}を満たすbib ibiが常に見つかることを証明すれば十分である.
しかし、それを証明するものを先に次の証明書目録に押しておきます.

コード#コード#

void solve() {
    int n, m; cin >> n >> m;
    bool chk[n]; memset(cnt, 0, n);
    stack<int> s;
    for (int i = n-1; i >= 0; --i) {
        if (m >= i) {
            chk[n-i] = true;
            m -= i;
            s.push(n-i);
        }
    }
    for (int i = n; i >= 1; --i) if (!chk[i]) {
        s.push(i);
    }
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << '\n';
}

アテステーション

数学的帰納法を真剣に使うと可読性が低下します.
逆に,以下の自明式が同じ結果を導く過程を見てみよう.
            n(n−1)2=(n−1)⋯+3+2+1n(n−1)2−1=(n−1)⋯+3+2+0n(n−1)2−2=(n−1)⋯+3+0+1⋮n(n−1)2−(n−1)=(n−2)+⋯+1              (n−1)(n−2)2=(n−2)+⋯+1⋮2⋅12=1\;\;\;\;\;\;\frac{n(n-1)}{2}=(n-1)\cdots +3+2+1\\\frac{n(n-1)}{2}-1=(n-1)\cdots +3+2+0\\\frac{n(n-1)}{2}-2=(n-1)\cdots +3+0+1\\\vdots\\\frac{n(n-1)}{2}-(n-1)=(n-2)+\cdots +1\\\;\;\;\;\;\;\;\frac{(n-1)(n-2)}{2}=(n-2)+\cdots +1\\\vdots\\\frac{2\cdot1}{2}=12n(n−1)​=(n−1)⋯+3+2+12n(n−1)​−1=(n−1)⋯+3+2+02n(n−1)​−2=(n−1)⋯+3+0+1⋮2n(n−1)​−(n−1)=(n−2)+⋯+12(n−1)(n−2)​=(n−2)+⋯+1⋮22⋅1​=1