A - Welcome to AtCoder Land

この問題では、入力された二つの文字列が特定の値と完全に一致するかを確認する基本的な処理が必要です。

実装ロジック

標準入力で受け取ったストリングスを入力変数へ保存し、固定されたターゲット文字列と比較します。両方が一致した場合のみ「Yes」を出力し、それ以外の場合は「No」を返却します。

#include <iostream>
#include <string>

using namespace std;

int main()
{
    // 入力を受け取る変数を明確な名前に変更
    string word_one, word_two;
    cin >> word_one >> word_two;

    // 期待される組み合わせとの一致判定
    bool match = (word_one == "AtCoder") &amp;&amp; (word_two == "Land");

    if (match)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

解説要点

文字列の等価比較が可能な言語機能を活用したシンプルな分岐処理です。

---

B - Ticket Counter

窓口でのサービス開始時刻および終了時刻のシミュレーションを行います。次の利用者は現在の処理完了時間より後に開始できないという制約があります。

実装ロジック

到着時刻リストを読み込み、それぞれの窓口処理開始時間を順次計算します。直前の処理終了時刻を超えていない場合は処理開始時刻が更新されます。処理開始時間から一定の所要時間が加算されて完了時刻となります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int num_people;
    int service_gap;
    
    if (!(cin >> num_people >> service_gap)) return 0;

    vector<int> arrivals(num_people + 1);
    for (int i = 1; i <= num_people; ++i)
    {
        cin >> arrivals[i];
    }

    int current_time_point = 0;
    
    for (int i = 1; i <= num_people; ++i)
    {
        // 次の利用可能時刻は、到着時刻と直前完了時刻の最大値になる
        if (arrivals[i] > current_time_point)
        {
            current_time_point = arrivals[i];
        }
        
        // サービス完了時刻を計算して出力
        current_time_point += service_gap;
        cout << current_time_point << endl;
    }

    return 0;
}

解説要点

イベント順に状態を更新していく貪欲的なシミュレーションの実行です。

---

C - Popcorn

複数の popcorn パターン（ビットマスク）から、指定されたすべての位をオンにする最小個数の選択を求めます。

実装ロジック

各文字列を整数値に変換し、ビット演算で状態を管理します。全ての部分集合を試行し、目標となる全部 bit が立つ状態になった際の最小要素数を探索します。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef long long ll;

int main()
{
    int total_patterns;
    int target_bits;
    cin >> total_patterns >> target_bits;

    vector<int> pattern_values(total_patterns + 1, 0);
    
    for (int i = 1; i <= total_patterns; ++i)
    {
        string s_val;
        cin >> s_val;
        int val = 0;
        for (char c : s_val)
        {
            val = (val << 1) | ((c == 'o') ? 1 : 0);
        }
        pattern_values[i] = val;
    }

    int min_selection_count = total_patterns;
    int limit_mask = (1 << total_patterns);

    // 全子セットの列挙
    for (int mask = 0; mask < limit_mask; ++mask)
    {
        int combined_state = 0;
        int count = 0;

        for (int i = 1; i <= total_patterns; ++i)
        {
            if ((mask >> (i - 1)) & 1)
            {
                combined_state |= pattern_values[i];
                count++;
            }
        }

        // 目標状態かどうか確認
        int goal = (1 << target_bits) - 1;
        if (combined_state == goal)
        {
            if (count < min_selection_count)
            {
                min_selection_count = count;
            }
        }
    }

    cout << min_selection_count << endl;

    return 0;
}

解説要点

bitmask を用いた部分集合列挙により、最適解を見つける探索アルゴリズムです。

---

D - Souvenirs

ソート済みの配列において、特定条件を満たす最小値を選択しながら全体への適用可能性をチェックします。

実装ロジック

商品リストと注文リストを昇順ソートします。各注文に対して、前回の選択index よりも後の範囲内で、条件値以上の最小価格を持つ商品を二分探索で見つけます。見つからなければ不可と判断し、成功時の合計コストを計算します。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
    int n_items;
    int m_orders;
    if (!(cin >> n_items >> m_orders)) return 0;

    vector<ll> prices(n_items + 1);
    for (int i = 1; i <= n_items; ++i)
    {
        cin >> prices[i];
    }

    vector<ll> orders(m_orders + 1);
    for (int i = 1; i <= m_orders; ++i)
    {
        cin >> orders[i];
    }

    sort(prices.begin() + 1, prices.end());
    sort(orders.begin() + 1, orders.end());

    int search_ptr = 1;
    bool possible = true;
    ll total_cost = 0;

    for (int i = 1; i <= m_orders; ++i)
    {
        int l = search_ptr;
        int r = n_items;
        int found_idx = -1;

        // 範囲内での二分探索
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (prices[mid] < orders[i])
            {
                l = mid + 1;
            }
            else
            {
                found_idx = mid;
                r = mid - 1;
            }
        }

        if (found_idx == -1 || prices[found_idx] < orders[i])
        {
            possible = false;
            break;
        }

        total_cost += prices[found_idx];
        search_ptr = found_idx + 1;
    }

    if (possible)
    {
        cout << total_cost << endl;
    }
    else
    {
        cout << "-1" << endl;
    }

    return 0;
}

解説要点

ソートと二分探索を組み合わせた、選別と検証を行う効率的な処理パターンです。

---

E - Alphabet Tiles

複数の文字種類の限定枚数を用いて長さ k の並びを作る総数を、動的計画法と組合せ論で計算します。

実装ロジック

文字種ごとに使える回数が与えられます。DP 状態として、i 番目の文字種まで使用して、全体の長さが j となる場合の組み合わせ数を記録します。組込関数を用いて組み合わせ係数を事前計算し、遷移ループで累積和を計算します。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MOD = 998244353;
ll combinations[2010][2010];
ll dp_states[30][1010];

void calc_combinations()
{
    for (int i = 0; i <= 2000; ++i)
    {
        combinations[i][0] = 1;
        for (int j = 1; j <= i; ++j)
        {
            combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;
        }
    }
}

int main()
{
    int k_length;
    cin >> k_length;

    calc_combinations();

    vector<int> char_counts(27, 0);
    for (int i = 1; i <= 26; ++i)
    {
        cin >> char_counts[i];
    }

    // DP 初期化
    for (int i = 0; i <= 26; ++i)
    {
        for (int j = 0; j <= k_length; ++j)
        {
            dp_states[i][j] = 0;
        }
    }
    
    dp_states[0][0] = 1;

    for (int i = 1; i <= 26; ++i)
    {
        for (int j = 0; j <= k_length; ++j)
        {
            // 同じ文字を使わない場合
            dp_states[i][j] = dp_states[i - 1][j];

            // 現在文字を使う場合
            for (int cnt = 1; cnt <= char_counts[i]; ++cnt)
            {
                if (j < cnt) break;
                
                ll ways = (dp_states[i - 1][j - cnt] * combinations[j][cnt]) % MOD;
                dp_states[i][j] = (dp_states[i][j] + ways) % MOD;
            }
        }
    }

    ll result_sum = 0;
    for (int len = 1; len <= k_length; ++len)
    {
        result_sum = (result_sum + dp_states[26][len]) % MOD;
    }

    cout << result_sum << endl;

    return 0;
}

解説要点

組み合わせ数による DP 遷移を行い、複雑な順序数を効率的に計算する技法です。