結果
| 問題 | No.3060 Erase Binary Matrix |
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2026-03-01 22:26:25 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 7,922 bytes |
| 記録 | |
| コンパイル時間 | 1,284 ms |
| コンパイル使用メモリ | 185,400 KB |
| 実行使用メモリ | 7,972 KB |
| 最終ジャッジ日時 | 2026-03-01 22:26:30 |
| 合計ジャッジ時間 | 2,881 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 49 |
ソースコード
#line 1 "data_structure/test/dynamic_bitset.yuki3060.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3060"
#line 2 "data_structure/dynamic_bitset.hpp"
#include <algorithm>
#include <string>
#include <vector>
struct dynamic_bitset {
using ull = unsigned long long;
static constexpr int W = 64;
int n = 0; // number of bits
int m = 0; // number of 64-bit blocks
std::vector<ull> a; // blocks
dynamic_bitset() = default;
explicit dynamic_bitset(int n_, bool init_one = false) { reset_size(n_, init_one); }
explicit dynamic_bitset(const std::string &s) : dynamic_bitset(int(s.size())) {
for (int i = 0; i < n; ++i) set(i, s[i] == '1');
}
void reset_size(int n_, bool init_one = false) {
n = n_;
m = (n + W - 1) / W;
a.assign(m, init_one ? ~0ULL : 0ULL);
trim();
}
int size() const { return n; }
// ---- low-level helpers ----
ull last_mask() const {
int r = n & (W - 1);
if (r == 0) return ~0ULL;
return (r == 64 ? ~0ULL : ((1ULL << r) - 1ULL));
}
void trim() {
if (m == 0) return;
a.back() &= last_mask();
}
static inline int ctz64(ull x) { return __builtin_ctzll(x); }
static inline int clz64(ull x) { return __builtin_clzll(x); }
static inline int msb_index64(ull x) { return 63 - clz64(x); } // x != 0
// ---- basic bit ops ----
bool test(int i) const { return (a[i >> 6] >> (i & 63)) & 1ULL; }
void set(int i) { a[i >> 6] |= (1ULL << (i & 63)); }
void reset(int i) { a[i >> 6] &= ~(1ULL << (i & 63)); }
void flip(int i) { a[i >> 6] ^= (1ULL << (i & 63)); }
void set(int i, bool v) { v ? set(i) : reset(i); }
void reset_all() { std::fill(a.begin(), a.end(), 0ULL); }
void set_all() {
std::fill(a.begin(), a.end(), ~0ULL);
trim();
}
void flip_all() {
for (auto &x : a) x = ~x;
trim();
}
// count (optional but handy)
long long popcount() const {
long long s = 0;
for (ull x : a) s += __builtin_popcountll(x);
return s;
}
long long count() const { return popcount(); }
// ---- bitwise ops ----
// ---- any / none ----
bool any() const {
for (ull x : a)
if (x) return true;
return false;
}
bool none() const { return !any(); }
// ---- bitwise assign ops ----
dynamic_bitset &operator^=(const dynamic_bitset &o) {
// assume same size in competitive programming usage
for (int i = 0; i < m; i++) a[i] ^= o.a[i];
trim();
return *this;
}
dynamic_bitset &operator|=(const dynamic_bitset &o) {
for (int i = 0; i < m; i++) a[i] |= o.a[i];
trim();
return *this;
}
dynamic_bitset &operator&=(const dynamic_bitset &o) {
for (int i = 0; i < m; i++) a[i] &= o.a[i];
trim();
return *this;
}
friend dynamic_bitset operator^(dynamic_bitset l, const dynamic_bitset &r) {
l ^= r;
return l;
}
friend dynamic_bitset operator|(dynamic_bitset l, const dynamic_bitset &r) {
l |= r;
return l;
}
friend dynamic_bitset operator&(dynamic_bitset l, const dynamic_bitset &r) {
l &= r;
return l;
}
bool operator==(const dynamic_bitset &o) const { return n == o.n && a == o.a; }
bool operator!=(const dynamic_bitset &o) const { return !(*this == o); }
dynamic_bitset operator~() const {
dynamic_bitset r = *this;
for (auto &x : r.a) x = ~x;
r.trim();
return r;
}
// ---- shifts ----
dynamic_bitset &operator<<=(int k) {
if (k <= 0 || n == 0) return *this;
if (k >= n) {
reset_all();
return *this;
}
int ws = k >> 6;
int bs = k & 63;
if (ws) {
for (int i = m - 1; i >= 0; --i) {
ull v = (i - ws >= 0) ? a[i - ws] : 0ULL;
a[i] = v;
}
}
if (bs) {
for (int i = m - 1; i >= 0; --i) {
ull hi = a[i] << bs;
ull lo = (i ? (a[i - 1] >> (64 - bs)) : 0ULL);
a[i] = hi | lo;
}
}
// zero-fill lower words introduced by ws shift
if (ws) {
for (int i = 0; i < ws && i < m; ++i) a[i] = 0ULL;
}
trim();
return *this;
}
dynamic_bitset &operator>>=(int k) {
if (k <= 0 || n == 0) return *this;
if (k >= n) {
reset_all();
return *this;
}
int ws = k >> 6;
int bs = k & 63;
if (ws) {
for (int i = 0; i < m; ++i) {
ull v = (i + ws < m) ? a[i + ws] : 0ULL;
a[i] = v;
}
}
if (bs) {
for (int i = 0; i < m; ++i) {
ull lo = a[i] >> bs;
ull hi = (i + 1 < m ? (a[i + 1] << (64 - bs)) : 0ULL);
a[i] = lo | hi;
}
}
// zero-fill upper words introduced by ws shift
if (ws) {
for (int i = m - ws; i < m; ++i)
if (0 <= i && i < m) a[i] = 0ULL;
}
trim();
return *this;
}
friend dynamic_bitset operator<<(dynamic_bitset b, int k) {
b <<= k;
return b;
}
friend dynamic_bitset operator>>(dynamic_bitset b, int k) {
b >>= k;
return b;
}
// ---- find set bits ----
// returns smallest i with bit=1, or -1
int first() const {
for (int i = 0; i < m; ++i) {
ull x = a[i];
if (x) return (i << 6) + ctz64(x);
}
return -1;
}
// returns smallest j > i with bit=1, or -1
int next(int i) const {
if (n == 0) return -1;
int j = i + 1;
if (j <= 0) return first();
if (j >= n) return -1;
int b = j >> 6;
int off = j & 63;
// mask out bits < off
ull x = a[b] & (~0ULL << off);
if (x) return (b << 6) + ctz64(x);
for (int bb = b + 1; bb < m; ++bb) {
ull y = a[bb];
if (y) return (bb << 6) + ctz64(y);
}
return -1;
}
// returns largest i with bit=1, or -1
int last() const {
for (int i = m - 1; i >= 0; --i) {
ull x = a[i];
if (i == m - 1) x &= last_mask();
if (x) return (i << 6) + msb_index64(x);
}
return -1;
}
// returns largest j < i with bit=1, or -1
int prev(int i) const {
if (n == 0) return -1;
int j = i - 1;
if (j < 0) return -1;
if (j >= n) return last();
int b = j >> 6;
int off = j & 63;
ull mask = (off == 63) ? ~0ULL : ((1ULL << (off + 1)) - 1ULL);
ull x = a[b] & mask;
if (x) return (b << 6) + msb_index64(x);
for (int bb = b - 1; bb >= 0; --bb) {
ull y = a[bb];
if (y) return (bb << 6) + msb_index64(y);
}
return -1;
}
};
#line 4 "data_structure/test/dynamic_bitset.yuki3060.test.cpp"
#include <iostream>
#line 6 "data_structure/test/dynamic_bitset.yuki3060.test.cpp"
using namespace std;
int main() {
cin.tie(nullptr), ios::sync_with_stdio(false);
int H, W;
cin >> H >> W;
using BS = dynamic_bitset;
vector<BS> A(H);
for (int i = 0; i < H; ++i) {
string s;
cin >> s;
A.at(i) = BS(s);
}
sort(A.begin(), A.end(), [&](const BS &l, const BS &r) { return l.count() < r.count(); });
vector<int> dp(H + 1);
for (int i = 0; i < H; ++i) {
dp[i + 1] = max(dp[i + 1], 1);
for (int j = 0; j < i; ++j) {
if ((A.at(i) & A.at(j)) == A.at(j)) dp[i + 1] = max(dp[i + 1], dp[j + 1] + 1);
}
}
cout << H - *max_element(dp.begin(), dp.end()) << '\n';
}