【AtCoder】ABC 349 A - Zero Sum Game | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 25

問題概要

1から [tex; N] の番号が付けられた [tex; N] 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行った。 人は最初にそれぞれ持ち点として0を持っており、各ゲームでは勝者の持ち点が1増え、敗者の持ち点が1減る。なお、持ち点は途中で負になることもあり得る。最終的に人 の持ち点が になったとき、人 の持ち点を求めよ。

制約

• 入力はすべて整数。
• 
• 

考察

A問題にしては長めの問題文である。

サンプルケース1を詳しく見てみよう。各ゲームごとの持ち点の推移を表にしてみた。

ここで注目すべきなのは、「全員の持ち点の総和」だ。上表において、各行ごとの4人の持ち点の総和を取ると全て0になる。

これは決して偶然ではない。各ゲームでは対戦した二人の持ち点が増減するものの、増分の絶対値は等しいため全員の持ち点の総和は変わらないからだ。開始時は全員の持ち点が0なので、無限回ゲームを行って途中どの二人を対戦させたとしても、 人の最終的な持ち点が分かっていれば、残り一人の最終的な持ち点も一意に定まる。

具体的には、人 の最終的な持ち点 は と計算できる。これをループなどを用いて求めていけばよい。

コード

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

using ll = long long;

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

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

int main()
{
    int N;
    cin >> N;

    int ans = 0;
    rep(i, 1, N)
    {
        int A;
        cin >> A;
        ans += A;
    }

    cout << ans * -1 << endl;
}

atcoder.jp

実装時間: 5分以内