A. Access Denied：パスワードの推測と応答時間解析

この問題は、サーバーからの応答時間を利用してパスワードを推測する対話型の課題です。パスワードの最大長は20文字であり、推測した文字列の長さが正解と異なる場合、応答には5msの遅延が生じます。また、文字ごとの照合には9msの遅延が加算されるという仕組みを利用します。

まず、長さ1から20までの文字列を順次送信し、応答時間が5msを超えるタイミングで正解の文字列長を特定します。長さが確定した後は、各文字位置において、使用可能な62文字（大文字、小文字、数字）を1文字ずつ試行します。ある文字が正解である場合、応答時間に9msが加算されるため、この閾値を超えた時点でその文字を採用し、次の位置の推測へ進みます。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    const string candidates = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    int length = 0;
    string response;

    // パスワードの長さを特定するフェーズ
    for (int len = 1; len <= 20; ++len) {
        cout << string(len, 'A') << endl;
        getline(cin, response);
        
        if (response == "ACCESS GRANTED") return 0;

        int timeTaken = 0;
        for (char c : response) {
            if (isdigit(c)) timeTaken = timeTaken * 10 + (c - '0');
        }

        if (timeTaken != 5) {
            length = len;
            break;
        }
    }

    string password(length, 'A');

    // 各文字を総当たりで特定するフェーズ
    for (int pos = 0; pos < length; ++pos) {
        for (char ch : candidates) {
            password[pos] = ch;
            cout << password << endl;
            getline(cin, response);

            if (response == "ACCESS GRANTED") return 0;

            int timeTaken = 0;
            for (char c : response) {
                if (isdigit(c)) timeTaken = timeTaken * 10 + (c - '0');
            }

            // 応答時間の増分から正解文字を判断する
            if (timeTaken >= 5 + (pos + 2) * 9) {
                break;
            }
        }
    }

    return 0;
}

J. Jet Set：経線の網羅判定と日付変更線の処理

この問題では、与えられたフライト経路が地球上のすべての経線を通過したかどうかを判定します。すべての経線を通過することを「世界一周」と定義します。2点間の経度差がちょうど180度である場合、その経路は最短経路となり、かつすべての経線を通過するため、即座に「yes」と判定できます。

それ以外の場合、2点間の経度差が180度より大きいか小さいかによって、通過する経線の範囲が変化します。特に180度を超える移動では、日付変更線を越えるルート（最短ルート）を選択するため、経度の走査範囲が180度地点で折り返すような挙動になります。データサイズが小さいため、各移動区間において通過する経度を配列などで記録し、最終的に未訪問の経度が存在しないかを確認します。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> lons(n);
    
    // 経度データを読み込み、-180〜180の範囲を0〜360に正規化
    for (int i = 0; i < n; ++i) {
        int lat, lon;
        cin >> lat >> lon;
        lons[i] = lon + 180;
    }

    // 経度を0.5刻みで記録するための配列（サイズは360 * 2 = 720）
    vector<bool> visited(721, false);

    for (int i = 0; i < n; ++i) {
        int curr = lons[i];
        int next = lons[(i + 1) % n];
        int diff = abs(next - curr);

        // 経度差が180度なら必ず全経線を通る
        if (diff == 180) {
            cout << "yes\n";
            return 0;
        }

        if (diff > 180) {
            // 180度を超える場合、日付変更線を越える範囲をマークする
            // 範囲を二つに分けて処理（折り返し）
            for (int j = min(curr, next) * 2; j <= 720; ++j) visited[j] = true;
            for (int j = 0; j <= max(curr, next) * 2; ++j) visited[j] = true;
        } else {
            // 通常の移動範囲をマーク
            int start = min(curr, next) * 2;
            int end = max(curr, next) * 2;
            for (int j = start; j <= end; ++j) visited[j] = true;
        }
    }

    // 未訪問の経度を探索
    for (int i = 0; i <= 720; ++i) {
        if (!visited[i]) {
            printf("no %.1lf\n", i / 2.0 - 180);
            return 0;
        }
    }

    cout << "yes\n";
    return 0;
}

K. Knitpicking：靴下のペア作成と最悪ケースの計算

種類の異なる靴下が混在しており、左右の区別があるもの（left, right）と、どちらの足にも使用できるもの（any）が存在します。確実にペアを作成するために必要な靴下の最小引き抜き数を求める問題です。

まず、ペアを作成することが物理的に可能かどうかを判定します。これは、同じ種類で左右が揃っている場合、あるいは「any」が2つ以上存在する場合などに成立します。可能である場合、各種類ごとに最悪のケースを考えます。左右の区別がある靴下については、多い方の足の靴下をすべて引く必要があります。「any」のみの種類については、最低1つ引けばその種類に関する条件を満たせます。これらを合計し、最後に確実にどれかのペアが完成することを保証するために+1を加えた値が答えとなります。

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

struct SockPile {
    int left = 0;
    int right = 0;
    int any = 0;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    map<string, SockPile> sockInventory;
    int n;
    cin >> n;
    bool possible = false;

    for (int i = 0; i < n; ++i) {
        string color, type;
        int count;
        cin >> color >> type >> count;

        if (type == "left") sockInventory[color].left = count;
        else if (type == "right") sockInventory[color].right = count;
        else sockInventory[color].any = count;

        // ペア成立の可能性チェック
        if (type == "any" && count >= 2) possible = true;
        if (type == "left" && sockInventory[color].right > 0) possible = true;
        if (type == "right" && sockInventory[color].left > 0) possible = true;
    }

    if (!possible) {
        cout << "impossible\n";
    } else {
        int required = 0;
        for (const auto& item : sockInventory) {
            const auto& data = item.second;
            if (data.left == 0 && data.right == 0) {
                // anyのみの場合は1つでOK（他のanyとペアになるか、別の種類のペアになる）
                required += 1; 
            } else {
                // 左右がある場合は多い方を引くのが最悪
                required += max(data.left, data.right);
            }
        }
        // どれか1つ余分に引くことでペアが確定する
        cout << required + 1 << '\n';
    }

    return 0;
}