トヨタ自動車プログラミングコンテスト 2024#2（AtCoder Beginner Contest 341）の A/B/C 問題の解法 #ABC341

2024-02-19

トヨタ自動車プログラミングコンテスト 2024#2（AtCoder Beginner Contest 341）の A/B/C 問題の解法。

実装はこちら atcoder/abc/301-400/341 · michimani/atcoder 。

A - Print 341

1 のほうが 0 よりひとつ多いので、まず 1 を出力してから 01 を \(N\) 回出力すればよい。

#include <iostream>

using namespace std;
using ui = unsigned int;

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

  cout << 1;
  for (ui i = 0; i < n; i++)
  {
    cout << "01";
  }
  cout << endl;

  return 0;
}

提出 #50329660 - トヨタ自動車プログラミングコンテスト 2024#2（AtCoder Beginner Contest 341）

B - Foreign Exchange

\(i+1\) の通貨単位は単調増加なので、 \(0 \leq i \leq N-1\) の各 \(i\) に対して順に行動を行う。その際、各 \(i\) に対して行動できる回数は \(A_i / S_i\) なので、 \(A_i \lt S_i \) になるまで 1 回ずつ行動するのではなくまとめて行動して \(A_{i+1} \) に \(T_i \times (A_i / S_i)\) を足すようにする。

最終的に \(A_N\) の値は 32 bit の範囲を超える可能性があるので、各 \(A_i\) の値は long long 型で保持する。

#include <iostream>
#include <vector>

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

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

  vector<ull> a(n, 0);
  for (auto &aa : a)
    cin >> aa;

  for (ui i = 0; i < n - 1; i++)
  {
    ull s, t;
    cin >> s >> t;
    a[i + 1] += (t * (a[i] / s));
  }

  cout << a[n - 1] << endl;
  return 0;
}

提出 #50396329 - トヨタ自動車プログラミングコンテスト 2024#2（AtCoder Beginner Contest 341）

C - Takahashi Gets Lost

\(S_1, \dots, S_H\) を読み込みつつ陸地になっている座標を記録していく。その後、すべての陸地に対してそこをスタート地点として \(T\) で与えられて移動が最後まで可能かを判定する。途中で海に到達した際には早期リターンできる。また、問題の制約上グリッドの外周はすべて海であることから、早期リターンすることにより \(T\) による移動中に \(H, W\) の範囲外に到達することはない。

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;

int main()
{
  ui h, w, n;
  cin >> h >> w >> n;

  string t;
  cin >> t;

  vector<pair<ui, ui>> riku;

  vector<vector<char>> g(h, vector<char>(w));
  for (ui i = 0; i < h; i++)
  {
    for (ui j = 0; j < w; j++)
    {
      cin >> g[i][j];
      if (g[i][j] == '.')
        riku.push_back({i, j});
    }
  }

  ui ans = 0;
  int sh = 0, sw = 0;
  bool ok = false;
  for (auto &r : riku)
  {
    ok = true;
    sh = int(r.first);
    sw = int(r.second);
    for (auto &d : t)
    {
      if (d == 'L')
      {
        sw--;
      }
      else if (d == 'R')
      {
        sw++;
      }
      else if (d == 'U')
      {
        sh--;
      }
      else if (d == 'D')
      {
        sh++;
      }
      else
      {
        // noop
      }

      if (g[ui(sh)][ui(sw)] == '#')
      {
        ok = false;
        break;
      }
    }

    ans += ui(ok);
  }

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