AGC048 A - atcoder < S

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# 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
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = [-1 for _ in range(N)]

    def root(self, N):
        if self.tree[N] < 0:
            return N
        self.tree[N] = self.root(self.tree[N])
        return self.tree[N]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.tree[x] > self.tree[y]:
            x, y = y, x
        self.tree[x] += self.tree[y]
        self.tree[y] = x

    def size(self, x):
        return -self.tree[self.root(x)]


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

    N = ii()
    target_str = 'atcoder'
    for _ in range(N):
        S = iss()
        if S > target_str:
            # 初期状態から条件を満たしている場合
            print(0)
            continue

        tmp = list(set(S))
        if tmp[0] == 'a' and len(tmp) == 1:
            # どのように移動しても条件を満たすことが出来ない場合
            print(-1)
            continue

        for i in range(len(S)):
            if S[i] == 'a':
                continue
            if S[i] > 't':
                print(i-1)
            else:
                print(i)
            break


if __name__ == '__main__':
    main()

考え方

文字列を操作して、条件の文字列より辞書順で降順となるようにします。
どのような状態の時に条件を満たすかを考える必要があります。

  • 回答概要
    • aしか存在しない文字列は必ず条件を満たすことが出来ない
    • 移動させる文字は一文字のみで良い

どのような文字列は条件を満たすことが出来ないか考えます。
次に文字列の文字をどのように移動させると、条件を満たすことができるのかを考えます。

まず、aのみで構成された文字列は必ず条件を満たすことが出来ません。
これはどのように文字を移動させても、辞書順が変わらないためです。

次にどのような文字列が条件を満たすかを考えます。
a以外の文字が存在するとき、
その文字がtより大きい場合には先頭から2文字目に存在する必要があります。
また、その文字がtより小さい場合には先頭に存在する必要があります。

文字列のどこかに存在するa以外の文字を先頭あるいは2文字目に移動させるとき、
移動回数を最短にするためには、先頭に近い文字の方が効率的です。
つまり、先頭からa以外の文字を探索し、
先頭あるいは2文字目のどちらに配置するかを判定することで回答を得ることが出来ます。