CSA Round #85 Strange Transformation

問題概要

CS Academy
二つの整数と個の数字が与えられる。以下の二つの操作をそれぞ れ回以上行い、条件を満たしつつをにしたい。
操作1.を倍する
操作2.をで割る(ただしが偶数の時に限る)

条件: からにする過程でが個の数字全てになる。

からにする過程を出力。不可能ならを出力。

制約

​​

個の数字について

​​
​​

考えたこと

サンプルをみると何がしたいのかよくわかる。
、、個の数字の集合をとするとの時出力は24,12,6,18,54,27,81のようになる。正しい操作と条件を満たしていればAは変化する過程でどのような値になってもいい。

まず、二つの操作ではを掛けるかで割るかの操作しかしないので、を素因数分解した際、以外の素因数とその指数は一致していなければならない。

このことは与えられる個の数字についても同じことが言える。

次に個の数字をどのような順番で経由していけばいいだろうか？もちろん、すべての組合せを考えるのは時間がかかりすぎる。例えば操作1のみが行える場合、は増加する一方であるから個の数字は昇順に並んでいることが望ましい。また、操作2のみが行える場合、は減少する一方であるかから個の数字は降順に並んでいることが望ましい。

では操作1,2が行える状況では個の数字はどのように並んでいればいいかを考えると、集合に含まれるすべての での指数については降順に、の指数については昇順にソートされていればいい。

こんな感じに

ソートされた結果のようになってしまう可能性があるのでソート後に正しくソートされているかのチェックを行なっている。

の並び順が決まったら、あとは,ソートされた,となっている配列を先頭から隣り合う要素を見てその指数の差を埋め合わせるようにを掛けるかで割るかの操作を行い値を出力していけば良い。

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

//素因数分解＜素因数、指数＞
map<int, int> prime_fac(int n) {
  map<int, int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

struct primeFac {
  //X_i,２の指数、３の指数
  int num = 0, two = 0, three = 0;
  bool operator<(primeFac x) const { return two >= x.two && three <= x.three; }
};
int n, a, b;
vector<primeFac> p(n + 2);

//２、３以外の素因数の積を計算
int cal(map<int, int> m, int x, int pos) {
  int res = x;
  for (auto &z : m) {
    if (z.first == 2) {
      int q = z.second;
      while (q--) res /= 2;
      p[pos].num = x;
      p[pos].two = z.second;
    } else if (z.first == 3) {
      int q = z.second;
      while (q--) res /= 3;
      p[pos].num = x;
      p[pos].three = z.second;
    }
  }
  return res;
}

signed main() {
  cin >> n >> a >> b;
  p.resize(n + 2);

  vector<int> x(n);
  rep(i, n) cin >> x[i];

  map<int, int> m;
  m = prime_fac(a);
  int res = cal(m, a, 0);
  m = prime_fac(b);

  if (res != cal(m, b, n + 1)) {
    cout << -1 << endl;
    return 0;
  }
  
  rep(i, n) {
    m = prime_fac(x[i]);
    if (res != cal(m, x[i], i + 1)) {
      cout << -1 << endl;
      return 0;
    }
  }
  
  sort(p.begin() + 1, p.end() - 1);
  
  rep(i, n + 1) {
    if (!(p[i] < p[i + 1])) {
      cout << -1 << endl;
      return 0;
    }
  }

  rep(i, n + 1) {
    cout << p[i].num << ' ';
    int l = p[i].num, r = p[i + 1].num;

    rep(j, abs(p[i + 1].two - p[i].two)) {
      l /= 2;
      if (l == r) break;
      cout << l << ' ';
    }
    rep(j, p[i + 1].three - p[i].three) {
      l *= 3;
      if (l == r) break;
      cout << l << ' ';
    }

    if (i == n) {
      cout << p[i + 1].num << endl;
    }
  }
  return 0;
}

感想

コードに関してはもっと綺麗に書けそう。こういう問題をすらっと解けるようになりたいね。