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

2024-03-10

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

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

A - Spoiler

| に挟まれている区間かどうかをもつ boolean の変数 bool ex を用意する。

\(S\) の先頭から一文字ずつ見ていき、 | が現れたら ex の値を反転して continue する。 ex == false のときだけその時の文字を出力する。

#include <iostream>

using namespace std;

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

  bool ex = false;
  for (auto c : s)
  {
    if (c == '|')
    {
      ex = !ex;
      continue;
    }

    if (!ex)
      cout << c;
  }

  cout << endl;
  return 0;
}

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

B - Delimiter

\(N\) の値がわからないので、無限ループで入力を受け取り、 0 が入力されたら break する。

入力された値を deque の先頭に追加していき、ループを抜けたあとに deque の要素を先頭から出力する。

#include <iostream>
#include <deque>

using namespace std;
using ui = unsigned int;

int main()
{
  deque<ui> a;
  while (true)
  {
    ui aa;
    cin >> aa;

    a.push_front(aa);
    if (aa == 0)
      break;
  }

  for (auto aa : a)
    cout << aa << endl;

  return 0;
}

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

C - A+B+C

まずは \(A_1, \dots, A_N\) を記録する。

\(B_1, \dots, B_M\) の入力を受け取りながら、各 \(A_i (1 \leq i \leq N)\) との和を計算し map<ull, bool> ab で保持する。

\(C_1, \dots, C_L\) の入力を受け取りながら、 ab の key との和を計算し、 map<ull, bool> abc で保持する。

\(X_1, \dots, X_Q\) について、各 \(X_q\) が abc の key として存在していれば Yes を、存在していなければ No を出力する。

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

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

int main()
{
  map<ull, bool> sum;

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

  cin >> m;
  ull b;
  map<ull, bool> ab;
  for (; m--;)
  {
    cin >> b;
    for (auto aa : a)
      ab[aa + b] = true;
  }

  cin >> l;
  ull c;
  for (; l--;)
  {
    cin >> c;
    auto it = ab.begin();
    while (it != ab.end())
    {
      sum[it->first + c] = true;
      it++;
    }
  }

  cin >> q;
  ull x;
  for (; q--;)
  {
    cin >> x;
    cout << (sum[x] ? "Yes" : "No") << endl;
  }

  return 0;
}

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

E - Insert or Erase

各 \(A_1, \dots, A_N\) を値として持つ Node を定義する。各 Node は前後 (prev と next)の Node を指すポインタも持つようにする。また、先頭の Node を指すポインタ root と、 \(A_i (1 \leq i \leq N)\) を key 、対応する Node のポインタを value として持つ map を用意する。

各 query について、以下の処理を行う。

`1 x y`

x を持つ Node を xn とする。

値 y を持つ Node nn を新たに作成し、 prev に xn を、 next に xn->next をセットする。

xn が末尾の Node ではない場合、つまり xn->next != NULL の場合、 xn->next の prev に nn をセットする。

xn の next に nn をセットする。

最後に map に y を key として nn のポインタを value として追加する。

例えば \(A = (1,2,3) \) だった場合の初期状態は下記のようになる。

graph LR n[Node \nA_i\nprev\nnext] n1[Node 1\n1\n NULL\n *Node2] n2[Node 2\n2\n *Node1\n *Node3] n3[Node 3\n3\n *Node2\n NULL] n1 --> n2 n2 --> n3

これに対して 1 2 4 が query として与えられた場合、下記のようになる。

graph LR n1[Node 1\n1\n NULL\n *Node2] n2[Node 2\n2\n *Node1\n *Node4] n4[Node 4\n4\n *Node2\n *Node3] n3[Node 3\n3\n *Node4\n NULL] n1 --> n2 n2 --> n4 n4 --> n3 style n4 fill:#f9f,stroke:#333,stroke-width:4px

`2 x`

x を持つ Node を xn とする。

xn->next->prev に xn->prev をセットする。

xn が先頭の Node ではない場合、つまり xn->prev != NULL の場合、 xn->prev の next に xn->next をセットする。

xn が先頭の Node である場合、つまり xn->prev == NULL の場合、 root に xn->next をセットする。

最後に map から x を key とする要素を削除する。

例えば、上の例に対して 2 2 が query として与えられた場合、下記のようになる。

graph LR n1[Node 1\n1\n NULL\n *Node2] n2[Node 2\n2\n *Node1\n *Node4] n4[Node 4\n4\n *Node2\n *Node3] n3[Node 3\n3\n *Node4\n NULL] n1 --> n2 n2 --> n4 n4 --> n3

これが

graph LR n1[Node 1\n1\n NULL\n *Node4] n4[Node 4\n4\n *Node1\n *Node3] n3[Node 3\n3\n *Node4\n NULL] n1 --> n4 n4 --> n3 -n2[Node 2\n2\n *Node1\n *Node4]

こうなる。

各 query について上記の処理を行ったあと、 root から順に Node の値を出力し、 next が NULL になるまで続ける。

#include <iostream>
#include <map>

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

struct Node
{
  ui x;
  Node *prev;
  Node *next;
};

int main()
{
  map<ui, Node *> an;

  ui n;
  cin >> n;

  ui a = 0;
  Node *root = NULL;
  Node *pn = NULL;
  for (ui i = 0; i < n; i++)
  {
    cin >> a;

    Node *node = new Node({a, pn, NULL});
    if (i == 0)
      root = node;

    if (i > 0)
      pn->next = node;

    pn = node;
    an[a] = node;
  }

  ui q;
  cin >> q;

  ui c, x, y;
  for (; q--;)
  {
    cin >> c;
    if (c == 1)
    {
      cin >> x >> y;
      Node *xn = an[x];
      Node *nn = new Node({y, xn, xn->next});
      if (xn->next != NULL)
        xn->next->prev = nn;

      xn->next = nn;
      an[y] = nn;
    }
    else if (c == 2)
    {
      cin >> x;
      Node *xn = an[x];

      if (xn->prev != NULL)
        xn->prev->next = xn->next;

      if (xn->next != NULL)
        xn->next->prev = xn->prev;

      if (xn->prev == NULL)
        root = xn->next;

      an.erase(xn->x);
      delete xn;
    }
    else
    {
      // noop
    }
  }

  cout << root->x;
  Node *nx = root->next;
  while (nx != NULL)
  {
    cout << " " << nx->x;
    nx = nx->next;
  }
  cout << endl;

  return 0;
}