競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

凍ってこまったこと #2 (WIP)

凍りました。こまりました。まとめます。(2) これから追記するかもしれません？

こまったこと

ひとのライブラリにバグを見つけたとき

https://dr0gsk0l.github.io/library/superstd/Multiset.cppdr0gsk0l.github.io

これの erase_k 、

  void erase_k(const T&a,int k){
    if(map<T,int>::count(a))return;
    at(a)-=k;
    if(at(a)<=0)erase(a);
  }

if(count(a)) で return したらよくない気がします

こういうとき、Twitter がないと言いにくいですね。 github でプルリクエストを出したらいいんじゃないですか？ぽか。

rate limit にひっかかったとき

なんだかすぐに制限がかかる気がします 気のせいですか？そうかも？

ぽか

書きません（？？） 編集前のコードはこんな感じでした

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    unsigned N, T, M;
    cin >> N >> T >> M;

    // hate[i] の j ビットめが 1 ⟹ i 番目の選手と j 番目の選手の相性が悪い (0-indexed)
    vector<unsigned> hate(N);
    for(unsigned i{}, a, b; i < M; ++i){
        cin >> a >> b;
        hate[--b] |= 1U << --a;
    }

    // 再帰関数で計算した値を出力
    cout << [dfs{[N, T, &hate](auto&& f, vector<unsigned>& teams, unsigned now) -> unsigned {
        // 最後の選手まで見て T チームに分かれていれば OK
        if(now == N)
            return size(teams) == T;

        unsigned ans{};

        // すでにあるチームに now 番目の選手を追加する
        for(auto&& team : teams)
            // チームに now 番目の選手と相性の悪い選手がいなければ
            if(!(team & hate[now])){
                team ^= 1U << now;
                ans += f(f, teams, now + 1);
                team ^= 1U << now;
            }

        // チーム数に余裕があるとき、新しいチームを作る
        if(size(teams) < T){
            teams.emplace_back(1U << now);
            ans += f(f, teams, now + 1);
            teams.pop_back();
        }

        return ans;
    }}, T]{
        vector<unsigned> team;
        team.reserve(T);
        return dfs(dfs, team, 0);
    }() << endl;

    return 0;
}

「無名関数再帰をキャプチャで受けてどうこうするのはイディオムすぎる」「unsigned じゃなくて int でもよくない？」「整数の初期化に一様初期化を使う意味はない」などのご意見があります。

  • 無名関数で再帰をする
    • 実際かなり知らないと読みにくそうな気がします。ごめんなさいです。グローバルに変数とか関数とかを置いて再帰を書くことをしないまま時を過ごしているのでラムダ式で再帰を書きがちなんですけど、やさしくないな〜と言われると返す言葉もございません（ぽか）。
  • unsigned じゃなくて int でもよい
    • まあそうなんですけど、そうなんですけど、むん。符号なしでいいなら符号なしでよくないですか？オーバーフローも未定義にならないですし。
  • 整数の初期化に一様初期化を使うな
    • これはわたしもなんで使ってるのかわからないんですけど、vector も set も modint も {} で初期化するのに慣れちゃいました。統一感。= 0 と打つより shift を押しながら中指を滑らせて {} と打鍵するほうが速いです（？）。

特に A-B 問題ではなるべく癖を抜くようにしてるんですけど、C 問題以降だとなかなか抜けていないことも多いかんじがします。 気をつけます。 ところで今日の B 問題の解説は入れ子になった any_of があるんですけど、ちゃんと癖抜けてますか？？気をつけます（でもこっちも意味論的に読みやすい気がするんですけどね（？）。std::ranges::any_of が使えるようになったらもっと読みやすくなる気がするんですけど（？？）。for 文とにゃんにゃんするプログラムも併記するかもしれません）

ちゃんと文を読むだけでわかってもらえる解説が書けるようになりたいですね。〜完〜

制限を満たしている状態で writer になったあと制限を満たさなくなると、こうなります（ぽか）。