C - Remainder Game

https://atcoder.jp/contests/agc022/tasks/agc022_c

思考

・2のべき乗なので、なるべく小さいkを使いたい

・同じkを複数回使う事はない

kを50から順に見ていき何かしたい。が、よく分からない

とりあえずaiから作れる数を考えてみる

ai        bi

1   :     0

2   :     0 

3   :     0 1

4   :     0 1 

5   :     0 1 2

6   :     0 1 2

 ai  >=  bi * 2 + 1 の時にaiはbiに出来る事が分かった

よって、ok(a,b) :=上の式を満たすか判定とすると

kを50から順に見ていき、あるiでok(ai % m , b)を満たす最小のmがkに等しい時、kを選ぶ必要があり、満たさなければkは必要ない     

O(n ^ 3)

しかしこれでは不十分である

選んだkは自由に使えるので、ナップザックのように「現状aiから作れる数」を持ち

aiのみでは無く、それらに対しても判定をしなくてはいけない

従って、あるiであって、aiから作れる数に対してok( ..)を満たす最小のm達の内、

それらの中で最小のmがkに等しい時、kを選ばなくてはいけない

ということになった

計算量はO(n ^ 4)

Submission #4570541 - AtCoder Grand Contest 022

void solve() {
    cin >> n;
    na(a, n);
    na(b, n);
    rep(i, n) {
        if (a[i] < b[i])fin(-1);
        if (b[i] == 0)con;
        if (a[i] == b[i])con;
        if (a[i] < b[i] * 2 + 1)fin(-1);
    }

    bool can[55][55] = {};
    rep(i, n) {
        can[i][a[i]] = 1;
    }

    rer(v, 50) {
        bool need = 0;
        rep(i, n) {
            int mineed = inf;
            if (can[i][b[i]])con;
            rep(h, 51) {
                if (can[i][h] == 0)con;
                int m = 0;
                rep(_, 51) {
                    m++;
                    if (ok(h % m, b[i]))brk;
                }
                chmin(mineed, m);
            }
            if (mineed == v) {
                need = 1;
                brk;
            }
        }
        if (need) {
            rep(i, n) {
                rep(j, 51) {
                    if (can[i][j] == 0)con;
                    can[i][j % v] = 1;
                }
            }
            cou += 1ll << v;
        }
    }
    cout << cou << endl;
}