Official

A - Two Lucky Numbers Editorial by E869120

解説の目次

プログラミングの学習を始めたばかりで何から手を付ければ良いか分からない方は、まずは「practice contest」の問題 A「Welcome to AtCoder」をお試しください。言語毎に解答例が掲載されています。以下、この解説の目次を記します。

  • 1. 単純なアルゴリズム
  • 2. 想定解法
  • 3. 想定解法の証明
  • 4. 解法を思いつくためのヒント
  • 5. ソースコード

すぐに解答を知りたい方は、「2. 想定解法」をご覧ください。


1. 単純なアルゴリズム

一般に、問題を解く手順のことを アルゴリズム といいます。同じ問題を解くにしても、様々なアルゴリズムが考えられ、少ない計算回数で解けるものとそうでないものがあります。アルゴリズムに関する簡単な紹介は、このスライド をご覧ください。

さて、この問題を解く単純なアルゴリズムとして、以下のように 1 つずつ順番に調べていくことが考えられます。

  • \(x=1\) は超ラッキーな数かどうか、判定する（Yes ならば 1 と出力して実行終了）
  • \(x=2\) は超ラッキーな数かどうか、判定する（Yes ならば 2 と出力して実行終了）
  • \(x=3\) は超ラッキーな数かどうか、判定する（Yes ならば 3 と出力して実行終了）
  • \(x=4\) は超ラッキーな数かどうか、判定する（Yes ならば 4 と出力して実行終了）
  • 以下同様に、初めて超ラッキーな数が現れるまで調べ続ける

しかし、このアルゴリズムでは、とても多くの計算処理を行わなければならないケースがあります。たとえば \(A=99999999, B=40000000\) の場合、最小の超ラッキーな数が 9999999920000000（16 桁）となり、ここまでを全部調べるのは大変です。

また、コンピュータの計算速度には限界があります。プログラミング言語によりますが、AtCoder では \(10^8 \sim 10^9\) 回を超える計算を行うプログラムを提出しても、実行時間制限超過（TLE）になってしまいます。

したがって、このままでは不正解です（ソースコード（C++））。別の方法を考えてみましょう。


2. 想定解法

実は、この問題の制約下では \(500,000,000 \times B + A\) は必ず「超ラッキーな数」になります。

したがって、これを出力する以下のようなプログラムを書くと、正解が得られます。

Python・JAVA・C のソースコードは、「5. ソースコード」をご覧ください。

#include <iostream>
#include <string>
using namespace std;

int main() {
	long long A, B; // long long 型の変数 A, B を定義
	cin >> A >> B; // 整数 A, B を入力
	cout << 500000000LL * B + A << endl; // 答えを出力（500000000LL は「long long 型の 500000000」という意味）
	return 0;
}


3. 想定解法の証明

次に、想定解法が正しい理由は以下のように証明できます。

\(X=500,000,000 \times B+A\) とするとき、\(2X = 10^9 \times B + 2A\) となる。このとき、以下が成り立つ。

  • \(X\) の下 8 桁が \(A\) となり、1 つ目の条件（\(A\) が現れる）を満たす。
  • \(A \leq 99999999\) より、\(2X\) の下 9 桁が \(2A\) 、それより上の桁が \(B\) となり、2 つ目の条件（\(B\) が現れる）を満たす。

いくつかのケースにおける \(X\) と \(2X\) の値を以下に示します。下 9 桁とそれ以上の桁に分割すると、証明が直観的に理解できるのではないかと思います。


4. 解法を思いつくためのヒント

本問題のような「答えを 1 つ構成する問題」を解く典型的な考察パターンとして、「与えられた条件のうちいくつかだけを考えた後、これを少し変更するテクニック」 があります。このテクニックにしたがって問題を解くと、以下のようにして想定解法に至ります。

ステップ1：1 つ目の条件だけを考える

まず、1 つ目の条件（\(x\) に \(A\) が現れる）を満たす整数 \(x\) を考える。明らかに、\(x=A\) のとき条件を満たす。

ステップ2：どう変更すれば良いか？

次に、1 つ目の条件を満たしたまま、答え \(x\) の形を少し変えることを考える。ここで、下 9 桁より上の部分を変更しても、1 つ目の条件は満たされるままである。（たとえば \(A=1234567\) のとき、\(x=1001234567\) や \(x=869001234567\) などに変更しても、1 つ目の条件を満たす）

ステップ3：2 つ目の条件の追加

そこで、\(2x\) の下 9 桁より上の部分について \(B\) が現れるようにすることを考えると、\(x=500,000,000 \times B+A\) が導出できる。

なお、同じような考察パターンが使える問題として、ARC 117 A - God Sequence があります。是非解いてみましょう。


5. ソースコード

posted:
last update: