結果

問題 No.1367 文字列門松
コンテスト
ユーザー Mottchan
提出日時 2025-08-21 11:30:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 7,252 bytes
コンパイル時間 380 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 67,952 KB
最終ジャッジ日時 2025-08-21 11:30:18
合計ジャッジ時間 3,647 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

## gcd(x, y):最大公約数, lcm(x, y):最小公倍数, factorial(n):階乗n!, prem(n, k):nPk(n, k), comb(n, r):二項係数nCr
from math import gcd, lcm, factorial, perm, comb

# 0~9を並び替えるならpermutationsかconbinations,N列のカテゴリを作るにはproduct
from itertools import product, permutations, combinations, accumulate

from functools import lru_cache  # @lru_cache(maxsize=128)
import operator
from string import ascii_uppercase, ascii_lowercase, digits  # 英字(大文字), 英字(小文字), 数字

MOD = 998244353


def II():
    return int(input())


def LI():
    return list(input())


def LMI():
    return list(map(int, input().split()))


def LMS():
    return list(map(str, input().split()))


def LLMI(x):
    return [list(map(int, input().split())) for _ in range(x)]


def LLMS(x):
    return [list(input()) for _ in range(x)]


def CUM(x: list, func=None, initial: int = None) -> list:
    """
    func:累積の仕方を指定する。
        operator.mul:掛け算
        operator.sub:引き算
        max:最大値
        min:最小値
    initial:初期値, Noneならx[0]が第一引数の数値になる
    """
    return list(accumulate(x, func=func, initial=initial))


def yesno(tf: bool):
    if tf:
        return print("Yes")
    else:
        return print("No")


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def group(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return "".join(f"{r}: {m}" for r, m in self.group().items())


def inverse_element(num: int):
    """
    逆元の作成
    ax ≡ 1 (mod p)となるxは、fetmatの小定理より
    a * a^(p-2) ≡ 1 (mod p)であるため、
    a^(p-2) (mod p) は逆元である
    """
    return pow(num, MOD - 2, MOD)


def make_graph(n: int, lmi: list, idx_0: bool = True, is_direct: bool = False):
    graph = [[] for _ in range(n)]
    for i in range(len(lmi)):
        a, b = lmi[i]
        if idx_0:
            a -= 1
            b -= 1
        # 有向グラフであれば1方向にappendする。
        graph[a].append(b)
        if not is_direct:
            graph[b].append(a)

    return graph


def bfs(n: int, graph: list[list[int]], s: int = 0, g: int = None):
    """
    s:start地点、指定しなければ頂点0から
    g:goal地点、指定しなければ端まで
    """
    start = (s, 0)
    d = deque([start])
    TF = [False] * n
    while d:
        crr, cnt = d.popleft()
        TF[crr] = True
        # if crr == g:
        #     return cnt
        for nxt in graph[crr]:
            if TF[nxt]:
                continue
            # d.append((nxt, cnt + 1))
            TF[nxt] = True

    return -1


def dfs(n: int, graph: list[list[int]], s: int = 0, g: int = None):
    """
    s:start地点、指定しなければ頂点0から
    g:goal地点、指定しなければ端まで
    """
    start = (s, 0)
    d = deque([start])
    TF = [False] * n
    while d:
        crr, cnt = d.pop()
        TF[crr] = True
        # if crr == g:
        #     return cnt
        for nxt in graph[crr]:
            if TF[nxt]:
                continue
            # d.append((nxt, cnt + 1))
            TF[nxt] = True


def dijkstra(n: int, graph: list[list[int, int]], s: int = 0):
    """
    s:start地点、指定しなければ頂点0から
    """

    que = []
    heappush(que, (0, s))
    TF = [False] * n
    # 各頂点の最短経路を格納する
    ans = [0] * n

    while que:
        cnt, crr = heappop(que)
        if TF[crr]:
            continue
        # 最短経路確定
        TF[crr] = True
        ans[crr] = cnt

        for nxt, val in graph[crr]:
            # 最短経路が確定しているところは除く
            if TF[nxt]:
                continue
            heappush(que, (cnt + val, nxt))
    else:
        return ans


def make_adjacency_matrix(n: int, nodes: list):
    matrix = [[float("INF")] * n for _ in range(n)]
    for node in nodes:
        v, m, c = node
        matrix[v][m] = c
        matrix[m][v] = c
    for i in range(n):
        matrix[i][i] = 0

    return matrix


def floyd_warchall_algorithm(n, matrix):
    """
    n:
        [int]頂点の数
    matrix:
        [list]隣接行列
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    return matrix


def lis(A: list):
    length = 0
    n = len(A)
    dp = [float("INF") for _ in range(n + 1)]
    dp[0] = -float("INF")

    for i in range(n):
        left = 0
        right = n

        while right - left > 1:
            mid = (right + left) // 2
            if dp[mid] < A[i]:
                left = mid
            else:
                right = mid

        dp[left + 1] = A[i]
        length = max(length, left + 1)

    return length


def manacher(s):
    T = "#" + "#".join(s) + "#"
    n = len(T)
    P = [0] * n  # 各位置での回文半径
    C, R = 0, 0  # 中心位置Cと回文右端R

    for i in range(n):
        mirr = 2 * C - i  # iの鏡像位置

        if i < R:
            P[i] = min(R - i, P[mirr])

        # 回文の中心を基準に左右に広げる
        a, b = i + P[i] + 1, i - P[i] - 1
        while a < n and b >= 0 and T[a] == T[b]:
            P[i] += 1
            a += 1
            b -= 1

        # 回文が右端を超えたら中心を更新
        if i + P[i] > R:
            C, R = i, i + P[i]

    return P  # 回文半径を返す

  
def execute():
    s = LI()
    t = list("kadomatsu")

    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # print(dp)
    ans = dp[len(s)][len(t)]
    # print(ans)
    if len(s) == ans:
        print('Yes')
    else:
        print('No')



if __name__ == "__main__":
    T = 1
    for _ in range(T):
        execute()
0