小課題 1

全部でテストケースの数は \(4\) 通りしかありません。場合分けをして解くことができます。

小課題 2, 3

数列の長さ \(N\) に対し、マージ方法の通り数は \((N-1)!\) 通りあります。小課題 2, 3 の制約において、これを全て探索する \(O(N(N-1)!)\) の解法は十分高速です。

小課題 4, 5, 6, 7

区間 dp を考えます。\(dp[l][r][a] := \{A[l\ldots r)\) に対するマージ操作で \(a\) を作るときの最大の OR 操作の回数 (作れないなら -inf) \(\} \) とし、区間 dp を行うことができます。

この dp は状態数が \(O(N^2 \max(A))\) で、遷移が \(O(N\max(A))\) なので合計での計算量は \(O(N^3\max(A)^2)\) となります。

表面上の計算量は \(5\) 乗ですが、実際には \(l < r\) であったり、\(dp[l][r][a] = \) -inf の場合に遷移をする必要がなかったり、遷移の大きさはより正確には \(a(r-l)\) 回程度であることから、実際には小課題 7、\(N \leq 128\) 程度まではこの解法で AC することが可能だと思います（嘘みたいな遷移の枝刈りをすると小課題 8 も通るかもしれません）。

小課題 8, 9, 10

適切な操作の順番について考察してみます。

AND 操作を行った時にマージした \(2\) つの要素を \(a,b\) とします。ここで、例えば \(a\) が生成されていた過程で一回でも OR 操作が使われていたとしましょう。

このとき、\(a\) で使われていた OR 操作と今回行った AND 操作を入れ替えても、もともとの操作列が条件を満たしていたとすれば、最終的な \(A_0\) が \(0\) のままになることが示せます。

これは、「もともと \(1\) になっていた bit が \(0\) になる」ということが起こりえないことからわかります。もともとの操作でマージ後のある bit が \(1\) になっていた場合、\(a,b\) の同じ位置の bit は両方とも \(1\) になっていたはずです。ここで、この入れ替えによって片方が \(0\) になったとしても、最終的に行うのは OR 操作であることから、入れ替え後のマージ後の当該 bit も \(1\) になることがわかります。

この swap argument を繰り返し適用することにより、最適な操作列は「全ての AND 操作は全ての OR 操作の後に行われる」という制約を満たすとしてよいことがわかります。

これにより、次のような dp を考えることができます： \(dp[r][a] := \{A[0\ldots r)\) に対するマージ操作で \(a\) を作るときの最大の OR 操作の回数 (作れないなら -inf) \(\} \)

この dp は、naive に行えば空間計算量 \(O(N\max(A))\)、遷移 \(O(\max(A))\) より、全体で \(O(N\max(A)^2)\) で解を求めることができます。とても定数倍が良い実装をすれば、小課題 11 も AC できるかもしれません（コンテスト中にこの解法で 66 点を獲得している人がいました）。

3 乗解法 (C++) :

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int M = 10;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
        A[i] = (1<<M)-1-A[i];
    }
    vector<vector<int>> dp(N+1,vector<int>((1<<M),30));
    dp[0][0] = 0;
    for(int i=0;i<N;i++){
        int now = (1<<M)-1;
        for(int j=i;j<N;j++){
            now &= A[j];
            for(int k=0;k<(1<<M);k++) dp[j+1][k|now] = min(dp[j+1][k|now],dp[i][k]+1);
        }
    }
    if(dp[N][(1<<M)-1] == 30) dp[N][(1<<M)-1] = N+1;
    cout<<N-dp[N][(1<<M)-1]<<endl;
}

小課題 11

先ほどの dp を改善することを考えます。まずは、先ほどのコードのこの遷移についてです：

        int now = (1<<M)-1;
        for(int j=i;j<N;j++){
            now &= A[j];
            for(int k=0;k<(1<<M);k++) dp[j+1][k|now] = min(dp[j+1][k|now],dp[i][k]+1);
        }

この遷移について、now の値は高々 \(\log(\max(A))+1\) 種類しかとりません。よって、遷移先は \(\log(\max(A))+1\) 種類の区間として表現することができます。imos 法的に dp の更新を行うことによって、\(O(N\max(A))\) 通りの各状態からの遷移を \(O(\log(\max(A)))\) 時間で行うことができます。

合計での計算量は \(O(N\max(A)\log(\max(A)))\) となります。定数倍が良ければ、小課題 12 にも通ると思います。

小課題 12

先ほどの遷移のコードの遷移を、\(i\) の値ごとに \(O(N+\max(A))\) 程度で計算することができれば、計算量から log を落とすことができそうです。

高速ゼータ変換の考え方を用います。now の値は \(\mathrm{AND}(A_i,A_{i+1} \ldots ,A_{j})\) を表しており、最終的な遷移先は \(A[0\ldots i-1]\) までで作られた要素を \(k\) として \(k|\mathrm{now}\) と表すことができます。ここで、\(j\) の値を増やしたときに、\(now\) の値は bit ごとに広義単調増加になります。

元ネタです：https://www.youtube.com/watch?v=6Io5B6_j7K4

13 個の subtask を設定しようというのはここからです。