課題1：最長共通部分列（LCS）の算出

技術概要

2つの文字列が与えられた際、順序を維持したまま両者に共通して現れる部分列のうち、最長のものを特定しその長さを返すアルゴリズムを実装する。入力ストリームには複数のテストケースが連続して含まれており、各文字列の最大長は1000文字に制限される。元の試験仕様では文字列長が等しく重複文字を含まない条件が付されていたが、本実装では汎用的な動的計画法アプローチを採用し、任意の文字列組み合わせに対応する。

入出力定義

• 入力形式：1行に2つの文字列を空白区切りで記述。EOFまで複数ケースを処理。
• 出力形式：各データセットに対し、算出されたLCS長を整数で標準出力。
• 制約条件：文字列長 ≤ 1000

参考実装（C++）

2次元DPテーブルを用い、部分問題の最適解をボトムアップで構築する。メモリ配置を明確にするため、インデックスオフセットを適用し、状態遷移を条件分岐で整理している。

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

int resolve_lcs(const std::string& src_a, const std::string& src_b) {
    size_t len_a = src_a.length();
    size_t len_b = src_b.length();
    
    // DP行列の初期化（0行目・0列目はベースケースとして0埋め）
    std::vector<std::vector<int>> matrix(len_a + 1, std::vector<int>(len_b + 1, 0));

    for (size_t row = 1; row <= len_a; ++row) {
        for (size_t col = 1; col <= len_b; ++col) {
            if (src_a[row - 1] == src_b[col - 1]) {
                matrix[row][col] = matrix[row - 1][col - 1] + 1;
            } else {
                matrix[row][col] = std::max(matrix[row - 1][col], matrix[row][col - 1]);
            }
        }
    }
    return matrix[len_a][len_b];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string token_x, token_y;
    while (std::cin >> token_x >> token_y) {
        std::cout << resolve_lcs(token_x, token_y) << "\n";
    }
    return 0;
}

課題2：固定シフト暗号の復号処理

技術概要

古典的な換字式暗号であるシーザー暗号の復号モジュールを作成する。暗号化時にアルファベットを5文字分後ろに循環シフトしているため、復号処理では5文字分前に戻す逆変換を行う。変換対象は大文字アルファベット（A-Z）のみとし、空白・句読点・その他の記号は原形を維持する。入力データは制御キーワードで区切られたブロック構造で提供され、終端マーカーまで連続処理する。

入出力定義

• データ構造：各ケースはSTARTで開始し、次に暗号文（1〜200文字）、最後にENDが続く。
• 終了条件：単独行のENDOFINPUTを検出した時点で処理を打ち切る。
• 出力形式：復号された平文をケースごとに1行出力。
• 制約条件：データセット数 ≤ 100、各行長 ≤ 200

参考実装（C++）

行単位読み込みとキーワードマッチングを組み合わせ、ストリーム制御を行う。文字変換部ではASCIIコードベースの算術演算を採用し、負の剰余結果を防ぐためモジュロ演算前に周期長（26）を加算するロジックを組み込んでいる。

#include <iostream>
#include <string>
#include <cctype>

std::string decode_shift_cipher(const std::string& encrypted_line, int offset) {
    std::string decoded_result;
    decoded_result.reserve(encrypted_line.size());

    for (char symbol : encrypted_line) {
        if (std::isupper(static_cast<unsigned char>(symbol))) {
            // 5文字前の位置へ循環戻し（負値対策で+26を実施）
            int base_idx = symbol - 'A';
            int restored_idx = (base_idx - offset + 26) % 26;
            decoded_result.push_back(static_cast<char>('A' + restored_idx));
        } else {
            // 非アルファベットはそのまま通過
            decoded_result.push_back(symbol);
        }
    }
    return decoded_result;
}

int main() {
    std::string input_line;
    const int reverse_shift = 5;

    while (std::getline(std::cin, input_line)) {
        if (input_line == "ENDOFINPUT") {
            break;
        }
        if (input_line == "START") {
            // 暗号文行の読み込みと復号実行
            std::getline(std::cin, input_line);
            std::cout << decode_shift_cipher(input_line, reverse_shift) << "\n";
            // 終了マーカー "END" の消費
            std::getline(std::cin, input_line);
        }
    }
    return 0;
}