#1083731 (C++17) No.996 Phnom Penh

• 問題: No.996 Phnom Penh
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:58:29
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,119 bytes
• コンパイル時間: 574 ms
• コンパイル使用メモリ: 74,324 KB
• 実行使用メモリ: 16,072 KB
• 最終ジャッジ日時: 2025-05-14 12:59:37
• 合計ジャッジ時間: 11,637 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 21 TLE * 1 -- * 3

ソースコード

#include <iostream>
#include <string>
#include <vector> // Used for std::vector but not essential here, string manipulation is enough
#include <numeric> // Not used, can remove include

/**
 * @brief Applies Operation 2 to the given string `s`.
 * 
 * Operation 2 consists of two steps:
 * 1. Remove all occurrences of the character 'h' from the string.
 * 2. Replace all occurrences of the character 'e' with 'h' in the resulting string.
 * 
 * The operation is considered valid only if the string changes as a result.
 * The function modifies the string `s` in place.
 * 
 * @param s The string to apply Operation 2 on. Passed by reference and modified.
 * @return true If the string `s` was changed by the operation.
 * @return false If the string `s` remained unchanged after the operation.
 */
bool apply_op2(std::string& s) {
    // Keep a copy of the original string to compare later and determine if the string changed.
    std::string original_s = s; 

    // Step 1: Create an intermediate string `next_s` by removing all 'h' characters from `s`.
    std::string next_s = "";
    // Optimization: Reserve memory for `next_s` roughly equivalent to the current string length.
    // This can reduce the number of memory reallocations needed as `next_s` grows.
    next_s.reserve(s.length()); 
    for (char c : s) { // Iterate through each character of the input string `s`
        if (c != 'h') { // If the character is not 'h'
            next_s += c; // Append it to the intermediate string `next_s`
        }
    }
    
    // Clear the original string `s` to prepare for rebuilding it based on `next_s`.
    s.clear(); 
    // Optimization: Reserve memory for the final string `s`. Its length will be exactly the length of `next_s`.
    s.reserve(next_s.length()); 

    // Step 2: Rebuild `s` from `next_s`. Replace 'e' characters with 'h'.
    for (char c : next_s) { // Iterate through each character of the intermediate string `next_s`
        if (c == 'e') { // If the character is 'e'
            s += 'h'; // Append 'h' to the final string `s`
        } else { // For any other character
            s += c; // Append the character itself to `s`
        }
    }

    // Return true if the final string `s` is different from the `original_s`.
    // This indicates that Operation 2 successfully changed the string.
    return s != original_s;
}


int main() {
    // Optimize standard C++ I/O operations for speed.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    std::string s; // Declare a string variable to store the input.
    std::cin >> s; // Read the input string from standard input.
    
    long long op_count = 0; // Initialize a counter for the total number of operations performed. Using long long for potentially large counts.
    
    std::string target = "phnom"; // The substring to search for in Operation 1.
    std::string replacement = "penh"; // The string to replace "phnom" with in Operation 1.

    // Main loop: continues as long as operations can be performed that change the string.
    // This implements a greedy strategy: prioritize Op1, then try Op2 if Op1 is not possible.
    while (true) { 
        // --- Try Operation 1 ---
        // Find the starting position (`pos`) of the first occurrence of the target substring "phnom".
        // `std::string::npos` is returned if the substring is not found.
        size_t pos = s.find(target); 
        
        // Check if "phnom" was found in the string `s`.
        if (pos != std::string::npos) {
             // If "phnom" is found, perform Operation 1: replace it with "penh".
             // `s.replace(pos, target.length(), replacement)` replaces the substring of length `target.length()` starting at `pos` with `replacement`.
             s.replace(pos, target.length(), replacement); 
             op_count++; // Increment the operation counter.
             // After successfully applying Op1, restart the `while` loop immediately using `continue`.
             // This ensures that we always check for Op1 possibilities first after any change.
             continue; 
        }

        // --- If Op1 was not possible, Try Operation 2 ---
        
        // Before attempting Op2, check if the string contains 'h' or 'e'. 
        // Op2 requires at least one 'h' to remove or one 'e' to replace with 'h' to potentially change the string.
        // If neither 'h' nor 'e' exists, Op2 cannot change the string.
        bool has_h_or_e = false; // Flag to track if 'h' or 'e' is present.
        for(char c : s) { // Iterate through the characters of the string `s`.
            if (c == 'h' || c == 'e') { // If 'h' or 'e' is found
                has_h_or_e = true; // Set the flag to true.
                break; // Exit the loop early as we've confirmed presence.
            }
        }

        // Proceed with Op2 only if 'h' or 'e' was found in the string.
        if (has_h_or_e) {
             // Attempt to apply Op2. The function `apply_op2` modifies `s` in place.
             // It returns `true` if the string was changed, `false` otherwise.
             if (apply_op2(s)) { 
                 op_count++; // If Op2 successfully changed the string, increment the operation counter.
                 // After successfully applying Op2, restart the `while` loop using `continue`.
                 // This allows checking if Op2 created new opportunities for Op1.
                 continue; 
             }
        }
        
        // --- Termination Condition ---
        // If the code reaches this point, it implies that:
        // 1. Operation 1 ("phnom" -> "penh") could not be applied (no "phnom" found).
        // 2. AND Operation 2 either was not applicable (no 'h' or 'e') or was applied but did not change the string.
        // In this state, no further operations can modify the string according to the rules.
        // Therefore, break out of the `while` loop.
        break; 
    }
    
    // Print the final total count of operations performed.
    std::cout << op_count << std::endl;
    
    return 0; // Indicate successful program execution.
}