DigitalArts プログラミングコンテスト2012 A - C-Filter

備忘録

問題

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
# MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = sl()
    N = ii()

    for _ in range(N):
        t = iss()
        for i in range(len(S)):
            if S[i] == t:
                # ルール1
                S[i] = '*' * len(S[i])
            if len(S[i]) == len(t):
                # ルール2
                for j in range(len(S[i])):
                    if t[j] == '*' or t[j] == S[i][j]:
                        continue
                    else:
                        break
                else:
                    S[i] = '*' * len(S[i])
    print(*S)


if __name__ == '__main__':
    main()

考え方

アルゴリズムよりも純粋な実装力寄りの問題
ルールに従って文字列の変換を行います。

明示されているルールは二つ

NGワードと完全一致する単語を*に置換すること
NGワードに*が含まれている場合にはすべての英文字と一致する

ルール１に関しては単純で、NGワードがabcの場合には、
与えられた文字列のうちabcと完全一致する文字列を***に変換します。
ルール２に関しては、判定が必要になります。
NGワードに*が含まれている場合にはどのような英文字にも当てはめることができるので、
NGワードと文字列の長さが一致している、かつNGワードの*以外の英文字が一致しているか判定する必要があります。
ただし、与えられる英文字も、NGワードの数もあまり長く１００以下程度なので素朴に実装することで大抵の場合には制限時間内に間に合うと思います。