Zenn
🕌

ABC220 A - Find Multiple / B - Base K C++解答例

2021/09/27に公開
C++
競技プログラミング
AtCoder
競プロ
tech

AtCoder Beginner Contest 220のA問題とB問題をC++で解きます。

A - Find Multiple

問題文をAtCoderのページより引用します。

問題文

A以上B以下であるようなCの倍数を、1つ出力してください。
条件を満たす数が存在しない場合は-1を出力してください。

制約

  • 1 \leq A \leq B \leq 1000
  • 1 \leq C \leq 1000
  • 入力はすべて整数

解答例

解答例1：while文を使った解法

制約が緩いので、全探索することを考えてみましょう。
B以下のCの倍数を全て列挙し、その中にA以上を満たす数が存在すればその数を出力、存在しなければ-1を出力すればよいです。

以下の解答例では、Cの倍数を順次格納していく変数answerと、問題文の条件を満たす数が存在するかどうかを表す論理型変数okの2つを用い、while文を使ってループを回しています。
条件を満たす数が見つかったらその時点でループを終了しています。

a.cpp
#include <iostream>

int main() {
  int64_t A, B, C;
  std::cin >> A >> B >> C;
 
  int64_t answer = 0;
  bool ok = false;
  // B以下のCの倍数を全て見ていく
  while (answer <= B) {
    answer += C;
    // 条件を満たす数が見つかればその時点でループを終了する
    // このときのanswerが答えとなる
    if (answer >= A && answer <= B) {
      ok = true;
      break;
    }
  }

  // 条件を満たす数が存在すればその数を出力
  if (ok) {
    std::cout << answer << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }
 
  return 0;
}

実際に提出したコードはこちら。

解答例2：整数の除算を利用した解法

公式解説で紹介されていた解法です。BをCで割ったときの商に、改めてCをかけたときの数は、B以下のCの倍数の中で最も大きい値となります。

この値がA以上だった場合、問題文の条件を満たす数が少なくとも1つは存在することになります。従って、その値を出力すればOKということになります。

a.cpp
#include <iostream>
 
int main() {
  int64_t A, B, C;
  std::cin >> A >> B >> C;
  
  // xはB以下のCの倍数の中で最大の数
  int64_t x = (B / C) * C;
  if (x >= A) {
    std::cout << x << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }
  
  return 0;
}

実際に提出したコードはこちら。

B - Base K

問題文をAtCoderのページより引用します。

問題文

整数A, BがK進法表記で与えられます。
A \times Bを10進法表記で出力してください。

制約

  • 2 \leq K \leq 10
  • 1 \leq A, B, \leq 10^5
  • A, BはK進法表記で与えられる。

解答例

N進法\leftrightarrow 10進法変換の問題…と思いきや、K進法で表記された数(文字列として扱うと楽です)を10進法に変換するだけで解くことができます。

「K進法で表された数値(文字列型)を10進法に変換する関数」を自作してもよいですが、C++の場合はstd::stoi関数[1]やstd::stol関数[2]などがまさにその機能を持っています。
これをそのまま使ってしまえば問題が解けるでしょう。

ただし、この問題ではオーバーフローに注意する必要があります。
制約を見ると、Kは最大で10まで与えられます。一方、AとBは最大で10^5までの数が与えられます。
そのため、この問題で考えられる最大の入力は、10進法で表記された10^5と10^5です。

ここで、10^5同士をかけたときの積は10,000,000,000となりますが、32bitの符号付き整数型(int型)が表せる最大の値は2,147,483,647であり、32bitでは表現することができないことがわかります(符号なしにしても無理です)。

従って、この問題ではint型やint32_t型ではなく、long long型かint64_t型を使う必要があります。
また、上記の関数を使って解く場合も、std::stoiやstd::stolではなく、std::stoll関数を利用する必要があります。

std::stoll関数を使って文字列をK進数に変換する際は、第1引数に変換したい文字列を、第2引数にnullptrを、第3引数にKを渡します。

b.cpp
#include <iostream>
#include <string>
 
int main() {
  int64_t K;
  std::cin >> K;
  std::string A, B;
  std::cin >> A >> B;
  
  std::cout << std::stoll(A, nullptr, K) * std::stoll(B, nullptr, K) << std::endl;
  
  return 0;
}

実際に提出したコードはこちら。

おまけ：進数変換関数の自作

K進法表記の文字列を10進法に変換する際は、変換したい文字列の各文字(各桁に当たります)に対して、桁に対応したKの累乗を掛けた値を全て足すことで求めます。

例えば、3進数で表記された数1201_{(3)}を変換する際は、

  • 1桁目の数に3^0 = 1を掛けた値(1 \times 3^0 = 1)
  • 2桁目の数に3^1 = 3を掛けた値(0 \times 3^1 = 0)
  • 3桁目の数に3^2 = 9を掛けた値(2 \times 3^2 = 18)
  • 4桁目の数に3^3 = 27を掛けた値(1 \times 3^3 = 27)

の総和が10進法表記したときの数になります。すなわち、

1 \times 3^0 + 0 \times 3^1 + 2 \times 3^2 + 1 \times 3^3 = 46

です。これを公式化すると、K進法で表記されたN個の桁を持つ数値Sのi (1 \leq i \leq N)桁の数をS_{i}としたとき、Sを10進法で表したときの値は、

\sum_{i = 1}^{N} S_{i} \times K^{i - 1}

と表せます。

実際にプログラムを組む際は、1桁目の数値にアクセスする際はS.at(N - 1)のように書くことになり、for文の記述が面倒になります。
なので、変換をする前に文字列の中身を逆転させてから計算するのが良いです。
std::reverse関数を使えば文字列の順序を逆転させることができます。この関数を使うためには<algorithm>ヘッダをインクルードする必要があります。

尚、文字列を逆転させた後、1桁目の値にアクセスする際はS.at(0)と書くことになります。i桁目の値にアクセスする際はS.at(i - 1)と書くことになるので注意しましょう。

K進数を10進数に変換する関数
int64_t base_k(std::string s, int64_t k) {
  int64_t answer = 0;
  // 各桁の値にかける係数
  int64_t pow = 1;
  // 文字列の順序を逆転させる
  std::reverse(s.begin(), s.end());
  for (int64_t i = 0; i < s.size(); i++) {
    answer += static_cast<int64_t>(s.at(i) - '0') * pow;
    pow *= k;
  }
 
  return answer;
}

プログラム全体は以下のようになります。

b.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
int64_t base_k(std::string s, int64_t k) {
  int64_t answer = 0;
  int64_t pow = 1;
  std::reverse(s.begin(), s.end());
  for (int64_t i = 0; i < s.size(); i++) {
    answer += static_cast<int64_t>(s.at(i) - '0') * pow;
    pow *= k;
  }
 
  return answer;
}
 
int main() {
  int64_t K;
  std::string A, B;
  std::cin >> K >> A >> B;
 
  std::cout << base_k(A, K) * base_k(B, K) << std::endl;
 
  return 0;
}

実際に提出したコードはこちら。

脚注

  1. https://cpprefjp.github.io/reference/string/stoi.html ↩︎

  2. https://cpprefjp.github.io/reference/string/stol.html ↩︎

Discussion