問題概要

$H \times W$ のグリッドが与えられる。各マスには文字 '.' か 'T' が書かれている。今、次の操作をできるだけ多く行いたいとする。

左右に 2 文字連続した "TT" を "PC" に置き換える

操作回数の最大化を目指すときの、操作後のグリッドを出力せよ。複数通りありうる場合はどれを出力してもよい。

制約

$1 \le H \le 100$
$2 \le W \le 100$

考えたこと

問題文が少し長めなので、感触を掴むために入力例を見てみる。たとえば入力例 2 は次のようになっている。

TTT..      PCT..
.TTT.  ->  .PCT.
TTTTT      PCTPC

3 行目があえてミスリーディングになっている (入出力例をそのまま鵜呑みにしてはいけないことはとても多いので注意)。3 行目は次のようにしてもいい。

TTT..      PCT..
.TTT.  ->  .PCT.
TTTTT      PCPCT

つまり、'T' が左右に連続している箇所について、"PC" を左から詰めていけば OK。

計算量は、各行について $O(W)$ の計算量で実装できるので、全体として $O(HW)$ となる。

コード

C++

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
    
    // 各行ごとに処理する
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j + 1 < W; ++j) {
            if (S[i][j] == 'T' && S[i][j + 1] == 'T') {
                S[i][j] = 'P';
                S[i][j + 1] = 'C';
            }
        }
        cout << S[i] << endl;
    }
}

Python3

Python では、「前から順番に "TT" を "PC" で置き換える」を実行してくれる関数 replace() がある！！

すごく楽！！

H, W = map(int, input().split())
for i in range(H):
    print(input().replace("TT", "PC"))

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 297 C - PC on the Table (灰色, 300 点)

問題概要

制約

考えたこと

コード

C++

Python3