AtCoder Beginner Contest 194 の A/B/C 問題の解法 #ABC194

AtCoder Beginner Contest 194 - AtCoder の A/B/C 問題の解法。

実装はこちら atcoder/abc/101-200/194 · michimani/atcoder 。

A - I Scream

A - I Scream

問題文通りの条件分岐をすればよい。

#include <iostream>

using namespace std;
using ui = unsigned int;

int main()
{
  ui a, b;
  cin >> a >> b;

  if (a + b >= 15 && b >= 8)
    cout << 1 << endl;
  else if (a + b >= 10 && b >= 3)
    cout << 2 << endl;
  else if (a + b >= 3)
    cout << 3 << endl;
  else
    cout << 4 << endl;

  return 0;
}

提出 #52919007 - AtCoder Beginner Contest 194

B - Job Assignment

B - Job Assignment

仕事 \(A、B\) を同じ人が行う場合と、別の人が行う場合のそれぞれの最小値を計算し、それらのうち小さい方を出力する。

同じ人が行う場合の最小値は、各 \(A_i、 B_i\) の入力を受け取りつつ \(\min(A_i + B_i)\) を計算しておく。

別の人が行う場合の最小値は、 \(1 \leq i \leq N, 1 \leq j \leq N、 i \neq j\) について、 \(\min(\max(A_i, B_j))\) を計算する。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using ui = unsigned int;

int main()
{
  ui n;
  cin >> n;
  vector<pair<ui, ui>> ab(n);

  ui same = 200000;
  for (auto &c : ab)
  {
    cin >> c.first >> c.second;
    same = min(same, c.first + c.second);
  }

  ui diff = 200000;
  for (ui i = 0; i < n; i++)
  {
    for (ui j = 0; j < n; j++)
    {
      if (i == j)
        continue;

      diff = min(diff, max(ab[i].first, ab[j].second));
    }
  }

  cout << min(same, diff) << endl;
  return 0;
}

提出 #52918861 - AtCoder Beginner Contest 194

C - Squared Error

C - Squared Error

問題文の計算式を変形することで、 \(O(N)\) で計算できるようになる。 変形は下記の通り。

$$ \begin{align} \sum_{i=2}^{N} \sum_{j=1}^{i-1} \left( A_i - A_j \right)^2 &= \sum_{i=2}^{N} \sum_{j=1}^{i-1} \left( A_i^2 + A_j^2 - 2 A_i A_j \right) \\ &= \frac{1}{2} \bigg( \sum_{i=1}^{N} \sum_{j=1}^{N} \left( A_i^2 + A_j^2 - 2 A_i A_j \right) \bigg) \\ &= \frac{1}{2} \bigg( \sum_{i=1}^{N} \sum_{j=1}^{N} A_i^2 + \sum_{i=1}^{N} \sum_{j=1}^{N} A_j^2 - 2 \sum_{i=1}^{N} \sum_{j=1}^{N} A_i A_j \bigg) \\ &= \frac{1}{2} \bigg( N \sum_{i=1}^{N} A_i^2 + N \sum_{j=1}^{N} A_j^2 - 2 \sum_{i=1}^{N} \sum_{j=1}^{N} A_i A_j \bigg) \\ &= \frac{1}{2} \bigg( 2N \sum_{i=1}^{N} A_i^2 - 2 \sum_{i=1}^{N} \sum_{j=1}^{N} A_i A_j \bigg) \\ &= N \sum_{i=1}^{N} A_i^2 - \sum_{i=1}^{N} \sum_{j=1}^{N} A_i A_j \\ &= N \sum_{i=1}^{N} A_i^2 - \sum_{i=1}^{N}\bigg( A_i \sum_{j=1}^{N} A_j \bigg) \\ &= N \sum_{i=1}^{N} A_i^2 - \bigg( \sum_{i=1}^{N} A_i \bigg)^2 \\ \end{align} $$

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;

int main()
{
  ui n;
  cin >> n;

  ull a2sum = 0;
  ll asum = 0;
  for (ui i = 0; i < n; i++)
  {
    ll a;
    cin >> a;
    a2sum += ull(a * a);
    asum += a;
  }

  ull ans = ull(n) * a2sum - ull(asum * asum);

  cout << ans << endl;
  return 0;
}

提出 #52918551 - AtCoder Beginner Contest 194