ABC301です！今回は文字列操作やカウントを駆使することでACにつながる問題が多い印象でした。
コンテンツ一覧
A問題
問題概略
この問題では、高橋くんと青木くんがN回の試合を行い、その結果が文字列Sで与えられます。この文字列Sにおける 'T' と 'A' の数をカウントし、多い方を勝者とします。ただし、同数の場合は先にその数に達した方が勝者とします。目的は、総合勝者が高橋くんか青木くんかを判定することです。
アプローチ
この問題は文字列の解析とカウントを主とした問題です。まず、文字列Sから 'T' と 'A' の数をカウントします。そして、その数が多い方を勝者とします。ただし、'T' と 'A' の数が同じ場合、先にその数に達した方が勝者となります。これを判定するためには、文字列Sを先頭から順に調べていき、'T' か 'A' が最初にその数を達成したかを見ることで判定できます。
プログラム
from collections import Counter
n = input()
S = input()
Awin = S.count('A') # 文字列S中の 'A' の数をカウント
Twin = S.count('T') # 文字列S中の 'T' の数をカウント
if Awin == Twin: # 'A' と 'T' の数が同じ場合
for s in S:
if s == "A":
Awin -= 1
if Awin == 0:
print("A") # 'A' の数が0になった時点で 'A' を出力し、プログラムを終了
exit()
else:
Twin -= 1
if Twin == 0:
print("T") # 'T' の数が0になった時点で 'T' を出力し、プログラムを終了
exit()
elif Awin > Twin:
print("A") # 'A' の数が 'T' より多い場合、 'A' を出力
else:
print("T") # それ以外の場合（'T' の数が 'A' より多い場合）、 'T' を出力
プログラムの解説
このプログラムでは、まず組み込み関数countを使用して、文字列S中の 'A' と 'T' の数をそれぞれカウントします。次に、それらの数が同じか、それともどちらかが多いかによって処理を分岐します。
'A' と 'T' の数が同じ場合、先にその数に達した方が勝者となるため、文字列Sを先頭から順に調べていきます。その際、'A' か 'T' の勝利数を引いていき、いずれかの数が0になった時点で、その文字を出力しプログラムを終了します。
一方、'A' と 'T' の数が同じでない場合、多い方が勝者となります。これは単純比較で、出力を分岐させます。
B問題
問題概略
与えられた数列に対して、隣接する2つの数の差の絶対値が1になるまで中間の数を追加する操作を行います。操作後の数列を出力する問題です。隣接する数の差が1より大きい場合、その間の数を追加することで差を1にします。数列の数は1つでも、多くても問題なく処理できます。
アプローチ
数列の各項を前から順に見ていき、その項と次の項の差が2以上なら、その差が1になるように間の数を挿入します。この操作を数列の最初から最後まで行います。出力には新たな数列を用います。これを R とします。
プログラム
N = int(input()) # 数列の長さを入力
A = list(map(int,input().split())) # 数列を入力
R = [] # 操作後の数列
for n in range(N-1):
if A[n] - A[n+1] < -1: # 項と次の項の差が-1より小さい場合
for i in range(A[n],A[n+1]):
R.append(i) # 間の数を挿入
elif A[n] - A[n+1] > 1: # 項と次の項の差が1より大きい場合
for i in reversed(range(A[n+1]+1,A[n]+1)):
R.append(i) # 間の数を挿入
else:
R.append(A[n]) # 項と次の項の差が1以下ならそのまま追加
R.append(A[-1]) # 最後の項を追加
print(*R) # 数列を出力
プログラムの解説
まず、数列の長さ N と数列 A を入力します。次に、操作後の新たな数列 R を作成します。
次に、数列 A の項を前から順に見ていきます。この時、項と次の項の差が-1より小さい場合、つまり項が次の項よりも小さいとき、項から次の項の一つ手前までの数を順に R に追加します。
\(\ \text{if} \ A[n] - A[n+1] < -1, \ \text{then append} \ A[n], A[n]+1, …, A[n+1]-1 \ \text{to} \ R \)
同様に、項と次の項の差が1より大きい場合、つまり項が次の項よりも大きいとき、項から次の項の一つ後までの数を逆順に R に追加します。
\(\ \text{if} \ A[n] - A[n+1] > 1, \ \text{then append} \ A[n], A[n]-1, …, A[n+1]+1 \ \text{to} \ R \)
項と次の項の差が1以下の場合、つまり項と次の項が同じか、項が次の項よりも1だけ大きい場合、項をそのまま R に追加します。
\(\ \text{if} \ A[n] - A[n+1] \leq 1, \ \text{then append} \ A[n] \ \text{to} \ R \)
その後、数列 A の最後の項を R に追加します。これで操作後の数列が完成します。
最後に、新たな数列 R を出力します。*R とすることで、数列を空白区切りの形式で出力します。
C問題
問題概要
この問題では、ゲームで使用する2つのカード列が与えられます。それぞれのカードには英小文字または '@' の文字が書かれており、 '@' のカードは 'a', 't', 'c', 'o', 'd', 'e', 'r' のいずれかのカードと置き換えることができます。ゲームの目的は、これらの2つの列を一致させることです。ただし、列内のカードは自由に並び替えることができます。
アプローチ
この問題は、各文字の出現数を比較して解くことができます。特に、'@' の文字と 'a', 't', 'c', 'o', 'd', 'e', 'r' の文字はお互いに置き換えることができますので、これらの文字の出現数の差を '@' の出現数で補うことが可能です。
数式で表すと、以下の条件が全ての英小文字に対して成立するならば、列を一致させることが可能です。
\(\ |AC[\text{{alp}}] - BC[\text{{alp}}]| \leq \text{{Aat}} + \text{{Bat}} \)
ただし、ACとBCはそれぞれ1つ目と2つ目の文字列における各英小文字の出現数を表し、AatとBatはそれぞれ1つ目と2つ目の文字列における'@'の出現数を表します。
プログラム
以下に、Pythonでの実装例を示します。このプログラムは、上述したアプローチを反映したものです。
from collections import Counter
import string
# 入力の受け取り
A = input()
B = input()
# '@'を置き換え可能な文字のリスト
atcoder = ['a','t','c','o','d','e','r']
# '@'の出現数を数える
Aat = A.count('@')
Bat = B.count('@')
# 各文字の出現数を数える
AC = Counter(A)
BC = Counter(B)
# 全ての英小文字についてループを回す
for alp in list(string.ascii_lowercase):
# '@'を置き換え可能な文字の場合
if alp in atcoder:
diff = AC[alp] - BC[alp]
# 1つ目の文字列に多い場合、'@'を使って補う
if diff > 0:
Bat -= diff
# 足りない場合は'No'を出力して終了
if Bat < 0:
print("No")
exit()
# 2つ目の文字列に多い場合、'@'を使って補う
elif diff < 0:
Aat += diff
# 足りない場合は'No'を出力して終了
if Aat < 0:
print("No")
exit()
# '@'を置き換え不可能な文字が一致していない場合は'No'を出力して終了
elif AC[alp] != BC[alp]:
print("No")
exit()
# 全ての文字が一致した場合は'Yes'を出力
print("Yes")プログラムの解説
このプログラムは、文字列を順に見ていき、'@'の文字と'a', 't', 'c', 'o', 'd', 'e', 'r' の文字の出現数の差を '@' の出現数で補うことが可能かどうかをチェックします。まず、'@'の出現数を計算し、次にCounterを使用して各文字の出現数を計算します。
その後、全ての英小文字に対してループを回します。'@'を置き換え可能な文字の場合、1つ目の文字列にその文字が多い場合は2つ目の文字列の'@'を使って補い、逆に2つ目の文字列にその文字が多い場合は1つ目の文字列の'@'を使って補います。これは、'@'を置き換えることで列を一致させるためです。
それぞれの場合、補おうとした'@'が足りない場合は列を一致させることが不可能なので、'No'を出力してプログラムを終了します。また、'@'を置き換え不可能な文字が一致していない場合も列を一致させることが不可能なので、'No'を出力してプログラムを終了します。
全ての文字が一致した場合は、列を一致させることが可能なので、'Yes'を出力します。
D問題
問題概略
今回の問題は、指定された文字列 S（0、1、?の三つの文字からなる）と整数 N を使って特定の操作を行う問題です。操作とは、「?」を「0」または「1」に置き換えて2進数として考え、その全ての組み合わせのうちN以下の最大値を求めるというものです。全ての組み合わせがNを超える場合は-1を出力します。
アプローチ
まず最初に、すべての「?」を「0」に置き換えた場合の値がNよりも大きいかを確認します。もしそれがNより大きければ、すべての組み合わせがNを超えるので、-1を出力してプログラムを終了します。
そうでない場合、文字列 S の先頭から順に「?」を探していきます。「?」が見つかったら、まずそれを「1」に置き換え、残りの「?」は全て「0」に置き換えて2進数としての値を計算します。その値がN以下ならば、「?」を「1」に置き換えます。Nを超えるなら、「?」を「0」に置き換えます。これを最後まで繰り返すことで、N以下の値を最大化することができます。
プログラム
# 入力を受け取る
S = input()
N = int(input())
# 「?」を全て「0」に置き換えた値がNを超えるか確認
if int(S.replace('?','0'),2) > N:
print(-1) # 超えるなら -1 を出力
exit() # プログラムを終了
def maximize_binary(S, N):
max_binary = ''
for i in range(len(S)):
if S[i] == '?':
# 「?」を「1」に置き換え、残りの「?」を全て「0」に置き換える
temp = max_binary + '1' + S[i+1:].replace('?', '0')
# 置き換えた値がN以下なら「1」に、Nを超えるなら「0」に
max_binary += '1' if int(temp, 2) <= N else '0'
else:
max_binary += S[i]
return max_binary
print(int(maximize_binary(S,N),2))
プログラムの解説
このプログラムでは、入力された文字列 S から「?」を見つけ出し、「1」に置き換えた場合にNを超えるかどうかを確認します。もしNを超える場合「?」は「0」に置き換え、Nを超えないようであれば「1」に置き換えるという操作を繰り返しています。この方法により、Nを超えない可能な限り大きな値を得ることができます。