Test/Range/bit_subset.test.cpp

View this file on GitHub
Last update: 2024-12-27 17:07:26+09:00
Problem: https://yukicoder.me/problems/no/733

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/733"

#include <iostream>
#include <vector>

// begin:tag includes
#include "../../Library/Range/bit.hpp"
#include "../../Library/Utility/Tools.hpp"
// end:tag includes

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int t, n;
  std::cin >> t >> n;
  std::vector<int> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto sum = mtd::vec(0, 1 << n);
  for (auto bit : std::views::iota(1, 1 << n)) {
    auto b = mtd::ctz(bit);
    sum[bit] = (bit == (1 << b) ? 0 : sum[bit ^ (1 << b)]) + a[b];
  }

  auto dp = mtd::vec(n, 1 << n);
  for (auto bit : std::views::iota(0, 1 << n)) {
    if (sum[bit] <= t) { dp[bit] = 1; }
  }
  for (auto bit : std::views::iota(0, 1 << n)) {
    for (auto sub : mtd::views::bit_subset(bit)) {
      mtd::chmin(dp[bit], dp[sub] + dp[bit ^ sub]);
    }
  }
  std::cout << dp[(1 << n) - 1] << std::endl;
}

#line 1 "Test/Range/bit_subset.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/733"

#include <iostream>
#include <vector>

// begin:tag includes
#line 2 "Library/Range/bit.hpp"

#include <ranges>

#line 2 "Library/Math/Bit.hpp"

namespace mtd {

  constexpr unsigned clz(unsigned int x) {
    int c = 0;
    if (x == 0) { return 0; }
    if (x & 0xffff0000) {
      x &= 0xffff0000;
      c |= 0x10;
    }
    if (x & 0xff00ff00) {
      x &= 0xff00ff00;
      c |= 0x08;
    }
    if (x & 0xf0f0f0f0) {
      x &= 0xf0f0f0f0;
      c |= 0x04;
    }
    if (x & 0xcccccccc) {
      x &= 0xcccccccc;
      c |= 0x02;
    }
    if (x & 0xaaaaaaaa) { c |= 0x01; }
    return c + 1;
  }

  constexpr unsigned ctz(unsigned int n) {
    if (!n) return -1;
    unsigned int c = 32;
    n &= -static_cast<signed int>(n);
    if (n) c--;
    if (n & 0x0000FFFF) c -= 16;
    if (n & 0x00FF00FF) c -= 8;
    if (n & 0x0F0F0F0F) c -= 4;
    if (n & 0x33333333) c -= 2;
    if (n & 0x55555555) c -= 1;
    return c;
  }

  constexpr unsigned long long popcount(unsigned long long x) {
    x = x - ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32);
    return x & 0x0000007f;
  }

}  // namespace mtd
#line 6 "Library/Range/bit.hpp"

namespace mtd {
  namespace ranges {
    struct bit_index_view : public std::ranges::view_interface<bit_index_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::forward_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(ctz(_bit)), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          bit ^= (1 << i);
          i = ctz(bit);
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return bit == other.bit;
        }
      };

      int bit;

      constexpr explicit bit_index_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_subset_view
        : public std::ranges::view_interface<bit_subset_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(_bit), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i - 1) & bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i;
        }
      };

      int bit;

      constexpr explicit bit_subset_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_supset_view
        : public std::ranges::view_interface<bit_supset_view> {
      class iterator {
        int i;
        int bit;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit, int _n)
            : i(_bit), bit(_bit), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i + 1) | bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && bit == other.bit && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int bit;
      int n;

      constexpr explicit bit_supset_view(int _bit, int _n) : bit(_bit), n(_n) {}
      constexpr auto begin() const { return iterator(bit, n); }
      constexpr auto end() const { return std::default_sentinel; }
    };

    struct k_bit_subset_view
        : public std::ranges::view_interface<k_bit_subset_view> {
      class iterator {
        int i;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _n, int _k) : i((1 << _k) - 1), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          int x = i & -i;
          int y = i + x;
          i = (((i & ~y) / x) >> 1) | y;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int n, k;
      constexpr explicit k_bit_subset_view(int _n, int _k) : n(_n), k(_k) {}
      constexpr auto begin() const { return iterator(n, k); }
      constexpr auto end() const { return std::default_sentinel; }
    };
  }  // namespace ranges

  namespace views {
    namespace __detail {
      template <typename... _Args>
      concept __can_bit_index_view = requires {
        ranges::bit_index_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_subset_view = requires {
        ranges::bit_subset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_supset_view = requires {
        ranges::bit_supset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_k_bit_subset_view = requires {
        ranges::k_bit_subset_view(std::declval<_Args>()...);
      };
    }  // namespace __detail

    struct _BitIndex {
      template <class... _Tp>
      requires __detail::__can_bit_index_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_index_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitIndex bit_index{};

    struct _BitSubsetView {
      template <class... _Tp>
      requires __detail::__can_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSubsetView bit_subset{};

    struct _BitSupsetView {
      template <class... _Tp>
      requires __detail::__can_bit_supset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_supset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSupsetView bit_supset{};

    struct _KBitSubsetView {
      template <class... _Tp>
      requires __detail::__can_k_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::k_bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _KBitSubsetView k_bit_subset{};
  }  // namespace views

}  // namespace mtd
#line 2 "Library/Utility/Tools.hpp"

#line 4 "Library/Utility/Tools.hpp"

namespace mtd {

  template <class T, class S>
  inline auto chmax(T& t, const S& s) {
    if (s > t) {
      t = s;
      return true;
    }
    return false;
  }

  template <class T, class S>
  inline auto chmin(T& t, const S& s) {
    if (s < t) {
      t = s;
      return true;
    }
    return false;
  }

  template <class S>
  constexpr auto vec(S x) {
    return x;
  }

  template <class S, class... T>
  constexpr auto vec(S x, int n, T... ns) {
    return std::vector(n, vec(x, ns...));
  }

}  // namespace mtd
#line 9 "Test/Range/bit_subset.test.cpp"
// end:tag includes

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int t, n;
  std::cin >> t >> n;
  std::vector<int> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto sum = mtd::vec(0, 1 << n);
  for (auto bit : std::views::iota(1, 1 << n)) {
    auto b = mtd::ctz(bit);
    sum[bit] = (bit == (1 << b) ? 0 : sum[bit ^ (1 << b)]) + a[b];
  }

  auto dp = mtd::vec(n, 1 << n);
  for (auto bit : std::views::iota(0, 1 << n)) {
    if (sum[bit] <= t) { dp[bit] = 1; }
  }
  for (auto bit : std::views::iota(0, 1 << n)) {
    for (auto sub : mtd::views::bit_subset(bit)) {
      mtd::chmin(dp[bit], dp[sub] + dp[bit ^ sub]);
    }
  }
  std::cout << dp[(1 << n) - 1] << std::endl;
}