結果

問題 No.3320 yiwiwiy
コンテスト
ユーザー みうね
提出日時 2025-10-06 10:14:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,109 bytes
コンパイル時間 1,451 ms
コンパイル使用メモリ 127,108 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-31 18:53:30
合計ジャッジ時間 6,839 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12 WA * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 128ビット整数型を 'int128' として扱う
using int128 = __int128_t;

// int128を出力するためのヘルパー関数
std::ostream& operator<<(std::ostream& os, int128 val) {
    if (val < 0) {
        os << "-";
        val = -val;
    }
    if (val == 0) {
        return os << "0";
    }
    std::string s = "";
    while (val > 0) {
        s += (val % 10) + '0';
        val /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

// タイプQにおけるPの値の、iとwに依存する部分を計算する関数
int128 calc_p_iw_part(long long IL, long long I_rem, long long IC, long long WC, long long W_rem, char type) {
    // 不正な分割でないかチェック
    if (IL < 0 || IL > I_rem) {
        return -1;
    }
    long long IR = I_rem - IL;

    // 1^2 + ... + N^2 などの和の計算。オーバーフロー防止のため int128 を使用
    int128 wc_128 = WC;
    int128 sum_j = wc_128 * (wc_128 + 1) / 2;
    int128 sum_j_sq = wc_128 * (wc_128 + 1) * (2 * wc_128 + 1) / 6;

    // Cブロック内のwが作るPへの貢献度
    int128 sum_term = wc_128 * IL * (IR + IC) + (IR + IC - IL) * sum_j - sum_j_sq;

    // 残りのw (W_rem) が作るPへの貢献度
    int128 w_rem_term = 0;
    if (type == 'a') { // y..i..[w..C]..i..y の構造
        w_rem_term = (int128)W_rem * IL * (IC + IR);
    } else { // y..i..[C..w]..i..y の構造
        w_rem_term = (int128)W_rem * (IL + IC) * IR;
    }

    return w_rem_term + sum_term;
}

// 各テストケースを解くメインの関数
void solve() {
    long long Y, I, W;
    long long A, B;
    std::cin >> Y >> I >> W >> A >> B;

    // --- 最適解を記録するための変数 ---
    int128 max_score = -1;
    std::string best_str = "";

    // --- 戦略1: タイプP (P-重視) ---
    {
        long long YL_p = Y / 2;
        long long YR_p = Y - YL_p;
        long long IL_p = I / 2;
        long long IR_p = I - IL_p;

        int128 p_val = (int128)W * YL_p * YR_p * IL_p * IR_p;
        int128 current_score = (int128)A * p_val;

        if (current_score > max_score) {
            max_score = current_score;
            best_str = std::string(YL_p, 'y') + std::string(IL_p, 'i') +
                       std::string(W, 'w') +
                       std::string(IR_p, 'i') + std::string(YR_p, 'y');
        }
    }

    // --- 戦略2: タイプQ (Q-重視) ---
    long long k = 0;
    if (I >= 2 && W >= 1) {
        k = std::min(I - 2, W - 1);
    }

    if (k > 0) {
        long long IC = k + 2;
        long long WC = k + 1;
        long long I_rem = I - IC;
        long long W_rem = W - WC;
        long long YL_q = Y / 2;
        long long YR_q = Y - YL_q;
        int128 p_y_part = (int128)YL_q * YR_q;

        std::string c_block = "i";
        for (int i = 0; i < k + 1; ++i) c_block += "wi";

        // --- 候補 (a): y..i..[w..C]..i..y ---
        {
            int128 b_coeff = (int128)W_rem * (I_rem + IC) + (int128)WC * (I_rem + IC - WC - 1);
            int128 a_coeff_abs = W;
            long double axis = (long double)b_coeff / (2.0L * a_coeff_abs);
            long long IL_center = round(axis);

            int128 p_iw_max = -1;
            long long IL_best = -1;
            
            // 軸周辺の整数を試し、浮動小数点誤差をなくす
            for (long long il = std::max(0LL, IL_center - 5); il <= std::min(I_rem, IL_center + 5); ++il) {
                 int128 current_p_iw = calc_p_iw_part(il, I_rem, IC, WC, W_rem, 'a');
                 if(current_p_iw > p_iw_max){
                     p_iw_max = current_p_iw;
                     IL_best = il;
                 }
            }
            if(IL_best != -1){
                int128 p_val = p_y_part * p_iw_max;
                int128 current_score = (int128)A * p_val + (int128)B * k;
                if(current_score > max_score){
                    max_score = current_score;
                    long long IR_best = I_rem - IL_best;
                    best_str = std::string(YL_q, 'y') + std::string(IL_best, 'i') + std::string(W_rem, 'w') + c_block + std::string(IR_best, 'i') + std::string(YR_q, 'y');
                }
            }
        }

        // --- 候補 (b): y..i..[C..w]..i..y ---
        {
            int128 b_coeff = (int128)W_rem * (I_rem - IC) + (int128)WC * (I_rem + IC - WC - 1);
            int128 a_coeff_abs = W;
            long double axis = (long double)b_coeff / (2.0L * a_coeff_abs);
            long long IL_center = round(axis);

            int128 p_iw_max = -1;
            long long IL_best = -1;

            for (long long il = std::max(0LL, IL_center - 5); il <= std::min(I_rem, IL_center + 5); ++il) {
                 int128 current_p_iw = calc_p_iw_part(il, I_rem, IC, WC, W_rem, 'b');
                 if(current_p_iw > p_iw_max){
                     p_iw_max = current_p_iw;
                     IL_best = il;
                 }
            }
             if(IL_best != -1){
                int128 p_val = p_y_part * p_iw_max;
                int128 current_score = (int128)A * p_val + (int128)B * k;
                if(current_score > max_score){
                    max_score = current_score;
                    long long IR_best = I_rem - IL_best;
                    best_str = std::string(YL_q, 'y') + std::string(IL_best, 'i') + c_block + std::string(W_rem, 'w') + std::string(IR_best, 'i') + std::string(YR_q, 'y');
                }
            }
        }
    }
    
    // Y,I,W>0なのに解が見つからない場合(通常は起こらない)、デフォルト文字列を生成
    if (max_score == -1 && (Y > 0 || I > 0 || W > 0)) {
       best_str = std::string(Y, 'y') + std::string(I, 'i') + std::string(W, 'w');
    }

    std::cout << best_str << std::endl;
}

int main() {
    // 高速化のためのおまじない
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
0