競技プログラミング練習記 No.61【ABC102練習】

初回 -> はじめに

ABC102を解きました。
3完です！

問題	時間	アルゴリズム	実行時間
A	1min	-	8ms
B	1min	-	6ms
C	82min	二分探索	37ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

最小要素と最大要素はstd::min_element()とstd::max_element()を使えば求まります。
書くのが少し手間なので、計算量的に間に合う場合はsortで十分です。

C問題の実行速度が提出時に C++ (GCC 9.2.1) で解いた人の中で1番でした。嬉しい。

A - Multiple of 2 and N

  int n;
  cin >> n;
  cout << (n % 2 == 0 ? n : n * 2);

「2 と N のどちらでも割り切れる最小の正整数」は、Nが偶数の時はN自身で、Nが奇数の時は2 * N ですね。
制約の範囲が大きいのでオーバーフローに注意です。（今回は大丈夫です。）

B - Maximum Difference

  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  cout << a.back() - a[0];

数列内の異なる2要素の差の絶対値を最大化する問題ですね。
数列内の最小要素と最大要素の差が答えになります。
最小要素と最大要素はstd::min_element()とstd::max_element()を使えば求まります。
今回は計算量的に間に合って書くのが手間だったのでsortしました。

C - Linear Approximation

  ll n;
  cin >> n;
  vector<ll> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> a[i];
    a[i] -= (i + 1);
  }

  auto f = [&](ll b)
  {
    ll ret = 0;
    for(int i = 0; i < n; ++i)
    {
      ret += abs(a[i] - b);
    }
    return ret; 
  };

  ll le = -1000200001LL, re = 1000200001LL;
  ll lv = f(le);
  ll rv = f(re);
  while(re - le > 1)
  {
    ll mid = (le + re) / 2LL;
    ll mv = f(mid);
    if (lv < rv)
    {
      re = mid;
      rv = mv;
    }
    else
    {
      le = mid;
      lv = mv;
    }
  }
  cout << min(rv, lv);

$A_i - i$を先に計算しておけば、 $b$ だけについて考えればいいですね。

$b$ についての二分探索で解きました。想定解法は中央値を使う方法です。
実行速度だけは速くて、提出時に C++ (GCC 9.2.1) で解いた人の中で1番でした。嬉しい。
二分探索の場合は範囲に注意で、$[-10^9 - 2 * 10^5\ ,\ \ \ 10^9 + 2 * 10^5]$ になります。

以下、解いたときの思考回路です。
これは平均値が答えだ(ﾄﾞﾔｧ
からのWA安定でした。
これは中央値が答えになります。
考察中に中央値も思い浮かんだのですが、謎の理由で却下していました。猛省せねば。

理想なら中央値を思い浮かんだ時点で実装しているべきですが、中央値からどんどん離れていきます。

問題名がLinear Approximation(線形近似)なのでグラフの極値を求める問題かなと思いました。
ちょうど解空間が下に凸な二次関数の形をしています。
ニュートン法？再急降下法？と思いましたが微分がよくわからず、、、
そんな重い実装はないはず、という思考で二分探索を思いつきました。

以上です。ありがとうございました。