HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）の A/B/C 問題の解法 #ABC342

2024-02-24

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）の A/B/C 問題の解法。

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

A - Yay!

ひとつ前の文字と異なる文字が現れた場所を出力する方針だと sample 2 が通らない。

\(S\) 内の各文字の出現場所を map<char, vector<ui>> cm で記録しておいて、出現回数が \(1\) 回の文字の出現場所 cm[x][0] を出力する。

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

using namespace std;
using ui = unsigned int;

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

 map<char, vector<ui>> cm;

 for (ui i = 1; i <= s.size(); i++)
   cm[s[i - 1]].push_back(i);

 auto it = cm.begin();
 while (it != cm.end())
 {
   if (it->second.size() == 1)
   {
     cout << it->second[0] << endl;
     return 0;
   }

   it++;
 }

 return 0;
}

提出 #50562604 - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

B - Which is ahead?

各 \(A_q, B_q (1 \leq q \leq Q)\) に対して \(P_1 , \dots, P_N\) を順に見ていき、最初に \(A_q\) または \(B_q\) と一致したときの \(P_i\) を出力する。

制約が緩いのでこれで十分間に合う。

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;

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

  vector<ui> p(n, 0);
  for (auto &pp : p)
    cin >> pp;

  ui q;
  cin >> q;
  for (; q--;)
  {
    ui a, b;
    cin >> a >> b;

    for (auto pp : p)
    {
      if (pp == a || pp == b)
      {
        cout << pp << endl;
        break;
      }
    }
  }

  return 0;
}

提出 #50566481 - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

C - Many Replacement

a から z までを順に vector<char> alp で保持しておく。\(S\) の各文字をアルファベット順に \(0 \leq i \leq 25\) に対応させ、 alp[i] の参照を要素とする vector<char *> s を作る。

各 \(c_q, d_q (1 \leq q \leq Q)\) に対して alp[i] == c となるものに対して alp[i] = d で更新する。

\(c_q = d_q\) となる \(q\) については alp の更新は発生しないためスキップできる。

最後に s の各要素に対してその参照先の文字を出力する。

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;

int main()
{
  vector<char> alp(26, '.');
  for (ui i = 'a'; i <= 'z'; i++)
    alp[i - 'a'] = char(i);

  ui n;
  cin >> n;

  vector<char *> s(n);
  for (ui i = 0; i < n; i++)
  {
    char c;
    cin >> c;
    s[i] = &alp[c - 'a'];
  }

  ui q;
  cin >> q;
  for (; q--;)
  {
    char c, d;
    cin >> c >> d;

    if (c == d)
      continue;

    for (auto &&al : alp)
      al = al == c ? d : al;
  }

  for (auto ss : s)
    cout << *ss;

  cout << endl;

  return 0;
}