競技プログラミング練習記 No.50【ABC112練習】

初回 -> はじめに

ABC112を解きました。
4完です！
4完ですが、D問題はコンテスト時間を超えて解きました。悔しい。

問題	時間	アルゴリズム	実行時間
A	1min	-	7ms
B	3min	-	12ms
C	43min	全探索	16ms
D	75min	約数	6ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

tupleは2つ以上の要素をまとめて管理したいときに便利です。
演算子のオーバーロードのような操作なしでsortもできます。

A - Programming Education

  int n;
  cin >> n;
  if (n == 1)
  {
    cout << "Hello World";
    return;
  }
  int a, b;
  cin >> a >> b;
  cout << a + b;

Nが1の時は出力をして早期returnです。
Nが2の時は追加の入力を受けとって出力しました。
Nは1か2の2通りなので、else句などは必要ありません。

B - Time Limit Exceeded

  int n, t_in, c, t;
  cin >> n >> t_in;
  int ans = 100000;
  for(int i = 0; i < n; ++i)
  {
    cin >> c >> t;
    if (t <= t_in) ans = min(ans, c);
  }
  if (ans == 100000) cout << "TLE";
  else cout << ans;

もらった入力がT以内であれば答えを更新します。
過去や未来の入力は影響しないので、逐次処理できますね。

答えが一度も更新されていなければTLEとの判断をします。

C - Pyramid

ll calcDiff(ll cx, ll cy, ll x, ll y)
{
  return abs(x - cx) + abs(y - cy);
}

void solve()
{
  ll n, x, y, h;
  cin >> n;
  vector<tuple<ll, ll, ll>> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> x >> y >> h;
    a[i] = make_tuple(h, x, y);
  }

  sort(a.rbegin(), a.rend());

  for(ll cx = 0; cx <= 100; ++cx)
  {
    for(ll cy = 0; cy <= 100; ++cy)
    {
      bool ok = true;
      ll ch = calcDiff(cx, cy, get<1>(a[0]), get<2>(a[0])) + get<0>(a[0]);
      for(const auto& t : a)
      {
        ll diff = calcDiff(cx, cy, get<1>(t), get<2>(t));
        ok &= ( ( ch == diff + get<0>(t) ) || (diff > ch && get<0>(t) == 0) );
      }
      if (ok)
      {
        cout << cx << " " << cy << " " << ch;
        return;
      }
    }
  }
}

tupleを使ってみました。
2つ以上の要素をまとめて管理したいときに便利です。
演算子のオーバーロードのような操作なしでsortもできます。

中心地がわかれば高さを求める式からピラミッドの高さがわかりますね。
ただ、入力のhが0の時はうまくいかないので注意です。

また、中心地のX, Y座標はそれぞれ[0, 100]の範囲内です。範囲が狭いので全探索が選択肢に入ります。
中心位置を仮に決めて入力の通りになるか試し、矛盾する点がなければその位置が答えになります。
これは、入力情報でピラミッドの位置が一意に決まるためにできる操作です。

入力数は100以下なので、最大計算量も以下のようになり間に合います。
[Xの候補数] * [Yの候補数] * [入力数] = 101 * 101 * 100 ≈ 10^6

はじめは数学的に考えて、絶対値を外して連立方程式を作って。。。
というようにゴリゴリやっていたのですが、途中で全探索すればいいことに気づきました。
もっとはやく全探索を思いつきたかった。こういうミス(?)が多いので減らしたい。

D - Partition

  ll n, m;
  cin >> n >> m;

  ll ans = 1;
  for(ll i = 1; i * i <= m; ++i)
  {
    if (m % i == 0)
    {
      if (i * n <= m) ans = max(ans, i);
      if (m / i * n <= m) ans = max(ans, m / i);
    }
  }
  cout << ans;

a1,a2,a3,...の最大公約数はMの約数になるので、Mの約数を順にみます。
求める答えは最大でM/Nになるので、Mの約数であってM/N以下の数字が答えになります。

書くのは単純でコードも単純なのですが、気付くのに時間がかかかりました。
約数の問題は得意だと思っていたので、もっと速く解きたかった。。。

以上です。ありがとうございました。