本日は「文字列」をテーマとした2つの問題を解きました。

問題1：高精度浮動小数点の加算

この問題は典型的なアルゴリズム問題であり、桁数が非常に大きな数値の加算を効率的に処理する方法を習得できます。

問題リンク：浮点数加算

解決策として、整数部と小数部を別々に処理するアプローチを採用しました。以下が実装コードです：

#include <cstdio>
#include <string>
#include <algorithm>

void addDecimalPart(const std::string& num1, const std::string& num2, 
                    int& carry, std::string& result) {
    int len1 = num1.length();
    int len2 = num2.length();
    int maxLen = std::max(len1, len2);
    
    std::string a = num1;
    std::string b = num2;
    
    // 長さの揃えるためにゼロ埋め
    if (len1 < maxLen) {
        a.append(maxLen - len1, '0');
    } else if (len2 < maxLen) {
        b.append(maxLen - len2, '0');
    }
    
    result.resize(maxLen);
    
    for (int i = maxLen - 1; i >= 0; --i) {
        int sum = (a[i] - '0') + (b[i] - '0') + carry;
        if (sum <= 9) {
            result[i] = sum + '0';
            carry = 0;
        } else {
            result[i] = (sum - 10) + '0';
            carry = 1;
        }
    }
}

void addIntegerPart(const std::string& num1, const std::string& num2, 
                    int carry, std::string& result) {
    result.clear();
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int currentCarry = carry;
    
    while (i >= 0 || j >= 0 || currentCarry == 1) {
        int digit1 = (i >= 0) ? num1[i] - '0' : 0;
        int digit2 = (j >= 0) ? num2[j] - '0' : 0;
        int sum = digit1 + digit2 + currentCarry;
        
        if (sum <= 9) {
            result.insert(result.begin(), sum + '0');
            currentCarry = 0;
        } else {
            result.insert(result.begin(), (sum - 10) + '0');
            currentCarry = 1;
        }
        
        --i;
        --j;
    }
}

int main() {
    char input1[1000], input2[1000];
    
    while (std::scanf("%s %s", input1, input2) != EOF) {
        std::string str1 = input1;
        std::string str2 = input2;
        
        // 小数点の位置を特定
        size_t pos1 = str1.find('.');
        size_t pos2 = str2.find('.');
        
        std::string intPart1 = str1.substr(0, pos1);
        std::string decPart1 = str1.substr(pos1 + 1);
        std::string intPart2 = str2.substr(0, pos2);
        std::string decPart2 = str2.substr(pos2 + 1);
        
        std::string decimalResult;
        int carry = 0;
        addDecimalPart(decPart1, decPart2, carry, decimalResult);
        
        std::string integerResult;
        addIntegerPart(intPart1, intPart2, carry, integerResult);
        
        std::printf("%s.%s\n", integerResult.c_str(), decimalResult.c_str());
    }
    
    return 0;
}

学習のポイント

• 文字列とvectorの類似性：stringクラスとvector<T>は同様のメンバ関数（size()、push_back()など）を持ち、[]演算子による要素アクセスが可能。ただし、いずれもpush_front()は直接サポートされていない。
• size()関数の使用注意：ループ条件内でsize()関数を呼び出す場合、コンテナサイズが変更されると正しく動作しない可能性がある。
• 文字コードの活用：文字列間の算術演算は、内部ではASCIIコードに基づいて処理される。
• 高精度計算の原理：文字'3'と'4'の加算は、'0'からのオフセットを用いて計算される。具体的には、'3' + '4' = ('0' + 3) + ('0' + 4) = '7'となる。

問題2：文字列のグループ別循環回転

この問題は、文字列を3つのグループに分類し、それぞれに対して異なるオフセットで循環回転を適用するアルゴリズムを実装するものです。

問題リンク：Wの暗号

文字をASCIIコードに基づき3つのグループに分類します：

• 第1グループ：'a'〜'i'（小文字アルファベットの前半）
• 第2グループ：'j'〜'r'（中盤）
• 第3グループ：'s'〜'z'（後半）

#include <cstdio>
#include <string>
#include <vector>

void classifyIndices(const std::string& text, 
                     std::vector<int>& group1,
                     std::vector<int>& group2,
                     std::vector<int>& group3) {
    for (int idx = 0; idx < static_cast<int>(text.length()); ++idx) {
        char ch = text[idx];
        if (ch >= 'a' && ch <= 'i') {
            group1.push_back(idx);
        } else if (ch >= 'j' && ch <= 'r') {
            group2.push_back(idx);
        } else {
            group3.push_back(idx);
        }
    }
}

void rotateRight(std::string& text, const std::vector<int>& indices, int offset) {
    if (indices.empty() || offset == 0) {
        return;
    }
    
    int len = indices.size();
    int actualOffset = offset % len;
    
    if (actualOffset == 0) {
        return;
    }
    
    std::string tempBuffer;
    tempBuffer.reserve(actualOffset);
    
    // 後方の要素を一時保存
    for (int i = len - actualOffset; i < len; ++i) {
        tempBuffer.push_back(text[indices[i]]);
    }
    
    // 前方の要素を後方へ移動
    for (int i = len - actualOffset - 1; i >= 0; --i) {
        text[indices[i + actualOffset]] = text[indices[i]];
    }
    
    // 保存した要素を先頭に配置
    for (int i = 0; i < actualOffset; ++i) {
        text[indices[i]] = tempBuffer[i];
    }
}

int main() {
    int offset1, offset2, offset3;
    
    while (std::scanf("%d %d %d", &offset1, &offset2, &offset3) == 3) {
        if (offset1 == 0 && offset2 == 0 && offset3 == 0) {
            break;
        }
        
        char inputBuffer[1000];
        std::scanf("%s", inputBuffer);
        std::string text = inputBuffer;
        
        std::vector<int> groupA, groupB, groupC;
        classifyIndices(text, groupA, groupB, groupC);
        
        rotateRight(text, groupA, offset1);
        rotateRight(text, groupB, offset2);
        rotateRight(text, groupC, offset3);
        
        std::printf("%s\n", text.c_str());
    }
    
    return 0;
}

学習のポイント

• 手動シミュレーションの重要性：纸上での動作確認を怠ると、実装に時間がかかることがある。アルゴリズムを理解するには、具体的な例で動作を追跡することが有効。
• 循環回転の実装：右回転は「後方の要素を一時保存→前方要素を後方へ移動→保存した要素を先頭に配置」の3段階で実装可能。
• 非連続部分文字列の操作：連続していない文字の集合を操作する場合、元の文字列内でのインデックスを配列に記録し、その配列を通じて間接的にアクセスする方法が有効。
• 境界条件の考慮：グループ内の文字数が0の場合の処理が必須。