C: Remainder Game - AtCoder Grand Contest 022

気づき

操作はkの降順だけ考えれば良い。 vに対して整数k1で操作したあとk2で操作したとする。 k1 <= k2を仮定する。 vをk1で割った余りv'は v' < k1 を満たす。 k1 <= k2より v'をk2で割った余りもv'である。よってk2による操作で値が変わらず、 k2の操作が無意味になる。

二分探索

0から 0b11111...1110 まで考えられる。 コストを2進数表記したとき、各桁は各操作をやったかどうかのフラグに対応する。 二分探索、あるいは辞書順最小を求める要領でこのコストを決める。 最初の桁、50による操作を考える。 50による操作が必要となるのは 49以下の全ての操作をすべて使っても、50の操作を使わなければ 数列{b}を作れない場合だけ。 つまり

0b01111...1110
  *

の操作をしたときに数列{b}を作れるかどうか判定すればいい。 ある値a[i]をb[i]に変更できるかを判定するには dp[x][y] := x番目の操作まで使って値yを作れるかどうか のようなDPを各(a[i], b[i])について解けばいい。 49,48,...,1の各操作についても同様に必要かどうかを決められる。

Kを操作に使う最大の整数とすると 実行時間はO(NK³)

int N, A[51], B[51];
bool dp[51][51];

int f(ll S, int id) {
    MEM(dp, 0);
    dp[50][A[id]] = 1;
    for (int i = 50; i >= 1; --i)rep(j, 51)if (dp[i][j]) {
        if (S >> i & 1) {
            dp[i - 1][j%i] = 1;
        }
        dp[i - 1][j] = 1;
    }
    RT dp[0][B[id]];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N;
    rep(i, N)cin >> A[i];
    rep(i, N)cin >> B[i];

    ll ans = 0, bb = (1ll << 51) - 1;
    for (int k = 50; k >= 1; --k) {
        bb >>= 1;
        ll S = ans | bb;
        int ok = 1;
        rep(i, N) {
            ok &= f(S, i);
            if (!ok)break;
        }
        if (!ok) ans |= 1ll << k;
    }
    if (ans == 2251799813685246ll)ans = -1;
    cout << ans << endl;
}