Bitmasking

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5638 🧐 관찰 및 접근 # 댐에 수문이 있고, 유량과 피해비용이 있는 것 같다. 피해비용은 여는 시간에 비례하지 않는 것 같다. 그러면 각 수문에 대해, 유량에 시간을 곱해서 각 수문이 버릴 수 있는 물의 양을 구할 수 있고, 그에 따른 가격이 나온다. 이건 그리디하게는 조금 곤란하고, 배낭 문제로 되나? 했는데, $V$가 너무 크다! 그런데 수문의 개수가 $n \leq 20$으로 유의미하게 작다. 각 테스트케이스에 대해 모든 수문을 열어보는 경우의 수를 수행할 수 있을 것 같다. 시간복잡도 $O(2^n \cdot nm)$ 정도에 동작할 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pll> door(N); rep(i, 0, N) cin >> door[i].first >> door[i].second; int Q; cin >> Q; rep(q, 1, Q+1){ ll V, T; cin >> V >> T; ll ans = 1e18; rep(bit, 0, 1<<N){ ll wat = 0, cost = 0; rep(i, 0, N) if(bit & (1<<i)) wat += door[i].first*T, cost += door[i].second; if(wat >= V) ans = min(ans, cost); } cout << "Case " << q << ": "; if(ans == 1e18) cout << "IMPOSSIBLE\n"; else cout << ans << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/15896 🧐 관찰 및 접근 # bitwise and들의 합과, 합들의 bitwise and 값을 구해야한다. 일단 앞에껏부터 해보자. $N$은 100만??이다. 개크네 모든 $(A_i \& B_j)$의 합을 1999로 나눈 나머지 나이브하게 제곱은 될 리가 없다. bitwise and의 특성을 생각해보자. $A_i$에서도, $B_j$에서도 켜져있어야 한다. 각 비트에 대해서 생각하면, $A$에서 해당 비트가 켜진 개수 * $B$에서 해당 비트가 켜진 개수와 같이 구할 수 있을 것 같다. 전처리에 $O(N\times29)$, 계산하는데에 $O(29)$가 걸릴 것 같다. 모든 $(A_i + B_j)$의 bitwise and 연산 값 자 이제 이게 문젠거같은데… 합이 이슈다. 받아올림이 있다보니 조금 신경쓰인다. 다시한번 bitwise and의 특성을 생각해보자. 모두 켜져있어야 한다는건, 모든 순서쌍 $(i, j)$에 대해 $A_i + B_j = C_k$라고 할때, 어떤 $C_k$의 비트가 꺼져있으면, 정답에서 해당 비트는 꺼진다. 일단 첫번째 비트에 대해서는 쉽게 구할 수 있는 것 같다. 더했을때 모두 $1$이 남기 위해선 $1 + 0, 0 + 1$ 두가지만 가능하기에, 개수가 $(N, 0), (0, N)$이 아니라면 비트가 꺼질 수밖에 없다. 하지만 해당 윗 비트부터는 받아올림이 생긴다… $11_2 + 01_2 = 100_2$ 와 같이 $(1, 0)$이었음에도 비트가 꺼질 수 있다. 혹은 $11_2 + 11_2 = 110_2$와 같이 $(1, 1)$이었으메도 비트가 켜질 수 있다. 하 이게 무슨 의미지? 예를들어 $4$의자리 비트가 켜져있나? 라는 질문은 $8$로 나눈 나머지들의 합에 대해, 나머지가 모두 $4$ 이상인가? 하는 질문과 같긴 하다. $0$$3$, $8$$11$은 안된다는거지. 그 사이에 값이 있는지 없는지를 체크할 수가 있나? 일반화시키면, $2^k$의 비트가 켜져있는건 $\mod 2^{k+1}$ 에 대해 나눈 애들의 합에 대해 $0 \leq s < 2^k$ 또는 $2^{k+1} \leq s < 2^{k+1} + 2^k$ 인게 있으면 안된다. 이걸 각 비트에 대해 한다고 하면 그래도 정렬해서 이분탐색으로 구할 순 있을거같긴 한데…… $N$ 제한이 100만이라 $O(29 \times N\log{N})$을 하면 죽여버리겠다는 말과 같은 것 같다. 어? 근데 내가 필요한건, 비트단위로 하나씩 확장해나가면서 정렬하는거다. 이게 바로 Radix Sort 아닌가? 게다가 배열 두개로 쪼개져있을때, 다른 배열에서 하나하나 합이 저 안에 들어있는지 확인하는건 그리디하게 0/1로 쪼개진 두 배열의 맨앞/맨뒤를 보는것만으로 해결할 수 있는 것 같다. 덱을 이용해서 관리해보자. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; vector<ll> A(N), B(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) cin >> B[i]; vector<ll> bitCountA(30), bitCountB(30); rep(i, 0, N) rep(j, 0, 30){ if((A[i] >> j) & 1) bitCountA[j]++; if((B[i] >> j) & 1) bitCountB[j]++; } ll ans1 = 0; rep(i, 0, 30){ ans1 += (1LL << i) % 1999 * (bitCountA[i] * bitCountB[i]) % 1999; ans1 %= 1999; } cout << ans1 << " "; ll ans2 = 0; vector<ll> dq[2], ndq[2]; dq[0].reserve(N); dq[1].reserve(N); ndq[0].reserve(N); ndq[1].reserve(N); rep(i, 0, N) dq[0].push_back(A[i]); rep(bit, 0, 30){ ndq[0].clear(); ndq[1].clear(); for(ll x: dq[0]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x); for(ll x: dq[1]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x); swap(dq[0], ndq[0]); swap(dq[1], ndq[1]); vector<ll> cand; if(!dq[0].empty()){ cand.push_back(dq[0].front()); cand.push_back(dq[0].back()); } if(!dq[1].empty()){ cand.push_back(dq[1].front()); cand.push_back(dq[1].back()); } bool flag = true; for(auto x: B) for(auto c: cand) if((((x+c) >> bit) & 1) == 0){ flag = false; break; } if(flag) ans2 += (1LL << bit); } cout << ans2 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17790 번역 문제 # 무방향 단순 그래프 G = (V, E)에 대해, V’ ⊆ V인 부분집합 V’를 독립 집합(independent set)이라고 부르는 것은 V’의 어떤 두 원소도 간선으로 연결되어 있지 않을 때입니다. G의 독립 집합을 최대 독립 집합(maximum independent set)이라고 부르는 것은 G에 그보다 엄격하게 더 많은 정점을 가진 독립 집합이 없을 때입니다. 특정한 종류의 연결된 그래프 G가 주어졌을 때, G의 최대 독립 집합의 크기를 구하세요.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14939 🧐 관찰 및 접근 # 맨 윗줄을 어찌저찌 일처리를 끝냈다고 가정하자. 두번째 줄부터, 그 윗줄의 남은 전구를 끄는 방법은 해당 칸 아래의 스위치를 컨트롤 하는 방법이 유일하다. 이를 사용하면 맨 윗줄을 처리할 수 있는 방법 $= 2^{10} = 1024$가지에 대해 해볼 수 있고, 시뮬레이션은 $100 \times 100 = 10000$번으로 충분히 시간 내로 들어온다. 맨 아랫줄에 켜진 전구가 남아있으면 안됨에 유의한다. 💻 풀이 # 코드 (C++): void solve(){ vector<string> board(10); rep(i, 0, 10) cin >> board[i]; int answer = 1e9; rep(bit, 0, 1<<10){ vector<string> cboard = board; int cnt = 0; auto press = [&](int r, int c){ cnt++; cboard[r][c] = (cboard[r][c] == 'O' ? 'X' : 'O'); if(r > 0) cboard[r-1][c] = (cboard[r-1][c] == 'O' ? 'X' : 'O'); if(r < 9) cboard[r+1][c] = (cboard[r+1][c] == 'O' ? 'X' : 'O'); if(c > 0) cboard[r][c-1] = (cboard[r][c-1] == 'O' ? 'X' : 'O'); if(c < 9) cboard[r][c+1] = (cboard[r][c+1] == 'O' ? 'X' : 'O'); }; rep(c, 0, 10) if(bit & (1 << c)) press(0, c); rep(r, 1, 10) rep(c, 0, 10) if(cboard[r-1][c] == 'O') press(r, c); bool ok = true; rep(c, 0, 10) if(cboard[9][c] == 'O') ok = false; if(ok) answer = min(answer, cnt); } if(answer == 1e9) cout << -1 << '\n'; else cout << answer << '\n'; } 🔒 구현 코드 잠금