AtCoder Beginner Contest 414 の A/B/C 問題の解法 #ABC414

2025-07-12

AtCoder Beginner Contest 414 の A/B/C 問題の解法。

実装はこちら atcoder/abc/401-500/414 · michimani/atcoder 。

A - Streamer Takahashi

ストリーマーのたかはしが \(L\) 時から \(R\) 時まで配信を行う。\(N\) 人のリスナーがいて、\(i\) 番目のリスナーは \(X_i\) 時から \(Y_i\) 時まで視聴可能。配信全体を視聴できるリスナーの人数を求める問題。

リスナーが配信全体を視聴できる条件は、\(X_i \leq L\) かつ \(R \leq Y_i\) である。この条件を満たすリスナーの数をカウントする。

#include <iostream>

using namespace std;
using ui = unsigned int;

int main()
{
  ui n, l, r;
  cin >> n >> l >> r;

  ui x, y;
  ui ans = 0;
  for (; n--;)
  {
    cin >> x >> y;

    ans += ui(x <= l && r <= y);
  }

  cout << ans << endl;

  return 0;
}

B - String Too Long

ランレングス符号化されたデータから元の文字列を復元する問題。\(N\) 個の文字と長さのペアが与えられ、それぞれの文字を指定された長さ分繰り返した文字列を連結する。結果の文字列の長さが100以下なら文字列を、101以上なら “Too Long” を出力する。

各ペアについて文字列の長さを累積し、途中で100を超えた場合は “Too Long” を出力する。100以下の場合は文字列を構築して出力する。

#include <iostream>

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

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

  ull tl = 0;
  string s = "";

  char c = '.';
  ull l = 0;
  for (; n--;)
  {
    cin >> c >> l;
    tl += l;

    if (tl > 100)
    {
      cout << "Too Long" << endl;
      return 0;
    }

    s += string(l, c);
  }

  cout << s << endl;

  return 0;
}

C - Palindromic in Both Bases

1 以上 \(N\) 以下の整数のうち、10進数と \(A\) 進数の両方で回文となる数の総和を求める問題。

まず10進数で回文となる数を効率的に生成する。長さ1から12までの回文を前半部分から構築することで全ての候補を作成し、それぞれについて \(A\) 進数でも回文かどうかを判定する。\(A\) 進数での回文判定は、数値を \(A\) 進数の各桁に分解してから前後の桁を比較する。

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ull = unsigned long long;

bool isPalindrome(ull num, int base)
{
  vector<int> digits;
  ull temp = num;
  while (temp > 0)
  {
    digits.push_back(temp % base);
    temp /= base;
  }

  int len = digits.size();
  for (int i = 0; i < len / 2; i++)
    if (digits[i] != digits[len - 1 - i])
      return false;

  return true;
}

void generatePalindromes(vector<ull> &palindromes, ull maxN)
{
  for (int len = 1; len <= 12; len++)
  {
    if (len == 1)
    {
      for (ull i = 1; i <= 9; i++)
        if (i <= maxN)
          palindromes.push_back(i);
    }
    else
    {
      int halfLen = (len + 1) / 2;
      ull start = 1;
      for (int i = 1; i < halfLen; i++)
        start *= 10;

      ull end = start * 10;

      for (ull half = start; half < end; half++)
      {
        string halfStr = to_string(half);
        string palindrome = halfStr;

        int startIdx = (len % 2 == 0) ? halfLen - 1 : halfLen - 2;
        for (int i = startIdx; i >= 0; i--)
          palindrome += halfStr[i];

        ull num = stoull(palindrome);
        if (num <= maxN)
          palindromes.push_back(num);
      }
    }
  }
}

int main()
{
  int a;
  ull n;
  cin >> a >> n;

  vector<ull> palindromes;
  generatePalindromes(palindromes, n);

  ull sum = 0;
  for (ull num : palindromes)
    if (isPalindrome(num, a))
      sum += num;

  cout << sum << endl;
  return 0;
}

Tags for this post: AtCoder C++

comments powered by Disqus

Prev: AtCoder Beginner Contest 413 の A/B/C 問題の解法 #ABC413

Next: AtCoder Beginner Contest 415 の A/B/C 問題の解法 #ABC415