結果

問題 No.2746 Bicolor Pyramid
コンテスト
ユーザー Naru820
提出日時 2025-11-19 15:54:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,612 bytes
コンパイル時間 810 ms
コンパイル使用メモリ 93,160 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-19 17:11:33
合計ジャッジ時間 2,910 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>

using namespace std;

// 64ビット整数型を使用
typedef long long ll;

// k段のピラミッドが作れるか判定する関数
// r: 赤ブロックの残り, b: 青ブロックの残り
bool can_build(ll k, ll r, ll b) {
    // k段目から1段目まで逆順にシミュレーション
    for (ll i = k; i >= 1; --i) {
        ll needed = i * i; // i段目に必要なブロック数

        // 赤も青も足りない場合は作成不可
        if (r < needed && b < needed) {
            return false;
        }

        // 貪欲法: 残りが多い方の色を使う
        // これにより、バランス良く消費し、後半（小さい段）での選択肢を残す
        if (r >= b) {
            r -= needed;
        } else {
            b -= needed;
        }
    }
    return true;
}

int main() {
    // 入力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll R, B;
    if (!(cin >> R >> B)) return 0;

    // 二分探索の範囲
    // 下限 0, 上限 2,000,000
    // (2*10^6)^3 / 3 は 2*10^18 を超えるため、これ以上の段数は物理的に作れない
    ll low = 0, high = 2000000;
    ll ans = 0;

    while (low <= high) {
        ll mid = low + (high - low) / 2;

        if (can_build(mid, R, B)) {
            // mid段作れるなら、もっと高くできるか試す
            ans = mid;
            low = mid + 1;
        } else {
            // 作れないなら、高さを下げる
            high = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}
0