ABC379、D問題が解けない（茶レベル）

Question

実現したいこと

リンク内容
の問題で、自分の考えたアルゴリズムは何がいけないのか知りたい。

発生している問題・分からないこと

解答を理解することはできました。しかし、自分の書いたコードではなぜ不正解になるのかが分かりません。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define ll long long

int main() {
    ll Q; 
    cin >> Q;
    vector<vector<ll>> vec(Q, vector<ll>(2));
    vector<pair<ll, ll>> pot(1, {0, 0});

    rep(i, Q) {
        cin >> vec[i][0];

        if (vec[i][0] == 1) {
            if (i != 0 && vec[i - 1][0] == 2) {
                pot.push_back({0, 0});
            }
            else if (pot.empty()) {
                pot.push_back({0, 0});
            }
            pot.back().first++;
        } 
        else if (vec[i][0] == 2) {
            cin >> vec[i][1];
            if (!pot.empty()) pot.back().second += vec[i][1];
        } 
        else if (vec[i][0] == 3) {
            cin >> vec[i][1];
            if (pot.empty()) {
                cout << 0 << endl;
                continue;
            }

            ll height = 0, ans = 0;
            bool harvested = false;

            for (ll j = pot.size() - 1; j >= 0; j--) {
                height += pot[j].second;
                if (height >= vec[i][1]) {
                    for (int k = 0; k <= j; k++) {
                        ans += pot[k].first;
                    }
                    cout << ans << endl;
                    pot.erase(pot.begin(), pot.begin() + j + 1);
                    harvested = true;
                    break;
                }
            }

            if (!harvested) {
                cout << 0 << endl;
            }
        }
    }

    return 0;
}

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

ChatGPTに聞いたり、デバッグ文字を追加して状況を逐一調べたりしましたが、入力例ではすべてうまくいっていて、何がいけないのかわかりません。

補足

特になし

Comments

[fana]

> 自分の考えたアルゴリズムは何がいけないのか

という話をしたい（：「アルゴリズムあるいはその実装たるコードのここがこう間違ってるよ」みたいな話が欲しい）のであれば，
なにはともあれ「自分の考えたアルゴリズム」の内容というのを他者にわかるように説明した方が，そういう方向に話が行きやすくなるんじゃないかと思いますが，どうなんでしょうね？

Answer 1

たぶんほかの人の回答もあったほうが参考になると思うので、(というか、個人的に書きたかったので)書いてみました。
c++言語があまりよくわからなくて、競技プログラミング避けていたんですが、結構問題見たときに面白いなと思ってチャレンジしてみました。

難しい型とかはわからないので、最低限vectoerだけ勉強して書きました。(queue操作がやりづらかったが)

TODOが残ってますが、考え方として特に清書せずに残しました。
intだとオーバーフローするかもしれないですが、そこらへんは定義域を見て調整すればよいと思いました。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define ll long long

int inputQ() {
    int Q;
    cin >> Q;
    return Q;
}

vector<vector<int>> inputTable(int Q) {
    
    vector<vector<int>> table(Q, vector<int>(2, 0));
    
    int inputInt1, inputInt2;
    
    for (int i = 0; i < Q; ++i) {
        cin >> inputInt1;
        table[i][0] = inputInt1;
        // 2, 3 の場合は追加で入力を受け付ける
        if (inputInt1 == 2 || inputInt1 == 3) cin >> inputInt2, table[i][1] = inputInt2;
    }
    
    
    return table;
    
}

int main() {
    int Q; 
    Q = inputQ();
    
    vector<vector<int>> table(Q, vector<int>(2, 0));
    table = inputTable(Q);
    
    // 入力のprint debug
    // for (int i = 0; i < table.size(); i ++) {
    //     for (int j = 0; j < table[i].size(); j ++) {
    //         cout << table[i][j];
    //     }
    //     cout << endl;
    // }
    
    // return 0;
    
    // キュー構造として考える
    vector<vector<int>> storage(0, vector<int>(2, 0));
    
    
    // TODO 1が何回続いたかを記録する
    // TODO 2が起きた回数を加算する
    // TODO 3が起きたら後ろから配列を消す　resize(n)メソッドを使用する 
    for (int i = 0; i < Q; ++i) {
        int tag = table[i][0];
        
        // Memo: switchを使うと変数のスコープの挙動でエラーを吐く
        if (tag == 1) {
            // 初回の種植え、または、育った種がすでにあったら、先頭に新しいものを用意する
            if (storage.size() <= 0 || storage[0][1] > 0) storage.insert(storage.begin(), {0, 0});
            // 埋められた回数を記録する
            storage[0][0] = storage[0][0] + 1;
        } else if (tag == 2) {
             int T = table[i][1];
            // 各埋められた回数の横に、高さを記録する
            for (int j = 0; j < storage.size(); ++j) {
                storage[j][1] = T;
            }
        } else if (tag == 3) {
            int H = table[i][1];
            int result = 0;
            for (int j = storage.size() - 1; j >= 0; -- j) {
              if (H <= storage[j][1]) {
                  result = result + storage[j][0];
                  storage.resize(j);
              } else {
                  // O(N)のためbreakしなくても遅くはない
                  break;
              }
            }
            
            cout << result << endl;
        }
    }
     
    // vector<vector<ll>> vec(Q, vector<ll>(2));
    // vector<pair<ll, ll>> pot(1, {0, 0});

    // rep(i, Q) {
    //     cin >> vec[i][0];

    //     if (vec[i][0] == 1) {
    //         if (i != 0 && vec[i - 1][0] == 2) {
    //             pot.push_back({0, 0});
    //         }
    //         else if (pot.empty()) {
    //             pot.push_back({0, 0});
    //         }
    //         pot.back().first++;
    //     } 
    //     else if (vec[i][0] == 2) {
    //         cin >> vec[i][1];
    //         if (!pot.empty()) pot.back().second += vec[i][1];
    //     } 
    //     else if (vec[i][0] == 3) {
    //         cin >> vec[i][1];
    //         if (pot.empty()) {
    //             cout << 0 << endl;
    //             continue;
    //         }

    //         ll height = 0, ans = 0;
    //         bool harvested = false;

    //         for (ll j = pot.size() - 1; j >= 0; j--) {
    //             height += pot[j].second;
    //             if (height >= vec[i][1]) {
    //                 for (int k = 0; k <= j; k++) {
    //                     ans += pot[k].first;
    //                 }
    //                 cout << ans << endl;
    //                 pot.erase(pot.begin(), pot.begin() + j + 1);
    //                 harvested = true;
    //                 break;
    //             }
    //         }

    //         if (!harvested) {
    //             cout << 0 << endl;
    //         }
    //     }
    // }

    return 0;
}

Comments

[utm.]

解説の方法は思いつかないですね。

合計の成長数と植えたときの成長数を引けばその間にどのくらい成長したかわかるってやつですよね。
なんか記憶の片隅にマンションが題材の問題で見た気がしますが、思いつかない自信しかないですね。

[fana]

本件は

> 自分の考えたアルゴリズムは何がいけないのか知りたい

とかいう話になっているのですが，それに対してこの回答というのは
「質問者と同じアルゴリズム　を実装してみたつもり」という内容であるのか，
「（質問文に提示されているコードとは無関係に）個人的に解いてみたよ」という話であるのか
どちらなのでしょう？

……っていう意味合いが明言されていた方が参考にしやすいのではないか，とか思いました．

[utm.]

後者です。

Answer 2

1の処理で、新しい経過日数の異なるpotを追加する条件が
potが無いときと
直前の処理が2の処理の時になっていますが、
直前の処理だけでなく、前回の新しいpot用意してから今までに2の処理があった場合になると思います。
（例 直前の処理が３の場合、刈り取った後の最新potは経過日数が0でない場合もあります）

さかのぼってチェックするのは面倒なのでシンプルに
その条件をpotが無いときと最新のpotの経過日数が0以外であるならで代用できないでしょうか？
１６行目(１の処理)

if ( pot.empty() ) {
        pot.push_back({0, 0});
} else if(pot.back().second!=0){
       pot.push_back({0, 0});
}
pot.back().first++;

Answer 3

1 : 植物が植えられていない植木鉢を
1 個用意し、その植木鉢に植物を植える。このとき植物の高さは
0 である。
2 T :
T 日待つ。このとき植えてあるすべての植物の高さが
T 増加する。
3 H : 高さが
H 以上の植物をすべて収穫し、収穫した植物の数を出力する。収穫した植物は植木鉢から取り除かれる。

つまり

"1" だったら pot に 1 つ追加
"2" だったら pot 内の全ての高さに T を加算
"3" だったら pot 内の全ての高さを調べて H 以上のものを数えて表示/削除

ですので、 vec みたいに過去のクエリを覚えておく必要も無ければ pot の first も必要無いのではないでしょうか。

書いてから解説を見ましたらベタだと時間かかるので区間を加算しておくヤツ（名前忘れた）にするんですね、失礼しました。

Answer 4

入力例ではすべてうまくいっていて、何がいけないのかわかりません。

とのことなので、うまくいかない入力例を挙げておきます。こちらの入力例でデバッグしてみてください。

以下の入力例について

5
1
2 1
3 2
1
3 1

正しい出力は以下ですが

0
1

ご提示のコードだと以下が出力されます。

0
2

---

上記入力例に対処すれば、AtCoder上では正答扱いになりますが、実際には時間超過が発生する可能性が残っています。
ご提示のコードに以下のような入力を与えると、収穫1回ごとに38行目で50,000回のループが発生し、収穫が100,000回行われるので、全体で5,000,000,000回の処理が行われることになります。対処方法については解説に載っている通りなので、そちらを参照してください。

200000
1
2 1
(上記2行を50,000回繰り返し)
3 50001
(上記1行を100,000回繰り返し)