結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー easy new
提出日時 2026-10-08 00:31:38
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,254 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,051 ms
コンパイル使用メモリ 352,840 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2026-10-08 00:31:46
合計ジャッジ時間 5,846 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int targetScore;
    cin >> targetScore;

    // minEvents[score] = minimum playback events needed for this score.
    const int INF = 1e9;
    vector<int> minEvents(targetScore + 1, INF);
    minEvents[0] = 0;

    for (int score = 1; score <= targetScore; score++) {
        for (int length = 1; length * length <= score; length++) {
            minEvents[score] = min(
                minEvents[score],
                length + minEvents[score - length * length]
            );
        }
    }

    string trace;
    int remainingScore = targetScore;
    char startPath = 'L';

    while (remainingScore > 0) {
        int shortestEndingL = -1;
        int longestValidLength = -1;

        for (int length = 1;
             length * length <= remainingScore;
             length++) {

            // Only consider blocks that preserve minimum total length.
            if (length + minEvents[remainingScore - length * length]
                != minEvents[remainingScore]) {
                continue;
            }

            // Lengths are visited in increasing order.
            longestValidLength = length;

            char endPath;
            if (length % 2 == 1) {
                endPath = startPath;
            } else {
                endPath = (startPath == 'L') ? 'G' : 'L';
            }

            // Keep the first, hence shortest, valid block ending in L.
            if (endPath == 'L' && shortestEndingL == -1) {
                shortestEndingL = length;
            }
        }

        int chosenLength;
        if (shortestEndingL != -1) {
            chosenLength = shortestEndingL;
        } else {
            chosenLength = longestValidLength;
        }

        // Append the chosen alternating block.
        char currentPath = startPath;
        for (int i = 0; i < chosenLength; i++) {
            trace.push_back(currentPath);
            currentPath = (currentPath == 'L') ? 'G' : 'L';
        }

        remainingScore -= chosenLength * chosenLength;

        // Repeating the previous ending path creates a block boundary.
        startPath = trace.back();
    }

    cout << trace << '\n';
}
0