Namaran

Code daily. Without assist.

2026-10-09

task_orders.cpp

#include <array>
#include <print>

int main() {
    constexpr std::array need{0b0000, 0b0001, 0b0001, 0b0010};
    constexpr int n = need.size();
    std::array<int, 1 << n> ways{};
    ways[0] = 1;
    for (int mask = 0; mask < 1 << n; ++mask)
        for (int j = 0; j < n; ++j)
            if (!(mask >> j & 1) && (need[j] & mask) == need[j])
                ways[mask | 1 << j] += ways[mask];
    std::println("{}", ways[(1 << n) - 1]);
}

これは何を出力するでしょうか?

Answer

3 です。

ways[mask] は、mask のビットが立っている作業を終えた状態へ、何通りの順番でたどり着けるかを表します。mask ごとに、まだ終えていない作業 j のうち、前提 need[j] のビットがすべて mask に含まれるものを次に終えられるとして、ways[mask | 1 << j] に ways[mask] を足します。mask | 1 << j は mask より大きいので、mask を小さい順に回せば、ある状態を読むときにはそこへの足し込みがすべて済んでいます。

need によると、作業0には前提がなく、1と2は0の後、3は1の後です。最初に終えられるのは0だけなので、残りは1、2、3を「1が3より前」という条件だけで並べる順番になります。3つの並べ方6通りのうち、1が3より前に来るのは1 2 3、1 3 2、2 1 3の3通りで、全作業を終えた ways[0b1111] は3です。