C++で原子価（結合数）から3つの原子が分子を形成できるか判定する方法

原子価（valence number）とは、ある原子が他の原子と何本の結合を形成しなければならないかを定義する数値です。この記事では、3つの原子それぞれの原子価が与えられたとき、それらが1つの分子を形成できるかどうかをC++で判定する方法を解説します。

なお、原子同士は複数の結合を形成できる点に注意してください。例えば、原子価が「2, 4, 2」である場合、以下のような結合が可能なので、答えはYESとなります。

1 – 2、1 – 2、2 – 3、2 – 3

分子を形成できない条件

3つの原子価を a、b、c とし、c が最大値であると仮定します。このとき、分子を形成できないのは次の2つの場合です。

• a + b + c が奇数の場合： 結合は必ず2つの原子の原子価をそれぞれ1ずつ減らすため、すべての結合を作り終えたときの総和は偶数になります。したがって、最初の総和が奇数であれば分子を形成できません。
• a + b < c の場合： 最大の原子価を持つ原子の結合相手が足りず、余った結合（未使用のコネクタ）が残ってしまいます。

上記の2つの条件に当てはまらなければ、3つの原子は分子を形成できます。

C++での実装例

#include<iostream>
using namespace std;

bool canMakeMolecule(int a, int b, int c) {
    // 総和が奇数、または最大値が他の2つの和より大きい場合は不可
    if ((a + b + c) % 2 != 0 || a + b < c)
        return false;
    else
        return true;
}

int main() {
    int a = 2, b = 4, c = 2;
    if (canMakeMolecule(a, b, c)) {
        cout << "They can form Molecule";
    } else {
        cout << "They can not form Molecule";
    }
}

実行結果

They can form Molecule

アルゴリズムのポイント

この問題の判定ロジックは非常にシンプルで、時間計算量はO(1)です。ポイントをまとめると以下の通りです。

• 3つの原子価の合計が偶数であることを確認する。
• 最大の原子価が、残り2つの原子価の合計以下であることを確認する。
• 両方の条件を満たせば「分子を形成できる」と判定できる。

このように、グラフ理論における次数列の性質（握手補題）を応用することで、効率的に判定を行うことができます。