AtCoder Beginner Contest 060 の A/B/C 問題の解法 #ABC060

2024-01-25

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

実装はこちら atcoder/abc/001-100/060 · michimani/atcoder

A - Shiritori

$A$ の末尾と $B$ の先頭、 $B$ の末尾と $C$ の先頭がそれぞれ同じ文字かどうかを判定する。

#include <iostream>

using namespace std;

int main()
{
  string a, b, c;
  cin >> a >> b >> c;

  if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0])
  {
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }

  return 0;
}

提出 #49652307 - AtCoder Beginner Contest 060

B - Choose Integers

整数 $x, y, z$ について、「 $x$ を $y$ で割ったあまりが $z$ になる」ことと「 $x - z$ を $y$ で割ったあまりが $0$ である」ことは同値である。

今回の問題では $x$ を $A$ の倍数と考えるので、 $A \times i - C$ を $B$ で割ったあまりが 0 になる $i$ が存在するかどうかを見つける問題となる。

$i = 1, 2, 3, \dots$ と確認していく際の $A \times i - C$ を $B$ で割ったあまりを $r_{i}$ とすると、答えが YES となるような入力についてはどこかのタイミングで $r_{i} = 0$ となる。答えが NO となるような入力については、 $r_{i}$ の現れ方が周期的になる。つまり、 $r_{i} = r_{j}$ 且つ $r_{i + 1} = r_{j + 1}$ となるような $i, j (i < j)$ が存在する。このような $i, j$ が現れた時点で答えは NO となる。

#include <iostream>
#include <map>
#include <vector>

using namespace std;
using ui = unsigned int;

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

  map<ui, ui> rm;
  vector<ui> rv;

  ui x = 1;
  ui pr = 0;
  bool exists = false;
  while (true)
  {
    ui r = (a * x - c) % b;
    if (r == 0)
    {
      cout << "YES" << endl;
      return 0;
    }

    if (rm.count(r) > 0)
    {
      if (exists && rv[rm[r] - 1] == pr)
      {
        cout << "NO" << endl;
        return 0;
      }
      exists = true;
    }
    else
    {
      exists = false;
    }

    rv.push_back(r);
    rm[r] = rv.size() - 1;
    pr = r;
    x++;
  }

  return 0;
}

提出 #49652242 - AtCoder Beginner Contest 060

C - Sentou

$t_{i} (1 \leq i \leq N)$ は 1 人目の人がスイッチを押してからの経過時間なので、単純に $i$ 人目の人がスイッチを押した時刻と考えられる。

$i + 1$ 人目の人がスイッチを押した時刻と $i$ 人目の人がスイッチを押した時刻の差が $T$ 未満の場合、まだシャワーが出ている状態であり、 $T$ 以上の場合はシャワーが止まっている状態となる。

シャワーが出ている状態でスイッチを押すと、既に出ているシャワーの残り時間を無視してその時点から $T$ 秒間シャワーが出ることになるので、シャワーが出ている合計時間としては重複している分だけ短くなる。具体的には、 $t_{i + 1} - t_{i}$ 分だけ合計時間が加算されることになる。

スイッチが押されていない状態では、 $t_{i + 1} - t_{i} >= T$ となるので、合計時間としては $min (T, t_{i + 1} - t_{i})$ を加算していけばよい。

#include <iostream>
#include <cmath>

using namespace std;
using ui = unsigned int;

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

  ui ans = t;
  ui prev = 0;
  for (ui i = 0; i < n; i++)
  {
    ui tt;
    cin >> tt;

    ans += min(t, tt - prev);

    prev = tt;
  }

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

提出 #49634392 - AtCoder Beginner Contest 060

Tags for this post: AtCoder C++

Prev: AtCoder Beginner Contest 043 の A/B/C 問題の解法 #ABC043

Next: パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) の A/B/C 問題の解法 #ABC231