おじさんの競プロ記録

自分の力で解答できた問題を振り返り、理解を深めたいです。

AtCoder Regular Contest 109 B - log

問題

問題文へ

長さ1からnまでのn種類の丸太が1本ずつほしいです。長さ1からn+1までn+1種類の丸太が1本ずつ販売されています。

買った丸太を切断することにコストはかかりません。丸太の値段は1本1円です。必要な最小の金額を求めてください。

制約

  • {1 \leqq n \leqq 10^18}

考えたこと

切断にコストがかからないので長さn+1を買い、たくさんの丸太にします。長さ1から作れば最適です。

n+1が2なら1本、3なら2本…10なら4本と書いて考えました。作れる最大の本数をxとして、x*(x+1)/2=n+1としてみました。n+1は与えられるので二次方程式でしょうか。それを解いて正しい答えか判定するプログラムを考える事は私には時間がかかりそうです。xに1から当てはめて試してみるプログラムならば、すぐに書けそうです。制約は大きいですが、試す回数は少なくともnの半分より小さくなるでしょうから間に合うと考えました。変数名がcountなのはカウントアップするイメージからです。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll n;
  cin >> n;

  ll target = n + 1;
  ll num = 1;
  ll count = 1;
  while (count * (count + 1) / 2 <= target) {
    count++;
  }
  --count;

  ll ans = n + 1 - count;

  cout << ans << endl;
  
  return 0;
}

解説を読んで

二分探索は思い浮かんでいませんでした。制限時間に間に合うか考えただけで、アルゴリズムを適用する思考が足りないようです。

1+...+k=k(1+k)/2も、プログラマの数学で読んでいたのに思い至らなかったのが悔やまれます。x*(x+1)/2はどんな式なら良いだろうと試行錯誤しました。