けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 356 B - Nutrients (6Q, 灰色, 150 点)

二次元配列の練習問題!

問題概要

 M 種類の栄養素があり、 i 番目の栄養素を  A_{i} g 以上摂取したい。

そこで、 N 個の食品を食べる。 i 番目の食品を食べると、栄養素  j X_{i, j} g 摂取できる。

この  N 個の食品を食べることで、 M 種類すべての栄養素を必要量以上に摂取できるかどうかを判定せよ。

解法

問題文中の  X の情報は、 N \times M のグリッド情報だと捉えることができる。たとえば、サンプル 1 を見ると  N = 2 M = 3 であり、 X は次のような 2 × 3 の情報と見ることができる。

20 0 10
0 100 100

また、 A は次のように  N 個の値からなる情報である。

10 20 30

この問題のやりたいことは、 X の各列  j について縦に足していき、その総和が  A_{j} 以上かどうかを確かめることである。

for 文を用いて次のように実装できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> A(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    vector X(N, vector(M, 0LL));
    for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> X[i][j];
    
    bool res = true;
    for (int j = 0; j < M; ++j) {
        long long sum = 0;
        for (int i = 0; i < N; ++i) sum += X[i][j];
        if (sum < A[j]) res = false;
    }
    
    cout << (res ? "Yes" : "No") << endl;
}