ABC137 A,B,C,D 反省会 -- priority_queue と料理

A: max 2 回やったけど initializer-list 使えば解説のとおり 1 回で済むね

B: i < -1000000 || i > 1000000 だったら除外しなきゃとかやったんだけどいま制約条件みたら 0 <= X <= 100 だったわ

C: 最初は sort して multiset<string> に放り込むときにダブリをいちいち数えるコードにしたんだけど、提出するときに制約的に TLE しそうだなーと思ったら案の定 TLE した。 map<string,int> にして少し工夫したら通った。あと解説放送みてたら同じく map<string,int> ではあるものの、ペアの数ではなく同じ文字列の個数のみ記録して最後に個数から i*(i-1)/2 の総和取ってて頭いいなと思った。あとこういうときは unordered_map でいいねって言ってた。確かにハッシュ化されてればよくて、ランダムアクセスは不要な問題。

D: 終了間際に解法は思いつくも、自力実装30分やってもバグったので諦めて解説放送みた。解説放送みたら v[M-a].pb(b) していて、何日目に実行可能な仕事であるかという情報を vector のインデックスに入れてしまうのは、取得がバグりにくくてめちゃめちゃ頭いいなと思った。

D の実装で vector から条件を満たすものを探して取得して削除して、なんてことを何行もかけて書くと必ずバグることを痛感した。インデックスでアクセスしようがイテレータでアクセスしようが、要素を削除するとずれる。それよか、解説放送のように vector の vector にしてしまって、削除の必要がないデータ構造にしてしまうほうが安全。

  int N, M;
  cin >> N >> M;
  vector<vector<int>> v(M);
  REP(i, N) {
    int a,b;
    cin >> a >> b;
    if (a > M) continue;
    v[M-a].pb(b);
  }

  int ans = 0;
  priority_queue<int> que;

  DEC(i, M-1, -1) {
    for (auto b: v[i]) que.push(b);

    if (!que.empty()) {
      ans += que.top();
      que.pop();
    }
  }

  cout << ans << endl;

priority_queue の使い方だが、pair<int,int> みたいに複雑なものを入れて Compare をがんばって自力で書いてバグらせるよりは、条件満たしたものを単に int で突っ込んで最大値をそのまま top で取り出して pop で消すだけ、としたほうがいい。料理と同じで下ごしらえをちゃんとやる方がシンプルに書けるし手が楽。

料理と同じといえば、今回は最終的な状態から時系列的に逆行して貪欲法やればよいという点も料理に似ている。まあ何でもかんでも逆算すればよいというものでもなくて、今回たまたまそうだっただけで、料理も逆算ばかりが重要なわけではなく、途中行程の特に1箇所がとても重要な料理もあり、競プロも TLE しないための工夫が大事だったり、とにかく台所に揃えておきたい選択肢が多いという意味のほうがむしろ料理と競プロの似ているところかもしれない。

おいしい料理も競プロも僕はまだまだ手探りです。