問題の言い換え

整数が $M$ 行 $N$ 列で並んでいる．列の合計値の最大値を求めよ．

解法

各列の合計を計算して，最大値を出力します．計算方法はいくらでもありますが，二次元配列の舐め方を考慮して2通り紹介します．

二次元配列を横に舐める方法

横に舐めるので，入力と同じようにfor文を回して処理します．列を逐次的に処理できないので，列の合計値を保存する配列を作る必要があります．

max_element()は配列の最大値を求める関数です．（#include <algorithm>が必要）

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,m;
    while(cin >> n >> m){
        if(n+m == 0)break;
        vector<vector<int>> v(m, vector<int>(n, 0));
        vector<int> col_sum(n, 0);
        // 入力
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin >> v[i][j];
            }
        }
        // 列の合計値を計算
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                col_sum[j] += v[i][j];
            }
        }
        // 最大値を出力
        cout << *max_element(col_sum.begin(), col_sum.end()) << endl;
    }
}

二次元配列を縦に舐める方法

この方法では列を逐次的に処理できるため，列の合計値を保存する配列が必要ありません．単に前の列から合計を計算して，答えの変数を更新します．

この場合，二次元配列を「縦方向に舐める」感覚が必要になります．C/C++において二次元配列の入力を受けるときには，

for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        // [i][j]で参照

のようにするのが一般的ですが，これは二次元配列を横方向に舐めています．ある行を固定して，列を回します．

一方で，縦方向に回すときには，列を固定して行を回します．コードで言うと，

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        // [j][i]で参照

みたいな感じです（もちろん，この実装は一例です）．

以上を踏まえると，以下のように書けます．

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,m;
    while(cin >> n >> m){
        if(n+m == 0)break;
        vector<vector<int>> v(m, vector<int>(n, 0));
        // 入力
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin >> v[i][j];
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            int score = 0; // i列目の合計が入る
            for(int j=0;j<m;j++){
                score += v[j][i];
            }
            // 最大値を更新
            ans = max(ans, score);
        }
        cout << ans << endl;
    }
}

gotutiyan’s blog

ICPC 2019 国内予選A 「期末試験の成績」解説

問題の言い換え

解法

二次元配列を横に舐める方法

二次元配列を縦に舐める方法