s8pc_4_b
WAの嵐
bit探索で1を対象のビルとして左から順に探索するだけ。
1のビルの時しかpre_maxを更新していなかったので
N=3,K=4
a={1, 10000, 2, 3}
のようなテストケースを逃していて大量WA
あと最初はlong longも忘れてた
#include<bits/stdc++.h>
using namespace std;
int n, k;
long long int a[22];
int bit_cnt(int bit){
int cnt = 0;
for(;bit;bit&=(bit-1)) cnt++;
return cnt;
}
int main(){
cin >> n >> k;
for(int i=0;i<n;i++) cin >> a[i];
long long int ans = (1LL<<60LL);
for(int i=0;i<(1<<n);i++){
if(bit_cnt(i) < k) continue;
long long int p = 0;
long long int pre = a[0];
for(int j=1;j<n;j++){
if( (i&(1<<j))){
if(a[j] <= pre){
p += (pre - a[j] + 1);
pre = max(pre, a[j]) + 1;
}
}
pre = max(pre, a[j]);
}
ans = min(ans, p);
}
cout << ans << endl;
}
joi2008yo_e
問題だけ読んでほったらかしてたら急に解法が降ってきた。
例のごとく000...000 ~ 111...111までのbitでR列目をひっくり返した場合にどうなるかをC行に試す全探索を行う。
C行目は独自にひっくり返せれるのでmax(1のbit数, 0のbit数)を考えればよい。
すぐに分かったけどRとCがごっちゃになってWA出しまくった。。。
#include<bits/stdc++.h>
using namespace std;
int r, c;
int a[11][11111];
int b[11111];
int cnt_bit(int bit){
int cnt = 0;
for(;bit;bit&=(bit-1)) cnt++;
return cnt;
}
int main(){
cin >> r >> c;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) cin >> a[i][j];
for(int j=0;j<c;j++){
for(int i=0;i<r;i++){
b[j] = b[j] << 1;
b[j] |= a[i][j];
}
}
int ans = 0;
for(int i=0;i<(1<<r);i++){
int num = 0;
for(int j=0;j<c;j++){
int p = b[j] ^ i;
int cnt = cnt_bit(p);
num += max(cnt, r-cnt);
}
ans = max(ans, num);
}
cout << ans << endl;
}
abc002_4
結構苦労した.
グループとなり得るパターンはn人をそれぞれbitのi番目に存在するか否かで考えると0000....000から1111....1111の2^nで表せれる
あとは適当な2人がグループのパターンに沿っている かつ 知り合いならばok
違うならngという感じで探していく
最大クリーク問題を求める問題を考えることと同じらしい
(無向グラフの中で最大な完全グラフを探し出す問題)
関係ないけれども完全グラフといえばヨビノリさんのこれが好き
#include<bits/stdc++.h>
using namespace std;
int n, m;
bool p[22][22];
int main(){
cin >> n >> m;
for(int i=0;i<m;i++){
int x, y;
cin >> x >> y;
x--; y--;
p[x][y] = p[y][x] = true;
}
int ans = 0;
for(int i=0;i<(1<<n);i++){
int bit = i;
bool flg = true;
for(int j=0;j<n;j++){
for(int k=j+1;k<n;k++){
if(((bit>>j)&1) && ( (bit>>k)&1) && !p[j][k]) flg = false;
}
}
int cnt = 0;
if(flg){
for(;bit;bit&=(bit-1)) cnt++;
}
ans = max(ans, cnt);
}
cout << ans << endl;
}
abc128_c
電球M[i]に使うスイッチをビットで管理する
スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント
カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯
そういえば今回は書かなかったけどビットカウントをするときは
for(int i=bit; i; i&=(i-1) ) cnt++;
ってやるとスマート
#include<bits/stdc++.h>
using namespace std;
int n, m;
int s[19];
int p[19];
int ret_cnt(int x){
int ret = 0;
while(x){
ret += (x&1);
x = (x>>1);
}
return ret;
}
int main(){
cin >> n >> m;
for(int i=0;i<m;i++){
int k;
cin >> k;
for(int j=0;j<k;j++){
int ss;
cin >> ss;
s[i] |= (1<<(ss-1));
}
}
for(int i=0;i<m;i++) cin >> p[i];
int ans = 0;
for(int i=0;i<(1<<n);i++){
bool flg = true;
for(int j=0;j<m;j++){
int cnt = ret_cnt( (i&s[j]) );
if(p[j] != cnt%2) flg = false;
//cout << cnt << endl;
}
if(flg) ans++;
}
cout << ans << endl;
}
abc128_c
電球M[i]に使うスイッチをビットで管理する
スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント
カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯
そういえば今回は書かなかったけどビットカウントをするときは
for( i=bit; i; i&=(i-1) ) cnt++;
ってやるとスマート
#include<bits/stdc++.h>
using namespace std;
int n, m;
int s[19];
int p[19];
int ret_cnt(int x){
int ret = 0;
while(x){
ret += (x&1);
x = (x>>1);
}
return ret;
}
int main(){
cin >> n >> m;
for(int i=0;i<m;i++){
int k;
cin >> k;
for(int j=0;j<k;j++){
int ss;
cin >> ss;
s[i] |= (1<<(ss-1));
}
}
for(int i=0;i<m;i++) cin >> p[i];
int ans = 0;
for(int i=0;i<(1<<n);i++){
bool flg = true;
for(int j=0;j<m;j++){
if(p[j] != cnt%2) flg = false;
//cout << cnt << endl;
}
if(flg) ans++;
}
cout << ans << endl;
}
*1:i&s[j]
ALDS1_5_A
bit全探索
毎クエリ計算しているとTLEになるのでクエリの外で前計算してテーブルに持たせておいて,各クエリの処理はテーブルを参照する
クエリ処理は気をつけよう…(反省)
#include<bits/stdc++.h>
using namespace std;
int n;
int q;
int a[29];
map < int, bool > mp;
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<(1<<n);i++){
int sum = 0;
for(int j=0;j<n;j++){
}
mp[sum] = true;
}
cin >> q;
while(q--){
int m;
cin >> m;
if(mp[m] == 1) puts("yes");
else puts("no");
}
}
*1:i&(1<<j
joi2008yo_d
これと同じ感じ
気が付けば過去問精選100問の工夫して通り数を減らす全列挙まで終了
#include<bits/stdc++.h>
using namespace std;
int m, n;
map < pair<int, int >, bool > np;
int main(){
cin >> m;
for(int i=0;i<m;i++){
int x, y;
cin >> x >> y;
}
cin >> n;
for(int i=0;i<n;i++){
int x, y;
cin >> x >> y;
vn.push_back( make_pair(x, y) );
np[vn[i]] = true;
}
for(int i=0;i<n;i++){
int cnt = 0;
for(int j=0;j<m;j++){
}
if(cnt == m){
cout << dx << " " << dy << endl;
break;
}
}
}
