AtCoder Beginner Contest 247 #ABC247

2024-01-18

AtCoder Beginner Contest 247 の A/B/C/D 問題の解説。

実装はこちら atcoder/abc/201-300/247 · michimani/atcoder 。

A - Move Right

\(S\) をビット列として受け取り、 1 回だけ右シフトした値を出力する。

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
  bitset<4> s;
  cin >> s;

  s >>= 1;
  cout << s << endl;
  return 0;
}

提出 #49377255 - AtCoder Beginner Contest 247

B - Unique Nicknames

人 \(i\) を下記の構造体で記録しつつ、 \(s_i, t_i\) それぞれの出現回数を map<string, ui> でカウントする。

struct Name
{
  string s;
  string t;
};

人 \(i\) について下記の条件に合致するものが存在した場合はその時点で No を出力して終了する。

\(s_i \neq t_i\) の場合
- \(s_i, t_i\) の出現回数がどちらも \(1\) ではない
\(s_i = t_i\) の場合
- \(s_i\) の出現回数が \(3\) 以上である

上記の条件に合致する人がいなかった場合は Yes を出力して終了する。

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

using namespace std;
using ui = unsigned int;

struct Name
{
  string s;
  string t;
};

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

  map<string, ui> ac;
  vector<Name> ns(n);
  for (auto &n : ns)
  {
    cin >> n.s >> n.t;
    ac[n.s]++;
    ac[n.t]++;
  }

  for (auto &n : ns)
  {
    if ((n.s != n.t && ac[n.s] != 1 && ac[n.t] != 1) ||
        (n.s == n.t && ac[n.s] > 2))
    {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}

提出 #49377175 - AtCoder Beginner Contest 247

C - 1 2 1 3 1 2 1

\(S_n\) を生成する関数を実装し、その再帰呼び出して \(S_N\) を生成する。再帰呼び出しの終了条件は \(n=1\) のときで、そのときの値は \(1\) とする。

#include <iostream>

using namespace std;
using ui = unsigned int;

string sn(ui n)
{
  if (n == 1)
  {
    return "1";
  }

  string snn = sn(n - 1);
  return snn + " " + to_string(n) + " " + snn;
}

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

  cout << sn(n) << endl;
  return 0;
}

提出 #49376766 - AtCoder Beginner Contest 247

D - Cylinder

各ボールを下記の構造体で表すことにする。

struct Ball
{
  ull x;  // 書かれている数
  ull c;  // 筒に入れられた個数
};

筒を list<Ball> cy で表現し、 \(query_q (1 \leq q \leq Q)\)に対して次の処理を行う。

1 x c

ボール {x, c} を cy の末尾に追加する。

2 c

合計値を \(0\) で初期化する
次の操作を \(c\) が \(0\) になるまで筒の先頭のボールに対して繰り返す
- ボールの個数が \(c\) を超える場合
  - 合計値に \(ボールに書かれている数\) と \(c\) の積を足す
  - ボールの個数から \(c\) を引いて、 \(c\) を \(0\) に更新する
- ボールの個数が \(c\) 以下の場合
  - 合計値に \(ボールに書かれている数\) と \(ボールの個数\) の積を足す
  - \(c\) からボールの個数を引いて、 \(c\) を更新する
  - ボールを削除する
合計値を出力する

#include <iostream>
#include <list>

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

struct Ball
{
  ull x;
  ull c;
};

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

  list<Ball> cy;
  for (ui i = 0; i < q; i++)
  {
    ui cmd;
    cin >> cmd;

    ull x = 0, c = 0, sum = 0;
    switch (cmd)
    {
    case 1:
      cin >> x >> c;
      cy.push_back({x, c});
      break;

    case 2:
      cin >> c;
      while (c > 0)
      {
        if (cy.front().c > c)
        {
          sum += cy.front().x * c;
          cy.front().c -= c;
          c = 0;
        }
        else
        {
          c -= cy.front().c;
          sum += cy.front().x * cy.front().c;
          cy.pop_front();
        }
      }

      cout << sum << endl;

      break;

    default:
      // noop
      break;
    }
  }

  return 0;
}