中学入試から：正三角形？二等辺？

はじめに

本記事はNabetani様がCodeIQに出題した問題「中学入試から：正三角形？二等辺？」の回答と、若干の解説を書いたものである。回答の提出はしなかったが一応解いたので、回答を公開することにする。
出題者様本人の解説は こちら から閲覧できる。

問題

問題の詳細は こちら から閲覧できるので、そちらを参照のこと。

私の回答

triangle.cpp

// g++ -g -std=c++11 -Wall triangle.cpp
#include <iostream>
#include <string>
#include <vector>
#include <regex>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <fstream>

using namespace std;

typedef map<string, double> map_t;

string join(const vector<string> &v, const string &separator)
{
    vector<string> res;
    transform(v.begin(), v.end(), back_inserter(res),
            [&](const string &s) { return res.size() + 1 == v.size() ? s : s + separator; }); 
    return accumulate(res.begin(), res.end(), string(""));
}

vector<string> split(const string &src, const string &separator)
{
    vector<string> v;
    const regex reg = separator.empty() ? regex("(.{1})") : regex(separator);
    const int frag = separator.empty() ? 1 : -1; 
    copy(sregex_token_iterator(src.begin(), src.end(), reg, frag), sregex_token_iterator(), back_inserter(v));
    return v;
}

vector<string> get_keys(const map_t &m) 
{
    vector<string> keys;
    transform(m.begin(), m.end(), back_inserter(keys), [](const map_t::value_type &p) { return p.first; }); 
    return keys;
}

vector<double> get_values(const map_t &m) 
{
    vector<double> values;
    transform(m.begin(), m.end(), back_inserter(values), [](const map_t::value_type &p) { return p.second; }); 
    return values;
}

string get_not_found_key(const vector<string> &v)
{
    const vector<string> a_to_c = { "A", "B", "C" };
    const auto it = find_if(
            a_to_c.begin(), a_to_c.end(),
            [&](const string &s) { return find(v.begin(), v.end(), s) == v.end(); });
    assert(it != a_to_c.end());
    return *it;
}

string get_not_found_key(const string &s)
{
    const vector<string> v = split(s, "");
    return get_not_found_key(v);
}

string get_not_found_key(const map_t &m)
{
    const vector<string> v = get_keys(m);
    return get_not_found_key(v);
}

map_t scan(const regex &reg, const vector<string> &v)
{
    map_t m;
    for(const auto &e : v) {
        smatch sm;
        if(regex_match(e, sm, reg)) {
            // keyが2文字以上(辺)の場合は1文字に置き換える
            // ex) AB/BA -> C, BC/CB -> A, AC/CA -> B
            const string key = string(sm[1]).size() == 1 ? sm[1] : get_not_found_key(sm[1]);
            m.insert( make_pair(key, atoi(string(sm[2]).c_str())) );
        }
    }
    return m;
}

int count_same_elements(const vector<double> &v, double delta)
{
    int res = 0;
    for(const auto &e1 : v) {
        res = max<int>(res, count_if(v.begin(), v.end(), [&](double e2) { return abs(e1 - e2) < delta; }));
    }
    return res;
}

string analyze_triangle_type(const map_t &m)
{
    const vector<double> v = get_values(m);
    if(v.empty()) {
        return "う";
    }

    const int same_elements = count_same_elements(v, 0.1);
    switch (same_elements) {
        case 2:
            return "い";
        case 3:
            return "あ";
        default:
            return "う";
    }
}

double deg_to_rad(double deg)
{
    const double pi = 3.14159265358979323846;
    return deg * pi / 180.0;
}

double solve_2d_eq(const map_t & sides, const map_t & angles)
{
    const string angle = begin(angles)->first;
    if(sides.count(angle) == 0) {
        const double x = begin(sides)->second;
        const double y = sides.rbegin()->second;
        const double z = x * x + y * y - 2 * x * y * cos(deg_to_rad(angles.at(angle)));
        return sqrt(z);
    }
    const string s = begin(sides)->first;
    const double x = s == angle ? sides.rbegin()->second : sides.begin()->second;
    const double y = s == angle ? sides.begin()->second : sides.rbegin()->second;
    const double a = 1;
    const double b = -2 * x * cos( deg_to_rad(angles.at(angle)) );
    const double c = x * x - y * y;
    return (-b + sqrt( b * b - 4 * a * c )) / (2 * a);
}

string solve_problem(const string &src)
{
    const auto v = split(src, ",");

    const auto angles = [&]() {
        const regex reg("角([A-C]{1})=([0-9]+)度");
        auto angles = scan(reg, v);
        if(angles.size() == 2) {
            const vector<double> values = get_values(angles);
            const int acc = accumulate(begin(values), end(values), 0);
            const string key = get_not_found_key(angles);
            angles.insert(make_pair(key, 180 - acc));
        }
        return angles;
    }();

    // 角度が全てわかっている場合は三角形の種類を判定可能
    if(angles.size() == 3) {
        return analyze_triangle_type(angles);
    }

    const auto sides = [&]() {
        const regex reg("([A-C]{2})=([0-9]+)cm");
        auto sides = scan(reg, v);
        if(sides.size() == 2 && !angles.empty()) {
            const double value = solve_2d_eq(sides, angles);
            const string key = get_not_found_key(sides);
            sides.insert(make_pair(key, value));
        }
        return sides;
    }();

    return analyze_triangle_type(sides);
}

void print_result()
{
    ifstream ifs("data.utf8.txt");
    if(ifs.fail()) {
        cout << "Failed to read file." << endl;
        return;
    }

    string in;
    vector<string> wrong_no;
    while(getline(ifs, in)) {
        const vector<string> v = split(in, "\t");
        const string actual = solve_problem(v[1]);
        const string expected = v[2];
        if(actual != expected) {
            wrong_no.push_back(v[0]);
        }
    }

    cout << join(wrong_no, ",") << endl;
}

int main()
{
    print_result();
    return 0;
}

大体200行くらい。

コードの解説

入力値のチェック

本当はやるべきなのかもしれないが、本問では「不正な入力に対処する必要はありません。」とのことなので、入力値のチェックはしていない。

三角形の種類の判定

今回の問題では、三角形ABCが

選択肢	説明
あ	正三角形である。
い	二等辺三角形である。（ただし、正三角形であるとはいえない。）
う	二等辺三角形ではない。または、二等辺三角形かどうかわからない。

の何れであるかを判定する。

判定するためには角度と辺の情報が必要になるので、それらを取得する。

角度情報の取得

角度情報は solve_problem 内の下記部分で取得している。
入力データから角度情報(正規表現 角([A-C]{1})=([0-9]+)度 にマッチするデータ)のみ読み取り、読み取ったデータが2つある場合は、「三角形の内角の和は180度」という性質を使って残りの角度を算出する。

const auto angles = [&]() {
    const regex reg("角([A-C]{1})=([0-9]+)度");
    auto angles = scan(reg, v);
    if(angles.size() == 2) {
        const vector<double> values = get_values(angles);
        const int acc = accumulate(begin(values), end(values), 0);
        const string key = get_not_found_key(angles);
        angles.insert(make_pair(key, 180 - acc));
    }
    return angles;
}();

上記処理で3つの角度情報を取得できた場合、三角形の種類を判定することが可能なので、判定結果を返して処理は終了となる。

辺情報の取得

角度情報だけで三角形の種類を判定できなかった場合、入力データから辺の情報を取得する。取得方法は角度の場合と同様だが、後の計算の都合上、辺の名前を下記のように置き換えている(scan 関数を参照)。

• BCまたはCB → A
• ACまたはCA → B
• ABまたはBA → C

辺情報が2つ以上取得でき、かつ角度情報が1つ以上取得できた場合は余弦定理により残りの辺情報を取得可能であるので、余弦定理を使って残りの辺情報を取得する。

余弦定理

難しくはないが、(個人的に)今回の問題の中で一番面倒だった部分。下記2つの場合で余弦定理の式を変形する必要が生じるのが面倒だった。

1. 求めたい辺の対角がわかっている場合
2. 求めたい辺の対角がわかっていない場合

例えば

• "AC=20cm,角C=60度,BC=12cm"

のような入力データの場合、求めたい辺ABの対角Cが既知のため、式の変更は不要。

C = \sqrt{ A^2 + B^2 - 2 \times A \times B \times cos(C) }

一方、

• "AC=20cm,角C=60度,BA=12cm"

のような入力データの場合、求めたい辺BCの対角Aが不明なため、式を下記のように変形する必要が生じる。

\begin{equation}
\begin{split}
C^2 &= A^2 + B^2 - 2 \times A \times B \times cos(C) \\
\Leftrightarrow 0 &= A^2 + (- 2 \times B \times cos(C)) \times A  + (B^2 - C^2)
\end{split}
\end{equation}

そして求めたい辺Aは2次方程式の解の公式を使って得ることができる。

A = \frac{(-b + \sqrt{ b^2 - 4 \times a \times c })}{2a}

ただし、a = 1, b = - 2 \times B \times cos(C), c = B^2 - C^2

上記処理の実装が solve_2d_eq で、本関数の if 文内の処理が1の場合に相当する。

最後に

出題者様の解説を見ると「角の名前や辺の名前を一切無視してよい」ようなので、余弦定理を使うような面倒なことはしなくて良かったみたい。また、辺の長さを余弦定理を使って求めるため浮動小数点を使うことになる。その結果、辺の長さを比較する際にある程度の誤差(私のプログラムでは0.1)を許容しての比較となり、厳密な比較はできないのもよろしくないと思う。