AtCoder ABC 369 A - 369 (6Q, 灰色, 100 点)

偶数と奇数に関する理解も問われる問題。

• 問題へのリンク

問題概要

2 つの整数 が与えられる。

「 を並び替えると等差数列をなす」

という条件をみたすような整数 が何通りあるか求めよ。

制約

• 

解法 (1)：数学的に解く

まず、 の大小関係で場合分けして考えましょう。

• の場合
• の場合
• の場合

があります。このうち、 である場合は、 が等差数列になるような は、 である場合しかありません。よって、1 通りです。

また、 である場合には、swap(A, B) をして、 であるとしても一般性を失いません。よって、これ以降 であるとして考えることにしましょう。

のとき

さて、 であるとすると、 が等差数列になるような は、整数に限らなければ、下図のように 3 通りあります。つまり、

• がこの順に等差数列をなすとき
• がこの順に等差数列をなすとき
• がこの順に等差数列をなすとき

です。これら 3 つの場合によって求められる は明らかに異なる値ですので、それぞれ整数になるのかどうかのみ考えましょう。

一旦、それぞれの の値を求めてみましょう。

• がこの順に等差数列をなすとき：
• がこの順に等差数列をなすとき：
• がこの順に等差数列をなすとき：

となります。このうち、 と については整数になります。しかし、 は整数であるとは限りません。 が偶数のときは整数ですが、奇数のときは整数とはなりません。

以上をまとめると、次のように整理できます（結局 であるか であるかは関係なくなります）。

---

• のとき：1 通り
• そうでなく が偶数のとき：3 通り
• そうでないとき：2 通り

---

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    if (A == B) cout << 1 << endl;
    else if ((A + B) % 2 == 0) cout << 3 << endl;
    else cout << 2 << endl;
}

解法 (2)：全探索で解く

もう 1 つの方法として、 をある範囲について全探索することが考えられます。

そこで、各 について、 が等差数列をなすかどうかを判定する方法を考えましょう。

を小さい順に並べて とします。このとき、 が等間隔に並ぶかどうかを確認すればよいです。それは

であるかどうか

によって確認できます。

コード

ここでは、 の探索範囲を -1000 から 1000 までとしています。制限時間の許す限り、範囲を大きめにとっておくのが無難でしょう。

一応最悪ケースの見積もってみましょう。

• のときに がこの順に等差数列をなす は、 です
• のときに がこの順に等差数列をなす は、 です

これらの が考えられる最小値と最大値となります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, res = 0;
    cin >> A >> B;

    for (int x = -1000; x <= 1000; x++) {
        vector<int> v({A, B, x});
        sort(v.begin(), v.end());
        if (v[1] - v[0] == v[2] - v[1]) res++;
    }
    cout << res << endl;
}