ABC301 A問題~B問題 解説

ABC301 の A問題~B問題 までの 解説を行います。

A問題

問題URL

\( S\)に含まれる“T”の文字数を\( T\), “A”の文字数を\( A\)とします。
\( T\gt A\)の場合は、“T”, \( T \lt A\)の場合は“A”と出力します。
\( T = A\)の場合、以下のアルゴリズムを利用して答えを求めることが可能です。

  1. \( t = 0, a = 0\)と定義します。ここには高橋くん、青木くんの勝利数を記録します。
  2. \( S\)の各文字を、\( S[i] (1 \lt i \lt N)\)とします。
  3. 各 \( i\)に対して、\( S[i]\)が”T”の時、\( t\)に1を加算し、\( S[i]\)が”A”の時、\( a\)に1を加算します。
  4. \( t = \frac{N}{2}\)となったとき“T”と出力し、
  5. \( a = \frac{N}{2}\)となったとき“A”と出力します。

(文字列を出力した後に、プログラムを終了させるようにする必要があります)

以上により、この問題を解くことが可能です。以下はPythonでのソースコード例となります。

N = int(input())
S = input()
T = S.count("T")
A = S.count("A")
if T > A:
  print("T")
if T < A:
  print("A")
else:
  win = N // 2
  t = 0
  a = 0
  for _ in range(N):
    if S[_] == "T":
      t += 1
      if t == win:
        print("T")
        break
    else:
      a += 1
      if a == win:
        print("A")
        break

B問題

問題URL

\( N\), \(max(A_i)\) が それぞれ100以下であるため、仮に最悪のケース(1, 100, 1, 100, 1, 100, …)を考えた場合でも、追加する整数の数は高々10000個程度であると考えられます。
よって、問題文通りの処理を愚直に行えば良いです。これは、Whileループなどを利用して処理をすることが出来ます。

Pythonでは、スライスというものを利用することにより、数列を区切ることが出来ます。それを活用するとよいでしょう。

N = int(input())
A = list(map(int,input().split()))
i = 0
while True:

  if i == len(A)-1:
      break
  if A[i+1] - A[i] == 1:
    i += 1
    if i == len(A)-1:
      break
  if A[i] < A[i+1]:
    X = A[0:i+1]
    Y = A[i+1:len(A)]
    Z = []
    for z in range(A[i]+1, A[i+1]):
      Z.append(z)
    A = X + Z + Y
    i += 1
  elif A[i] > A[i+1]:
    X = A[0:i+1]
    Y = A[i+1:len(A)]
    Z = []
    for z in range(A[i+1]+1, A[i]):
      Z.append(z)
    A = X + Z[::-1] + Y
    i += 1
print(*A)
タイトルとURLをコピーしました