AtCoder Beginner Contest 419 の A/B/C 問題の解法 #ABC419

2025-08-26

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

実装はこちら atcoder/abc/401-500/419 · michimani/atcoder 。

A - AtCoder Language

与えられた文字列を特定のAtCoderish言語に翻訳する問題。“red"→"SSS”、“blue"→"FFF”、“green"→"MMM"の3つの翻訳ルールがあり、それ以外は"Unknown"を出力する。

実装では map を使って文字列と対応する出力をマッピングし、入力文字列が存在する場合は対応する値を、存在しない場合は "Unknown" を出力する。

#include <iostream>
#include <map>

using namespace std;

int main()
{
  string s;
  cin >> s;

  map<string, string> c = {
      {"red", "SSS"},
      {"blue", "FFF"},
      {"green", "MMM"},
  };

  if (c.count(s) > 0)
    cout << c[s] << endl;
  else
    cout << "Unknown" << endl;

  return 0;
}

B - Get Min

整数値のボールを入れる袋（バッグ）に対して、ボールの追加と最小値の取得・削除を繰り返すクエリ処理問題。

実装では map を使って各値の出現回数を管理している。これにより重複する値を効率的に扱える。クエリ1では値を追加して出現回数を増やし、クエリ2では最小値（map の最初の要素）を出力して出現回数を減らす。出現回数が0になった場合は map から削除する。

priority_queue や multiset を使う方法もあるが、map を使うことで値の管理と最小値の取得を両方効率的に行える。

#include <iostream>
#include <map>

using namespace std;
using ui = unsigned int;

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

  map<ui, ui> bc;
  ui c = 0, x = 0;
  for (; q--;)
  {
    cin >> c;

    switch (c)
    {
    case 1:
      cin >> x;
      bc[x]++;

      break;

    case 2:
      x = bc.begin()->first;
      cout << x << endl;

      bc[x]--;
      if (bc[x] == 0)
        bc.erase(x);
      break;

    default:
      // noop
      break;
    }
  }

  return 0;
}

C - King’s Summit

実際の問題は「\(N\) 人が格子上で8方向に移動できるとき、全員が同じ位置に集合するのに必要な最小時間を求める」というもの。

この問題を解くために、実装では以下のように解釈している：

最適な集合地点は、全員の座標の中央付近
各人は8方向に移動でき、チェビシェフ距離で移動時間が決まる
最適解は、各座標軸での最小値と最大値の中点を集合地点とした場合

各点の \(x\) 座標と \(y\) 座標をそれぞれソートし、最小値と最大値を求める。正方形の中心を各座標の中点とし、中心から最も遠い点までの距離（チェビシェフ距離）を求める。これが全員が集合するのに必要な最小時間となる。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ui = unsigned int;

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

  vector<ui> r(n);
  vector<ui> c(n);

  for (ui i = 0; i < n; i++)
    cin >> r[i] >> c[i];

  sort(r.begin(), r.end());
  sort(c.begin(), c.end());

  ui tr = (r[0] + r[n - 1]) / 2;
  ui tc = (c[0] + c[n - 1]) / 2;

  ui ans = max(
      max(tr - r[0], r[n - 1] - tr),
      max(tc - c[0], c[n - 1] - tc));

  cout << ans << endl;

  return 0;
}

Tags for this post: AtCoder C++

comments powered by Disqus

Prev: AtCoder Beginner Contest 416 の A/B/C/D 問題の解法 #ABC416