mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #312 (Div. 2) C. Amr and Chemistry

実装弱いマンなので実装に非常に苦しみました。

解法

やること自体はそれほど難しくなく,要するに「各iについてa[i]からたどり着くことのできる数を列挙し,それぞれの数に到達する最小手数を求める。すべてのa[i]からたどり着ける数について,その最小手数の合計を求める」という手順でやります。

で,僕はだいぶ実装に悩んだので今回は実装についても書いていきます。
まず,「各iについてa[i]からたどり着くことのできる数を列挙し,それぞれの数に到達する最小手数」はbfsで求めます。visにtrueかfalseしか考えてなかったので毎回memsetとか使ったら死ぬとか考えてましたがvisはもっと柔軟に使えてa[i]についてbfsしてるときはvis[x] = iみたいな感じで処理すればいちいち初期化しなくてokです(こんなことに気づかないのアホだ…)

で,あとはcntとかstepみたいな配列を用意すれば上でやりたい処理はきちんと出来ます。cnt[x]は各a[i]からxにたどり着く回数を示し,step[x]は各a[i]からxにたどり着く最小回数の合計です。

const int MAXN = 100100;
const int INF = 1e9;
int n;
int a[MAXN];
vector<pii> A[MAXN];
int vis[MAXN], step[MAXN], cnt[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int X;
        cin >> X;
        queue<pii> que;
        que.push(pii(X, 0));
        while (!que.empty()) {
            auto p = que.front(); que.pop();
            int x = p.first, y = p.second;
            if (x >= MAXN) continue;
            if (vis[x] == i+1) continue;
            cnt[x]++;
            step[x] += y;
            vis[x] = i+1;
            que.push(pii(x/2, y+1));
            que.push(pii(x*2, y+1));
        }
    }
    int ans = INF;
    for (int i = 0; i < MAXN; i++) {
        if (cnt[i] == n) ans = min(ans, step[i]);
    }
    cout << ans << endl;
    return 0;
}