TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

06 /
19
2022
 

【ABC246-Dの反省】「とある部分を境目として」N以上になっているときは二分探索が使えそう

2022年6月19日に開催されたAtCoder Beginner Contest 246(以下、ABC246) にバーチャル参加しました。

AtCoder Beginner Contest 246 – AtCoder
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

結果は以下の通りでした。

良かった点

良くなかった点

今回の反省では、解けなかったD問題を解説ACをします。

目次

  1. D問題について
  2. hamayanhamayanさんの解説で復習
  3. この問題は「競プロ的なアプローチを含んだ問題」
  4. 今回も実装は自力で

D問題について

問題等は以下のリンクをご確認ください。

D – 2-variable Function
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

hamayanhamayanさんの解説で復習

今回はhamayanhamayanさんの解説で復習しました。

hamayanhamayanさんの解説記事もよく読んでいます。

書いていただいて、ありがとうございます。

解説記事はこちら

この問題は「競プロ的なアプローチを含んだ問題」

このABC246-D問題を考えている最中は目立つ数式に気をとられ、数学で何かしらするのがポイントなのだろうかと考えていました。

しかし、hamayanhamayanさんの解説でまず記載されているのが、次の文章です。

『なかなか難しいというか、競プロ的なアプローチを含んだ問題。』。

全くマトが外れていたようです。

では「競プロ的なアプローチ」とはどのようなアプローチなのでしょうか。

hamayanhamayanさんの解説では、次のような手順を示してくれています。

1.候補を全列挙できるか否かを考える

2.片方を固定して、もう一方を効率化できないかを考える

3.とある部分を境目としてN以上になっているので、二分探索が使えそうと思いつく

この思考の手順は他の問題でも使えそうです。

確かに、公式の解説や他の方の解説でも同じような話を聞いた記憶があります。

記憶にあるだけではなく、このあたりの感覚はなんとか使えるように、コンテスト中に思いつくようにせなあきません。

実装は自力で

今回の反省でACできたコードは以下のようになりました。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
const ll INF = 1LL << 62;
// const int INF = 1001001001;

ll f(ll a, ll b) {
  return a * a * a + a * a * b + a * b * b + b * b * b;
}

int main() {
  ll N;
  cin >> N;

  ll ans = INF;
  for(ll i = 0; i <= 1000000; ++i) {
    ll wa = -1;
    ll ac = 1000000;
    while (wa + 1 != ac) {
      ll md = (wa + ac) / 2;
      if (N <= f(i, md)) {
        ac = md;
      } else {
        wa = md;
      }
    }
    ans = min(ans, f(i, ac));
  }

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