AGC022 A - Diverse Word

備忘録

問題

atcoder.jp

回答

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 = iss()
    ret = []
    for i in range(ord('a'), ord('z')+1):
        for j in range(len(S)+1):
            if chr(i) in S[:j]:
                continue
            ret.append(S[:j] + chr(i))

    ret.sort()
    idx = bisect.bisect_left(ret, S)
    print(-1 if len(ret) == idx+1 else ret[idx+1])


if __name__ == '__main__':
    main()

考え方

愚直に多彩な文字列を全て生成して、
そのうち条件に一致する文字列を探索する回答を行いました。

英小文字iと文字列Sを左からj番めまで抜き出した文字列のうち、
英小文字iが存在していない場合には結合した文字列を生成します。
全ての多彩な文字列のパターンを生成した後、ソートした結果から
二分探索で文字列Sの辞書順で次の文字を探索します。