zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC167-C「Skill Up」です。
ポイント
出ました。Atcoderお得意のbit全探索です。bit全探索については以下の記事をご覧ください。
あわせて読みたい
【c++で楽しく実装！】bit全探索
本記事では，bit全探索の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。 目次へジ...
おさえるべき内容
bit全探索の実装方法
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N, M, X;
int C[20];
int A[20][20];
// ansは最大でも12*10^5程度
int ans = 20000000;
int main(){
cin >> N >> M >> X;
rep(i, N){
cin >> C[i];
rep(j, M){
cin >> A[i][j];
}
}
// bit全探索開始
// bitsに順列の情報が入っている
rep(bits, 1<<N){
// flagはどの参考書を選ぶかどうかを表している
bool flag[N];
rep(n, N){
if (bits & (1<<n)) flag[n] = true;
else flag[n] = false;
}
// 各場合分けで必要となる金額を計算する
// flagはboolなので実質0or1とみなせるためそのまま計算に利用
int sums = 0;
rep(i, N){
sums += flag[i] * C[i];
}
// 各アルゴリズムに関する理解度
int Y[20];
rep(i, 20) Y[i] = 0;
rep(i, N){
if (flag[i]){
rep(j, M) Y[j] += A[i][j];
}
}
// 各アルゴリズムに対する理解度がXを全て上回っているかどうかを調べる
bool ok = true;
rep(j, M){
if (Y[j] < X) ok = false;
}
// もし全部上回っていたら最小値を更新する
if (ok) ans = min(ans, sums);
}
// もし最小値が一度も更新されていなければ"-1"を出力する
if (ans == 20000000) cout << "-1" << endl;
// それ以外は最小値を出力する
else cout << ans << endl;
}
コメント