クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-2 Best Cow Line（POJ 3617）」(p.45)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 Best Cow Line（POJ 3617）」(p.45)
のコードをPythonで書き直したものとなっています。

入力

N\\S

入力例



6
ACDBCB


解答

蟻本ではputcharで一文字ずつ出力していますが、Pythonで出力するための標準関数であるprintは出力の際に自動的に改行が挟まれてしまいます。

そのため、下のコードでは文字列Tに文字を追加していき、最後に文字列Tを出力しています。

# 入力
N = int(input())
S = input()

# S[a], S[a+1], ..., S[b]が残っている文字列
a = 0
b = N - 1

T = ''    # 文字列T

while a <= b:
    # 左からみた場合と右から見た場合を比較
    left = False
    for i in range(b - a + 1):    # 0 <= i <= b - a
        if S[a + i] < S[b - i]:
            left = True
            break
        elif S[a + i] > S[b - i]:
            left = False
            break
    # 文字列Tに文字を追加する
    if left:
        T += S[a]
        a += 1
    else:
        T += S[b]
        b -= 1

print(T)