【競プロ精進ログ】ABC167-C

zuka

ABCをコツコツ解いていきます。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC167-C「Skill Up」です。

ポイント

出ました。Atcoderお得意のbit全探索です。bit全探索については以下の記事をご覧ください。

おさえるべき内容

 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;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる