松針を松枝に挿入する加工工程をプログラムで再現する問題を考えます。この工程は特定の制約条件下でデータを処理する必要があり、適切なデータ構造の選択が解決の鍵となります。

与えられるものは、供給装置に並んだ N 枚の松針、容量 M の一時保管箱、容量 K の松枝です。松枝への挿入は、常に前回挿入した松針以下のサイズであるという制約があります。この制約を満たしながら、可能な限り多くの松枝を作成する必要があります。

アルゴリズムの核心は、以下の優先順位に従って松針を選択することです。

1. 保管箱の最上面の松針が挿入条件を満たす場合、これを優先して使用
2. 満たさない場合、供給装置の先頭の松針が条件を満たすか確認
3. いずれも満たさず、かつ保管箱に空きがある場合、供給装置から松針を取り出して保管箱に格納し、再び先頭の松針を確認
4. 保管箱が満杯で挿入不可の場合、現在の松枝を完成させる

このロジックを実現するために、供給装置には先入れ先出しのキュー、保管箱には後入れ先出しのスタックを用います。これにより、工人の作業プロセスを忠実に再現できます。

入出力仕様

最初の行に N M K が空白区切りで与えられます。続く行に N 個の整数が供給順に並んでいます。完成した松枝ごとに、底から順に松針サイズを空白区切りで出力します。

実装詳細

以下の実装では、純粋な配列とインデックス操作を用いてメモリ効率を最大化しています。STL コンテナを使用しないことで、オーバーヘッドを排除しています。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int needle_count, box_max, branch_max;
    cin >> needle_count >> box_max >> branch_max;
    
    vector<int> supply(needle_count);
    for (int i = 0; i < needle_count; ++i) {
        cin >> supply[i];
    }
    
    int supply_pos = 0;
    int temp_box[20];
    int box_idx = -1;
    vector<vector<int>> completed;
    vector<int> branch;
    
    while (supply_pos < needle_count || box_idx >= 0 || !branch.empty()) {
        // 空の松枝の開始処理
        if (branch.empty()) {
            if (box_idx >= 0) {
                branch.push_back(temp_box[box_idx--]);
            } else if (supply_pos < needle_count) {
                branch.push_back(supply[supply_pos++]);
            } else {
                break;
            }
            continue;
        }
        
        int previous = branch.back();
        
        // 保管箱の確認
        if (box_idx >= 0 && temp_box[box_idx] <= previous) {
            branch.push_back(temp_box[box_idx--]);
        }
        // 供給装置の確認
        else if (supply_pos < needle_count) {
            if (supply[supply_pos] <= previous) {
                branch.push_back(supply[supply_pos++]);
            } else if (box_idx + 1 < box_max) {
                temp_box[++box_idx] = supply[supply_pos++];
            } else {
                completed.push_back(branch);
                branch.clear();
            }
        }
        // 供給装置が空
        else {
            completed.push_back(branch);
            branch.clear();
        }
        
        // 容量チェック
        if (branch.size() == branch_max) {
            completed.push_back(branch);
            branch.clear();
        }
    }
    
    // 結果表示
    for (size_t i = 0; i < completed.size(); ++i) {
        for (size_t j = 0; j < completed[i].size(); ++j) {
            if (j) cout << " ";
            cout << completed[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

このコードは、供給装置の位置ポインタ、スタックトップインデックス、現在の松枝の状態を明確に分離して管理しています。これにより、各ステップでの条件分岐を明確に記述でき、バグの発生を抑制します。