A - God Sequence 解説
by 
E869120
プログラミングの学習を始めたばかりで何から手を付ければ良いか分からない方は、まずは「practice contest」の問題 A「Welcome to AtCoder」をお試しください。言語毎に解答例が掲載されています。
この解説では、
- A 問題「God Sequence」の解法
- どのような考察ステップで解法に至るか
- サンプルコード
の 3 つを紹介します。
1-1. \(A \geq B\) の場合の解法
次のようにすることで「神の数列」にできます。
- \(E_1 = 1, E_2 = 2, \cdots, E_A = A\) とする。
- \(E_{A + 1} = -1, E_{A + 2} = -2, \cdots, E_{A + B - 1} = -(B - 1)\) とする。
- 最後の \(E_{A + B}\) で調整して、総和を \(0\) にする。
そのとき、\(1 \leq i \leq B-1\) に対して \(E_i + E_{A + i} = 0\) が成り立つため、
\[ E_{A + B} = - \sum_{i=B}^{A} E_i = -\sum_{i = B}^{A} i = -\left(B + (B + 1) + ... + (A - 1) + A\right) \leq -B \]
となることから、\(E_i\) がすべて異なる「神の数列」になるのです。（シグマ記号についてはこちらの記事を参照）
より分かりやすく説明するために、いくつか例を載せておきます。
- \(A = 3, B = 3\) の場合：\(E = (1, 2, 3, -1, -2, -3)\)
- \(A = 4, B = 2\) の場合：\(E = (1, 2, 3, 4, -1, -9)\)
- \(A = 9, B = 5\) の場合：\(E = (1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, -3, -4, -35)\)
といった感じになります。
1-2. \(A < B\) の場合の解法
基本的に \(A \geq B\) の場合の逆をやれば良いです。つまり、次のようになります。
- \(E_1 = 1, E_2 = 2, \cdots, E_{A - 1} = (A - 1)\) とする。
- \(E_{A + 1} = -1, E_{A + 2} = -2, \cdots, E_{A + B} = -B\) とする。
- 最後の \(E_{A}\) で調整して、総和を \(0\) にする。
このとき、\(E_A\) の値を計算すると \(A\) 以上の整数になります。したがって、\(E_i\) がすべて異なる「神の数列」となるのです。
より分かりやすく説明するために、いくつか例を載せておきます。
- \(A = 2, B = 4\) の場合：\(E = (1, 9, -1, -2, -3, -4)\)
- \(A = 3, B = 7\) の場合：\(E = (1, 2, 25, -1, -2, -3, -4, -5, -6, -7)\)
- \(A = 4, B = 10\) の場合：\(E = (1, 2, 3, 49, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10)\)
2. どのようにして解法に至るか？
これは典型なのですが、与えられた条件のうちいくつかを撤廃した上で、最も単純な形を考えるという考察テクニックがあります。例えば今回の問題の場合、
- \(E_1 + E_2 + \cdots + E_{A + B} = 0\)
という条件のみを撤廃し、他の \(4\) つの条件をすべて満たす数列「半・神の数列」を考えてみましょう。例えば次のようなものがあります。
- \(E_1 = 1, E_2 = 2, \cdots, E_A = A\)
- \(E_{A + 1} = -1, E_{A + 2} = -2, \cdots, E_{A + B} = -B\)
このような数列を考えてから「総和が \(0\) になる」という条件を付け足すと、比較的簡単に方針が見えてきます。少し考えると、数列の要素のうち 1 つを変えるだけで実現できるのです。現在の総和が正の場合 \(E_{A+B}\) の値を減少させ、負の場合 \(E_{A}\) の値を増加させるだけで良いのです。まとめると、本問題で要求される考察テクニックは次の \(2\) 点となります。
- いくつかの条件を撤廃した「簡単な問題」を考える
- 数列などの要素を \(1\) つ変えることで、答えが導けるか考える
3. サンプルコード
まず、C++ での解答例は次のようになります。（リンク）
#include <iostream>
using namespace std;
int A, B, E[1 << 18];
int main() {
// Input
cin >> A >> B;
// Make "God Array"
if (A >= B) {
for (int i = 0; i < A; i++) E[i] = i + 1;
for (int i = A; i < A + B - 1; i++) E[i] = -(i - A + 1);
for (int i = 0; i < A + B - 1; i++) E[A + B - 1] -= E[i];
}
else {
for (int i = 0; i < A - 1; i++) E[i] = i + 1;
for (int i = A; i < A + B; i++) E[i] = -(i - A + 1);
for (int i = 0; i < A + B; i++) { if (i != A - 1) E[A - 1] -= E[i]; }
}
// Output
for (int i = 0; i < A + B; i++) {
if (i) cout << " ";
cout << E[i];
}
cout << endl;
return 0;
}
他のプログラミング言語でのサンプルコードは、次の通りです。
投稿日時:
最終更新: