C. Anya and 1100

問題URL

Problem - C - Codeforces

解法

文字列中の特定のパターン「1100」の出現回数を管理する問題です。ある位置の文字を変更したとき、それが「1100」の存在にどのような影響を与えるかを考えます。

変更による影響は三種類あります：

• 「1100」の個数が1増える
• 「1100」の個数が1減る
• 変化なし

変更箇所について、それが「1100」のどの位置（1番目〜4番目）に対応するかを列挙し、その位置から長さ4の 부분文字列を抽出して「1100」と一致するかをチェックします。一致すればその位置は「1100」に貢献しており、一致しなければ貢献していないと判断できます。

変更前後の貢献度を比較し、差分を出力します。

実装

#include <bits/stdc++.h>
using namespace std;

bool checkContribution(int idx, const string& str) {
    const string target = "1100";
    
    // idx が最初の位置の場合
    if (idx + 3 < str.size() && str.substr(idx, 4) == target) return true;
    
    // idx が2番目の位置の場合
    if (idx - 1 >= 0 && idx + 2 < str.size() && str.substr(idx - 1, 4) == target) return true;
    
    // idx が3番目の位置の場合
    if (idx - 2 >= 0 && idx + 1 < str.size() && str.substr(idx - 2, 4) == target) return true;
    
    // idx が4番目の位置の場合
    if (idx - 3 >= 0 && str.substr(idx - 3, 4) == target) return true;
    
    return false;
}

void solve() {
    string s;
    int q;
    cin >> s >> q;
    
    const string target = "1100";
    int count = 0;
    
    // 初期状態の出現回数をカウント
    for (int i = 0; i + 3 < (int)s.size(); i++) {
        if (s.substr(i, 4) == target) count++;
    }
    
    while (q--) {
        int pos;
        char ch;
        cin >> pos >> ch;
        pos--;
        
        if (s[pos] != ch) {
            int before = checkContribution(pos, s);
            s[pos] = ch;
            int after = checkContribution(pos, s);
            
            if (before && !after) count--;
            else if (!before && after) count++;
        }
        
        cout << (count > 0 ? "YES" : "NO") << '\n';
    }
}

void setup() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setup();
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

D. I Love 1543

問題URL

Problem - D - Codeforces

解法

グリッドの各layer（周回路）について考えます。各layerは独立して処理できます。

各layerについて、4辺の文字を 순서대로読み取り、1つの文字列を形成します。起点はどこでも良い（环形の性质）ので、字符串の先頭3文字を末尾に追加することで闭环を模拟します。

形成された文字列において「1543」が出現する回数をカウントすれば、それがそのlayerの答えになります。全layerの合計が最終答えとなります。

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<string> grid(n + 1);
        for (int i = 1; i <= n; i++) {
            string row;
            cin >> row;
            grid[i] = " " + row;
        }
        
        const string target = "1543";
        int total = 0;
        
        int layers = min(n, m) / 2;
        for (int layer = 1; layer <= layers; layer++) {
            string layerStr;
            
            // 上辺 (左から右)
            for (int j = layer; j <= m - layer + 1; j++)
                layerStr += grid[layer][j];
            
            // 右辺 (上から下)
            for (int i = layer + 1; i <= n - layer + 1; i++)
                layerStr += grid[i][m - layer + 1];
            
            // 下辺 (右から左)
            for (int j = m - layer; j >= layer; j--)
                layerStr += grid[n - layer + 1][j];
            
            // 左辺 (下から上)
            for (int i = n - layer; i > layer; i--)
                layerStr += grid[i][layer];
            
            // 闭环处理
            layerStr += layerStr.substr(0, 3);
            
            // 出現回数をカウント
            for (int i = 0; i + 3 < (int)layerStr.size(); i++) {
                if (layerStr.substr(i, 4) == target) total++;
            }
        }
        
        cout << total << '\n';
    }
    
    return 0;
}