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

AtCoder Beginner Contest 246 – AtCoder

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

atcoder.jp

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

• 3完（A,B,C）0WA
• 順位: -位
• パフォーマンス: –
• レーティング: – (-)

良かった点

• 0WAだったこと。

良くなかった点

• D問題をACしたかった。

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

目次

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

D問題について

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

D – 2-variable Function

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

atcoder.jp

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;
}