ブログ記事に書くと定着度が高まることがわかったので，これからは解いた問題を積極的に記事にしていこうと思う．

問題概要

$ N $要素からなる数列$ a = \{ a_1, a_2, \cdots, a_n \} $，$ b = \{ b_1, b_2, \cdots, b_n \} $に対し，以下の操作を行う．

ある正の整数$ k $を選び，数列$ a $の要素$ a_i $を，$ a_i \% k $に置き換える．置き換えはすべての要素に対して行う必要はなく，置き換えを行う要素と行わない要素が混在してもよい．この操作のコストは$ 2^{k} $である．

この操作を繰り返すことで，$ a$を$ b$にする．

この操作を繰り返し，すべての頂点から石を取り除くことができるかどうかを求める．できる場合，コストの和の最小値を求める．

ただし$ 1 \leq N \leq 50 $，$ 0 \leq a_i, b_i \leq 50 $．

解法概要

部分問題の作り方

まず，

$ a_i \% k $への置き換えは，必ずしもすべての要素に対して行う必要はない

ので，$ a_i$を$ b_i$にすることができるのか$ i$ごとにバラバラに考えてもよいことがわかる．$ a_i$を$ b_i$にするために使わなかった$ k$を$ a_j$を$ b_j$にするために使っても，$ a_i$を$ b_i$にする操作の可否には影響しない．

また，

$ b \leq 50 $より，50以上の整数を使う必要はない
同じ正の整数$ k $で何度も剰余を取っても意味がない

このことから，使う$ k $を集合として管理したくなるが， $ 2^{50} $ 通りの集合でコストを求めたらもちろんTLE．しかし，コストについて考えてみると

$ 2^{k} + 2^{k-1} + \cdots + 2^{1} = 2^{k+1} - 2 \lt 2^{k+1} $より，(たとえ操作回数が増えようとも) より大きな$ k $を使わずに済む場合には使うべきではない

ということがわかるので，はじめに1以上49以下のすべての正の整数からなる集合$ S $を用意して，大きな要素$ k $から順に「本当に必要な$ k $なのかどうか」をチェックし，いらない$ k $は捨てていくという方法が取れそうだと考えられる．

部分問題の解き方

次に「本当に必要な$ k $なのかどうかをチェックする」方法について考察する．$ k $が必要であるということは，

1以上$ n $以下のすべての$ i $について$ S $を$ b_i $にすること(以降「目標」と呼ぶ) ができる集合$ S $について，$ k $が$ S $から取り去られたときに，$ S $は目標を達成できなくなる．

というように言い換えられる．

したがって，50以下の整数$ m $と集合$ S $の要素$ k $について，$ m $から$ m \% k $へ辺を張った有向グラフを用意し，ワーシャルフロイド法などで$ a_i$から$ b_i$に到達可能かどうかを確かめればよい．$ k $が$ S $から取り去られたときに到達不可能になってしまうような$ a_i$，$ b_i$が1組でも存在する場合には，$ k $は必要ということになる．

ちなみに今回は最小のコストを求めるのであって操作回数を最小化したいわけではないので，有向グラフの辺の重みは1などの定数でよい．

ソースコード

#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;

typedef long long ll;

ll wf[51][51];
int n;
int a[50], b[50];

void floyd_warshall(set<int> st){
    fill((ll *)wf[0], (ll *)wf[51], LLONG_MAX);

    for(int k: st){
        repp(n, 51){
            wf[n][n%k] = 1LL;
        }
    }

    repp(k, 51){
        repp(i, 51){
            repp(j, 51){
                wf[i][j] = min(wf[i][j], (wf[i][k]|wf[k][j]));
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    rep(n) cin >> a[i];
    rep(n) cin >> b[i];

    int same = 1, max_a = -1, max_b = -1;
    rep(n){
        if(a[i] != b[i]) same = 0;
        max_a = max(max_a, a[i]);
        max_b = max(max_b, b[i]);
    }

    /* 操作の必要なし */
    if(same){
        cout << 0 << endl;
        return 0;
    }
    /* bの要素がすべて0 (=1で剰余とっておしまい) */
    if(max_b == 0){
        cout << 2 << endl;
        return 0;
    }

    set<int> st;
    reppp(i, 1, 51) st.insert(i);
    
    int use = 0;
    ll ans = 0LL;
    floyd_warshall(st);
    rep(n){
        if(wf[a[i]][b[i]] == LLONG_MAX){
            use = 1;
            break;
        }
    }
    if(use){
        cout << -1 << endl;
        return 0;
    }

    for(int l=50;l>=1;l--){
        int use = 0;
        st.erase(l);
        floyd_warshall(st);
        rep(n){
            if(wf[a[i]][b[i]] == LLONG_MAX){
                use = 1;
                break;
            }
        }
        if(use){
            ans |= 1LL << l;
            st.insert(l);
        }
    }

    cout << (ans?ans:-1) << endl;
}

感想

本番ではグラフ作ってどうこう以前に，コストに対する考察が足りていなかった．

NoiminのNoise

AtCoder Grand Contest 022 C - Remainder Game

問題概要

解法概要

部分問題の作り方

部分問題の解き方

ソースコード

感想