AtCoder ABC 323 C - World Tour Finals (灰色, 250 点)

1 つ 1 つの要素は難しくないが、実装がとにかく重たい！落ち着いて整理して考えたい問題。

• 問題へのリンク

問題概要

プレイヤー が、配点が である 個の問題からなるコンテストに挑んでいる。なお、 は 以上 以下の の倍数である。

プレイヤー には最初から 点のボーナスがついており、コンテスト開始から解けた問題の配点の分だけ得点が積み上がる。

プレイヤー が現在解けている問題を表す情報は長さ の文字列 で表される。 文字目が o ならば問題 が解けていて、x ならば問題 が解けていないことを表す。

各プレイヤー について、まだ解けてない問題のうち、仮に最小で何問解けば、全体の中で単独トップになるかを求めよ。

制約

• 

考えたこと

まず最初に、各プレイヤー の現在の得点を求めよう。それを score[i] とする。

各プレイヤー に対して、次の手順で答えが求められる。一歩一歩のステップはさほど難しくないが、とにかくステップが多くて実装が重たい！

---

• 部分問題 1：プレイヤー が単独トップになるために、あと何点必要かを求める ( 点とする)
• 部分問題 2：プレイヤー がまだ解いていない問題の集合を把握する (配点が高い順に とする
• 部分問題 3：プレイヤー が を順に足していき、はじめて 点以上となるまでに足す個数を求める

---

これら部分問題は、単独で出題されれば ABC の A 問題や B 問題でよく見かけるような問題だ。ここまでちゃんと問題を分解できれば、あとはそれぞれを実装するだけだ。

今回はこれらが組み合わさり、重ための C 問題となっている。

コード

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

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    vector<string> S(N);
    vector<int> score(N, 0);  // 人 i のスコア
    for (int i = 0; i < N; ++i) {
        score[i] += i + 1;  // ボーナス点
        cin >> S[i];
        for (int j = 0; j < M; ++j) if (S[i][j] == 'o') score[i] += A[j];
    }
 
    // 人 0, 1, ..., N-1 について
    for (int i = 0; i < N; ++i) {
        // トップになるのにあと何点必要か
        int need = 0;
        for (int j = 0; j < N; ++j) {
            if (j == i) continue;
            need = max(need, score[j] + 1 - score[i]);
        }
        
        // 人 1 が解いていない問題の得点を大きい順に並び替える
        vector<int> mada;
        for (int j = 0; j < M; ++j) if (S[i][j] == 'x') mada.push_back(A[j]);
        sort(mada.begin(), mada.end(), greater<int>());
        
        // 残り必要得点を充足するまで、解いていく
        int res = 0;
        for (int j = 0; j < mada.size() && need > 0; ++j) {
            need -= mada[j];
            ++res;
        }
        cout << res << endl;
    }
}