AGC022 A - Diverse Word
備忘録
問題
回答
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
の辞書順で次の文字を探索します。