ABC167に参加してみました
初めに
今回はABC167に参加しましたが、今回もCを解いている途中でタイムアップしました。。。
（全探索すれば解けるとは思ったんですがTLEになっていまいました。）
なので、今回もC問題について書いて行こうと思います。
https://atcoder.jp/contests/abc167
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Skill Up
この問題は、本屋でそれぞれCi円で売られているN冊の参考書よりM個のアルゴリズムを学び、
それぞれの理解度(Aij)をX以上にするために必要な金額の最小値を出力する問題です。
初めの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,bool> Pair;
int main(){
ll N,M,X;
ll tot = 0;
ll ans = INF;
cin >> N >> M >> X;
vector<ll> a(M);
vector<ll> C(N);
vector<vector<ll>> A(N,vector<ll>(M));
for(ll i = 0;i < N;++i){
cin >> C[i];
for(ll j = 0;j < M;++j) cin >> A[i][j];
}
//順列の生成用配列
vector<ll> v;
//順列の生成用配列に0～Nの値を格納
for(ll i = 0; i < N;++i) v.push_back(i);
do{
// 初期化します
tot = 0;
for(ll i = 0; i < M;++i) a[i] = 0;
for(ll i = 0; i < N;++i){
// 各アルゴリズムの理解度が条件を満たしているか否かを判断するフラグ
bool flg = true;
//購入費を加算します
tot = tot + C[v[i]];
for(ll j = 0; j < M;++j){
// 理解度を加算します
a[j] += A[v[i]][j];
// 各アルゴリズムの理解度がXより小さい場合はflgをfalseにします
if(a[j] < X) flg = false;
}
// 各アルゴリズムの理解度がX以上である場合は購入費の更新をします
if(flg){
ans = std::min(ans,tot);
break;
}
}
// 順列を列挙
}while(next_permutation(v.begin(),v.end()));
// 購入費が初期値から購入されているか判定
if(ans == INF) cout << "-1" << endl;
else cout << ans << endl;
return 0;
}
本を選択するパターンを順列で列挙(next_permutation)しています。
N冊の本をすべて購入しなくても理解度がX以上になるパターンが存在するため、
すべてのアルゴリズムの理解度がX以上になった際に購入費(ans)を更新しループを抜けるようにしています。
そして、最後に購入費が初期値から更新されているかを判定し計算結果を出力しています。
このプログラムだとNの最大値である12が入力された場合は12!通りのパターンに対して、
条件を満たすか確認が必要があるため、TLEになっていたものと思います。
(TLEになるだろうなとは思いつつこの方法しか浮かばなかった、、、)
next_permutation - cpprefjp C++日本語リファレンス
解説を見てからの回答
順列でもすべてのパターンを列挙可能ですが、そもそも順番は気にする必要が無いため
組み合わせのパターンを列挙すれば良いので、下記のように書くことが出来ます。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
int main(){
ll N,M,X;
ll tot = 0;
ll ans = INF;
cin >> N >> M >> X;
vector<vector<ll>> A(N,vector<ll>(M));
vector<ll> C(N);
for(ll i = 0;i < N;++i){
cin >> C[i];
for(ll j = 0;j < M;++j) cin >> A[i][j];
}
// (1<<N)で1を左にNビットシフトする(N=3だった場合：0001(1) → 1000(8))
for(ll i = 0;i < (1<<N);++i){
tot = 0;
vector<ll> a(M);
for(ll j = 0;j < N;++j){
// (i>>j)でiを右にjビットシフトする(i=6,j=1だった場合：0110(5) → 0011(3) ＆ 0001(1) = 0001)
if((i>>j)&1){
tot = tot + C[j];
for(ll k = 0;k < M;++k) a[k] += A[j][k];
}
}
bool flg = true;
for(ll j = 0;j < M;++j) if(a[j] < X) flg = false;
if(flg) ans = std::min(ans,tot);
}
if(ans == INF) cout << "-1" << endl;
else cout << ans << endl;
return 0;
}
10進数の数字を2進数で表すと以下のように1と0で表すことが出来ます。
1 → 0001
2 → 0010
3 → 0011
4 → 0100
・
・
・
1を「購入する」、0を「購入しない」とし、さらに下記のイメージのように2進数のそれぞれの桁を本のN番目と見立てます。
下記のように見立てることで、それぞれの桁数の値を確認することで、
本を購入する組み合わせを列挙することが出来ます。
それぞれ桁の値を確認する際は、確認する桁数分だけ右にビットシフトし1との論理和を
計算することで確認することが出来ます。
例 ) 0110(5)の3桁目の値を確認する場合
0110(5)を2ビットずらし、0001(1)との論理和を計算します。
0001(1) & 0001(1) = 0001
この方法であれば、最大で212通りのパターンを列挙して条件を満たすか確認すれば良いので、
最初に考えて方法より計算量がかなり少なく計算できますね。
最後に
今回の問題は、解釈を間違えて効率的な全探索を行う事ができませんでしたが、
bit全探索という新たな探索方法の知識を得られたのは良かったかなと思います。
まだまだ勉強が必要ですね。。。
