結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <bitset>

using namespace std;

typedef long long ll;

// 異なる平方数の和で作れない数は最大でも128付近であるため、
// 小さい範囲の判定用に定数を用意
const int MAX_IMPOSSIBLE = 150;

// k段のピラミッドに必要なブロック総数
// オーバーフローを防ぐため __int128 を使用するか、制限内で計算する
ll get_total_blocks(ll k) {
    // k(k+1)(2k+1)/6
    // k <= 2*10^6 なので、計算結果は高々 ~2.6*10^18 程度。long longに収まる。
    // 計算途中のオーバーフローに注意
    unsigned __int128 K = k;
    unsigned __int128 total = K * (K + 1) * (2 * K + 1) / 6;
    if (total > 4000000000000000000ULL) return 4000000000000000000LL; // 飽和
    return (ll)total;
}

// 小さいkに対する厳密なDP判定
// bitsetを使って到達可能な和を列挙する
bool check_small(ll k, ll R, ll B) {
    ll total = get_total_blocks(k);
    if (total > R + B) return false;

    // 必要な赤ブロックの数の候補範囲: [max(0, Total - B), min(Total, R)]
    ll min_r = max(0LL, total - B);
    ll max_r = min(total, R);
    
    if (min_r > max_r) return false;

    // DPで到達可能な和を計算
    // k=20のとき total=2870 なので bitset<3000> で十分
    bitset<3000> dp;
    dp[0] = 1;
    
    for (int i = 1; i <= k; ++i) {
        ll sq = i * i;
        dp |= (dp << sq);
    }

    // 範囲内にtrueがあるか探す
    // min_r から max_r まで
    for (ll r = min_r; r <= max_r; ++r) {
        if (r < 3000 && dp[r]) return true;
    }
    
    return false;
}

// 判定関数
bool check(ll k, ll R, ll B) {
    // kが小さい場合はDPで厳密に解く
    if (k <= 20) {
        return check_small(k, R, B);
    }

    ll total = get_total_blocks(k);
    if (total > R + B) return false;

    // kが大きい場合
    // 到達不可能な数は小さい値（最大128）に限られることが知られている。
    // 範囲 [min_r, max_r] が 128 より大きい値を含んでいれば、必ず到達可能。
    // もし範囲全体が 128 以下なら、それは「小さい数」のチェックが必要だが、
    // k > 20 で Total は数千になるため、
    // R, B が極端に小さくない限り範囲は128を超える。
    
    ll min_r = max(0LL, total - B);
    ll max_r = min(total, R);

    if (min_r > max_r) return false;

    // 範囲の上限が128を超えていれば、129以上の数はすべて作れる（k>20なら十分な1,4,9...があるため）
    // 正確には「異なる平方数の和で表せない最大整数」は128。
    if (max_r > 128) return true;

    // ここに来るのは R, B の片方が極端に小さく、必要なブロック数が128以下に収まる場合。
    // k > 20 で Total > 2000 なのに ターゲットが <= 128 ということは
    // ほぼすべてのブロックをもう一方の色にする必要がある。
    // 小さい数は k=20 までの平方数で作れるかどうかのチェックで十分（1..20の2乗があれば128以下は網羅できる）
    
    // 念のため事前に計算しておいた「作れない数リスト」でチェック
    // 128以下の作れない数: 
    // 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, ... (OEIS A001422)
    // 毎回DPするのは重くないので、ここでも部分的にDPを回して確認する
    
    bitset<150> dp;
    dp[0] = 1;
    // 128を作るのに必要なのは高々12^2=144まで。k>20なので十分足りる
    for (int i = 1; i <= 20; ++i) { 
        int sq = i * i;
        if (sq > 130) break;
        dp |= (dp << sq);
    }

    for (ll r = min_r; r <= max_r; ++r) {
        if (dp[r]) return true;
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll R, B;
    if (cin >> R >> B) {
        ll low = 0, high = 2000000; // 2*10^6 程度が上限
        ll ans = 0;

        while (low <= high) {
            ll mid = low + (high - low) / 2;
            if (check(mid, R, B)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
0