第 1 問：温度計 (Thermometer)

体温の読み取り値に基づき、状態を示す整数を出力する単純なシミュレーション問題です。入力された小数点数がどの範囲に属するかを判断します。

解法の方針

温度値を float または double 型で受け取り、以下の条件ロジックで分岐処理を行います。

• 38.0 以上の場合：レベル 1
• 37.5 未満の場合：レベル 3
• それ以外：レベル 2

実装コード

#include <iostream>
using namespace std;

void process_measurement() {
    double temperature;
    cin >> temperature;
    
    if (temperature >= 38.0) {
        cout << 1 << endl;
    } else if (temperature < 37.5) {
        cout << 3 << endl;
    } else {
        cout << 2 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    process_measurement();
    return 0;
}

第 2 問：券門の記録 (Ticket Gate Log)

'i' と 'o' が交互に並んでいるべき文字列に対し、最小の挿入回数で規則を満たすように修正する必要があります。元の配列をその場で書き換えるのは非効率なため、エラー箇所をカウントする方式をとります。

アルゴリズム概要

インデックスが偶数の位置には 'i' が、奇数の位置には 'o' が来るはずです。ループ内で現在の文字が期待値と異なる場合、誤りとして計上します。最終的に長さが偶数か奇数かによって追加の調整が必要かどうかを判断します。

実装コード

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

void solve_ticket_log() {
    string log_data;
    cin >> log_data;
    
    int error_count = 0;
    int len = (int)log_data.length();
    
    for (int i = 0; i < len; ++i) {
        char expected_char = (i % 2 == 0) ? 'i' : 'o';
        if (log_data[i] != expected_char) {
            error_count++;
        }
    }
    
    if (len % 2 != 0) {
        error_count++;
    }
    
    cout << error_count << endl;
}

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

第 3 問：バリエーション分割 (Easy Version)

数列をある点で左右に二分したとき、両側に含まれる相異なる整数種の合計の最大値を求める問題です。

実装のアプローチ

全体を右側のマップで初期化し、ポインタを左から右へ動かしながら要素を移動させることで計算量を抑えます。右側マップから数を減らし、左側マップに数を加えつつ、それぞれのセットサイズ（種類数）の総和を監視します。

ソースコード

#include <vector>
#include <map>
#include <iostream>
using namespace std;

void solve_variety_split() {
    int n;
    cin >> n;
    vector<int> nums(n);
    map<int, int> right_group, left_group;
    int max_distinct_sum = -1;
    
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        right_group[nums[i]]++;
    }
    
    for (int i = 0; i < n; ++i) {
        right_group[nums[i]]--;
        if (right_group[nums[i]] == 0) {
            right_group.erase(nums[i]);
        }
        
        left_group[nums[i]]++;
        
        int current_sum = (int)left_group.size() + (int)right_group.size();
        if (current_sum > max_distinct_sum) {
            max_distinct_sum = current_sum;
        }
    }
    
    cout << max_distinct_sum << endl;
}

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

第 4 問：立方体 (Cubes)

与えられた整数 N を三つの立方体の和で表せるかを検討します。数学的な変形を行い、判別式が平方数になる条件を利用します。

数理モデルと検証

a と y の二乗関係を導出し、b についての二次方程式を作成します。ここで、判別式のルート部分が整数（平方根が正整数）になる必要があり、さらに結果が整数解になることを確認します。大規模な数値に対する平方根チェックには二分探索を用います。

実装コード

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

typedef long long ll;

ll get_integer_root(ll x) {
    if (x < 0) return -1;
    if (x == 0) return 0;
    
    ll low = 1, high = x;
    ll ans = -1;
    
    while (low <= high) {
        ll mid = low + (high - low) / 2;
        ll sq = mid * mid;
        
        if (sq == x) return mid;
        else if (sq < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

void solve_cubes_problem() {
    ll N;
    cin >> N;
    
    for (ll a = 1; a * a * a <= N; ++a) {
        ll remainder = N - a * a * a;
        if (remainder <= 0) continue;
        
        if (remainder % (3 * a) != 0) continue;
        
        ll k = remainder / (3 * a);
        ll discriminant = a * a + 4 * k;
        ll d = get_integer_root(discriminant);
        
        if (d == -1) continue;
        
        if ((d - a) % 2 != 0 || d < a) continue;
        
        ll y = (d - a) / 2;
        if (y > 0) {
            ll x = a + y;
            cout << x << " " << y << endl;
            return;
        }
    }
    cout << -1 << endl;
}

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

第 5 問：ツリーのパス分解 (Tree Path Decomposition)

木構造において、各ノードが所属するパスの構成制約を満たすかどうかを検証する深さ優先探索 (DFS) の問題です。

探索戦略

子孫のサブツリーサイズを確認し、k を満たすかどうかの状態遷移を行います。具体的には、サブツリーが k より小さい場合は「接続点」として扱い、k と等しい場合はパスを完了させてクリアとし、それより大きい場合は不整合とみなします。

ソースコード

#include <vector>
#include <function>
#include <iostream>
using namespace std;

const int MAX_NODES = 1000005;
vector<int> adj[MAX_NODES];
int subtree_size[MAX_NODES];

bool validate_dfs(int u, int parent, int limit, int node_count) {
    subtree_size[u] = 1;
    int active_children = 0;
    
    for (int v : adj[u]) {
        if (v != parent) {
            bool child_valid = validate_dfs(v, u, limit, node_count);
            
            if (!child_valid) return false;
            
            if (subtree_size[v] > 0) {
                active_children++;
                subtree_size[u] += subtree_size[v];
            }
        }
    }
    
    if (subtree_size[u] < limit) {
        // パスが不完全なので接続点となる必要がある
        if (active_children > 1) return false;
    } else if (subtree_size[u] == limit) {
        // パス完結時に枝が増えすぎないこと
        if (active_children > 2) return false;
        subtree_size[u] = 0; 
    } else {
        return false;
    }
    return true;
}

void solve_tree_decomposition() {
    int n, k;
    cin >> n >> k;
    
    if (k == 1) {
        cout << "Yes" << endl;
        return;
    }
    
    for (int i = 0; i < n * k - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    if (validate_dfs(0, -1, k, n * k)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve_tree_decomposition();
    return 0;
}