AtCoder Beginner Contest 335（Sponsored by Mynavi） #ABC335

2024-01-07

AtCoder Beginner Contest 335（Sponsored by Mynavi）の A/B/C/D 問題の解法。

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

A - 202<s>3</s>

入力された文字列の最後の文字を 4 に置き換えて出力する。

#include <iostream>

using namespace std;

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

  s[s.length() - 1] = '4';
  cout << s << endl;
  return 0;
}

提出 #49126459 - AtCoder Beginner Contest 335（Sponsored by Mynavi）

B - Tetrahedral Number

\(x,y,z\) それぞれについて \(1 \leq x,y,z \leq N\) の三重ループを回して、条件を満たす組み合わせを出力する。辞書順が条件となっているが、 \(x,y,z\) の順にループを組めば辞書順になる。

#include <iostream>

using namespace std;
using ui = unsigned int;

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

  for (ui x = 0; x <= n; x++)
  {
    for (ui y = 0; y <= n; y++)
    {
      for (ui z = 0; z <= n; z++)
      {
        if (x + y + z <= n)
        {
          cout << x << " " << y << " " << z << endl;
        }
      }
    }
  }

  return 0;
}

提出 #49126424 - AtCoder Beginner Contest 335（Sponsored by Mynavi）

C - Loong Tracking

長さ \(N\) の配列にそれぞれ \(x,y\) の値を保持するようにする。

頭の位置を移動させるたびに、新しい頭の位置を配列の末尾から先頭に向かうように更新する。指定されたパーツの座標を出力する際は、それまでに頭を移動させた回数から、配列の中での対象パーツの位置を計算して出力する。

#include <iostream>
#include <vector>

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

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

  vector<vector<ll>> p(n, vector<ll>(2, 0));
  for (ui i = 0; i < n; i++)
  {
    p[i][0] = ll(i + 1);
  }

  ui move = 0;
  for (ui i = 0; i < q; i++)
  {
    ui k;
    string c;
    cin >> k >> c;

    if (k == 1)
    {
      ui head_idx = (n - move) % n;
      ll new_x = p[head_idx][0];
      ll new_y = p[head_idx][1];
      if (c == "R")
      {
        new_x++;
      }
      else if (c == "L")
      {
        new_x--;
      }
      else if (c == "U")
      {
        new_y++;
      }
      else if (c == "D")
      {
        new_y--;
      }
      else
      {
        // noop
      }

      ui new_head_idx = (head_idx + n - 1) % n;
      p[new_head_idx][0] = new_x;
      p[new_head_idx][1] = new_y;
      move = (move + 1) % n;
    }
    else
    {
      ui org_idx = ui(stoi(c)) - 1;
      cout << p[(org_idx + n - move) % n][0] << " " << p[(org_idx + n - move) % n][1] << endl;
    }
  }

  return 0;
}

提出 #49117713 - AtCoder Beginner Contest 335（Sponsored by Mynavi）

D - Loong and Takahashi

\(N \times N\) の行列を配列で用意して、 \((1,1)\) から時計回りに渦を巻くように \(N^2 - 1\) 個の値を埋めていく。 \(N^2 - 1\) 番目の値のみ T とする。

渦巻き状に値を配置する方法はいくつかありそうだが、今回は下記のように実装した。

用意する配列は \(N+2 \times N+2\) として、一番外の一周は番兵とした。

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;

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

  vector<vector<string>> g(n + 2, vector<string>(n + 2, "_"));
  for (ui i = 0; i <= n + 1; i++)
  {
    for (ui j = 0; j <= n + 1; j++)
    {
      if (i == 0 || i == n + 1 || j == 0 || j == n + 1)
      {
        g[i][j] = "x";
      }
    }
  }

  ui x = 1, y = 1;
  g[1][1] = "1";
  for (ui m = 1; m <= n * n - 1; m++)
  {
    if (g[y][x + 1] == "_" && g[y + 1][x] == "_")
    {
      x++;
    }
    else if (g[y + 1][x] == "_" && g[y][x - 1] == "_")
    {
      y++;
    }
    else if (g[y][x - 1] == "_" && g[y - 1][x] == "_")
    {
      x--;
    }
    else if (g[y - 1][x] == "_" && g[y][x + 1] == "_")
    {
      y--;
    }
    else if (g[y][x + 1] == "_")
    {
      x++;
    }
    else if (g[y + 1][x] == "_")
    {
      y++;
    }
    else if (g[y][x - 1] == "_")
    {
      x--;
    }
    else if (g[y - 1][x] == "_")
    {
      y--;
    }

    string s = to_string(m + 1);
    if (m == n * n - 1)
    {
      s = "T";
    }

    g[y][x] = s;
  }

  for (ui i = 1; i <= n; i++)
  {
    for (ui j = 1; j <= n; j++)
    {
      if (j > 1)
      {
        cout << " ";
      }
      cout << g[i][j];
    }
    cout << endl;
  }

  return 0;
}