【AtCoder】ABC 420 B - Most Minority | 緑コーダーが解くAtCoder

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 74 / NoviSteps: 5Q

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 人が $M$ 回の0か1かを選択する投票を行った。各人の各回の投票は $N$ 個の長さ $M$ の0, 1からなる文字列 $S_1,S_2,\dots,S_N$ として与えられ、 $S_{i, j}$ は人 $i$ の $j$ 回目の投票への内容を表す。

各回の投票では、次のルールで得点が与えられる。

その回の投票で0を選択した人が人、1を選択した人が人いたとする。
- $x=0$ または $y=0$ のとき : その投票では全員に $1$ 点が与えられる。
- そうでなく $x \lt y$ のとき : その投票で0に投票した人のみに $1$ 点が与えられる。
- そうでないとき : その投票で1に投票した人のみに $1$ 点が与えられる。

$M$ 回の投票を終えた後、それらの投票における合計の得点が最も高い人を全員求めよ。

制約

$N$ は $1 \le N \le 99$ を満たす奇数
$M$ は $1 \le M \le 100$ を満たす整数

考察

基本的には問題文の通りにやるだけ。

各回ごとに、 $N$ 人の投票状況を読み取りながら $x, y$ を計算していき、両者の関係によって得点を加算していく。

その後、得点の最大値を求め、その得点を取った人の番号を順に出力する。

実装例

得点の最大値を求める過程で、ranges::max_elementを使っている。

cpprefjp.github.io

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    rep(i, 0, N) cin >> S[i];

    vector<int> points(N, 0);
    rep(j, 0, M)
    {
        int x = 0, y = 0;
        rep(i, 0, N)
        {
            if (S[i][j] == '0')
                x++;
            else
                y++;
        }

        if (x == 0 || y == 0)
        {
            rep(i, 0, N) points[i]++;
        }
        else if (x < y)
        {
            rep(i, 0, N)
            {
                if (S[i][j] == '0')
                    points[i]++;
            }
        }
        else
        {
            rep(i, 0, N)
            {
                if (S[i][j] == '1')
                    points[i]++;
            }
        }
    }

    int max_val = *ranges::max_element(points);
    rep(i, 0, N)
    {
        if (points[i] == max_val)
            cout << i + 1 << " ";
    }
    return 0;
}