2022年7月17日開催のABC260 解説＆反省会。Cまでは簡単、D問題でかなり悩まされました。
バックナンバーはこちらから！
コンテンツ一覧
A - A Unique Letter
問題
長さ \(\ 3 \) の文字列\(\ S \) が与えられます。
\(\ S \) に\(\ 1 \) 度だけ含まれる文字を\(\ 1 \) つ出力してください。
但し、そのような文字が存在しない場合は代わりに -1 と出力してください。
制約と入力形式
- \(\ S \) は英小文字のみからなる\(\ 3 \) 文字の文字列
回答アプローチ
愚直な場合分けで解きました。リストをsetで重複を排除して、長さが\(\ 1 \) か\(\ 2 \) か\(\ 3 \) かで場合分けを行います。
S_2 = list(set(S))
if len(S_2) == 1:
print(-1)
elif len(S_2) == 3:
print(S[0])
else:
if S.count(S_2[0]) == 1:
print(S_2[0])
else:
print(S_2[1])B - Better Students Are Needed!
問題
入学試験の受験者が\(\ N \) 人います。
試験の結果、\(\ i \) 番の受験生は数学で\(\ A_i \) 点、英語で\(\ B_i \) 点を取りました。
試験の合格者は次のように決められます。
- 数学の点が高い方から\(\ X \) 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方から\(\ Y \) 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方から\(\ Z \) 人を合格とする。
- ここまでで合格となっていない受験者は、不合格とする。
ただし、 1. から 3. までのどの段階についても、同点であった場合は受験生の番号の小さい方を優先します。入出力例も参照してください。
以上の手順で合格者を決める時、合格となった受験生の番号を小さい方から順に改行区切りで出力してください。
制約と入力形式
- 入力は全て整数
- \(\ 1 \leq N \leq 1000 \)
- \(\ 0 \leq X,Y,Z \leq N \)
- \(\ 1 \leq X + Y +Z \leq N \)
- \(\ 0 \leq A_i,B_i \leq 100 \)
回答アプローチ
Pythonのソート機能でうまく解ける問題です。
各受験者を
[ 数学の点数, 英語の点数, 合計点, 合格フラグ, 受験番号]
の\(\ 5 \)要素のリストで管理します。単純に数学、英語、合計点の順にソートできればいいのですが、途中途中で合格者が出てしまい、それらをソートから排除するのを考える必要があります。
Pythonのリストにはsortメソッドからあり、特に指定しないと先頭の要素にて昇順にソートされます。sortメソッドにはkeyという引数に関数を指定でき、その関数の出力をもとに昇順でソートできます。lambda関数で、自作の処理を入れれば、好きなアルゴリズムでソート可能です。
>>> a= ["apple","app","pple"]
>>> a.sort(key=len) #文字列の長さでソートします。
>>> print(a)
['app', 'pple', 'apple']昇順でソートされるため、点数を高い順にソートしたい場合は、点数のマイナスでソートすれば良いです。この時、合格者に対しては異常に高い点数を設定し、ソートの後ろに行くようにして排除します。合格フラグは\(\ 0 \) で初期化をして、合格した場合は英数の満点\(\ +1 \) 点の\(\ 201\) 点を代入し、点数のマイナスしてソートします。（合格してない場合は必ず\(\ 0 \) 以下の値になり、合格者は\(\ 1 \) 以上の値になります。）
また、同じ点数の場合などは、受験番号が若い順に有利となるため、このソートも随時行います。
N,X,Y,Z = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = [[A[i],B[i],A[i]+B[i],0,i+1] \
for i in range(N)]
def sort_list(L,i,X): #ソートをする関数
L.sort(key=lambda x:x[3]-x[i]) # 合格フラグ - 点数 合格者は1に近い値となります。
for j in range(X):L[j][3] = 201 # 合格者は合格フラグを201に設定
L.sort(key=lambda x:x[-1]) # 受験番号でソート
for i,x in enumerate([X,Y,Z]):
sort_list(L,i,x)
for l in L:
if l[3]:print(l[-1])C - Changing Jewels
問題
高橋君はレベル\(\ N \) の赤い宝石を\(\ 1 \) 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。
- レベル\(\ n \) の赤い宝石 (\(\ n \) は\(\ 2 \) 以上) を「レベル\(\ n-1 \) の赤い宝石\(\ 1 \) 個と、レベル\(\ n \) の青い宝石\(\ X \) 個」に変換する。
- レベル\(\ n \) の青い宝石 (\(\ n \) は\(\ 2 \) 以上) を「レベル\(\ n-1 \) の赤い宝石\(\ 1 \) 個と、レベル\(\ n-1 \) の青い宝石\(\ Y \) 個」に変換する。
高橋君はレベル\(\ 1 \) の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル\(\ 1 \) の青い宝石を最大何個入手できますか？
制約と入力形式
- \(\ 1 \leq N \leq 10 \)
- \(\ 1 \leq X \leq 5 \)
- \(\ 1 \leq Y \leq 5 \)
- 入力される値はすべて整数
回答アプローチ
割と単純な漸化式で解けます。
$$ B_n = R_{n-1} + Y \times B_{n-1} (2 \leq n \leq N) \tag{1}$$
$$ R_n = R_{n-1} + X \times B_{n} (2 \leq n \leq N) \tag{2}$$
ただし、\(\ R_n \) は、\(\ B_n \) に依存するため、\(\ B_n \) から処理する必要があります。
N,X,Y = map(int,input().split())
if N>1:
B,R = [0]*N,[0]*N
B[1],R[1] = Y,X*Y
for i in range(2,N):
B[i] = R[i-1] + Y*B[i-1]
R[i] = R[i-1] + X*B[i]
print(R[-1])
else:
print(0)D - Draw Your Cards
問題
1 から\(\ N \) が書かれた\(\ N \) 枚のカードが裏向きで積まれた山札があり、上から\(\ i \) 枚目のカードには整数\(\ P_i \) が書かれています。
この山札を使って、以下の行動を\(\ N \) ターン繰り返します。
- 山札の一番上のカードを引いて、そこに書かれた整数を\(\ X \) とする。
- 場に見えている表向きのカードであって書かれた整数が\(\ X \) 以上であるもののうち、書かれた整数が最小のものの上に、引いたカードを表向きで重ねる。もし場にそのようなカードがなければ、引いたカードをどれにも重ねずに表向きで場に置く。
- その後、表向きのカードが\(\ K \) 枚重ねられた山が場にあればその山のカードを全て食べる。食べられたカードは全て場から消滅する。
各カードについて、何ターン目に食べられるか、あるいは最後まで食べられないかを求めてください。
制約と入力形式
- 入力は全て整数
- \(\ 1 \leq K \leq N \leq 2 \times 10^5 \)
- \(\ P \) は \(\ (1,2,\ldots,N) \) の順列（ \(\ (1,2,\ldots,N) \)を並べ替えて得られる列）である
回答アプローチ
コンテストの時間内に解けませんでしたが、コンテスト後も色々と考えさせられた問題です。最初は「場」を管理するのが大変そうなので、「場」を使わないやり方を考えました。（なおTLE）
各カードを
[カードに書かれた番号, 代表カード, 食べられるターン]
の3つの要素を持つリストとします。代表カードとは、場に重ねた時にそのカードの一番下にあるカードのことを指します。「代表カード」と「食べられるターン」は「\(\ -1 \)」として初期化します。
その後、カードを山札の順に並べて、山札の一番上のカードから順番に見ていきます。このとき、そのカードの「代表カード」が 「\(\ -1 \)」のとき、代表カードをそのカード自身のインデックスとします。つまり、このカードが場に出たときに一番底にくるカード、代表カードとなります。その後、代表カードの後続のカードから、この代表カードに重ねられるカードを\(\ K \) 枚探します。重ねられるカードは代表カードを基準として、\(\ K \)枚に渡って降順となるカードかつ、今まで他の代表カードに所属していないカード群です。\(\ K \)枚に渡って降順になるカードは代表カード所属（リストの代表カードも更新されます）となり、食べられることが確定します。食べられるターンは、代表カードにのみ刻めば十分です。
場を使わないので、個人的にはスマートなやり方に感じましたが、最悪 \(\ O(N^{1.5}) \) となり、今回のテストケースでは最後の一個だけTLEとなってしまいました。
N,K = map(int,input().split())
P = [[p,-1,-1] for p in list(map(int,input().split()))] #値、一番下のカード、終了ターン
T = 1
for i in range(N):
if P[i][1] > -1:
continue
C = K-1
P[i][1] = i
bottom = P[i][0]
base = bottom
for j in range(i,N):
if P[j][0] < base and P[j][1] == -1:
P[j][1] = i
base = P[j][0]
C -= 1
if C == 0:
P[i][2] = j+1
break
sortedP = sorted(P)
for sp in sortedP:print(P[sp[1]][-1])代表カードという考え方だけ引き継ぎ、 \(\ O(N\log N) \) となるように考え直します。
場という概念をリストでプログラム上にも実装して、終了ターンや重ねられている枚数を代表カードをキーに管理します。
山札からカードを引いて場のカードに重ねる際は、場は確実に昇順になることが保証されているため、重ねる対象のカードを場から二分探索で探します。（場のカードのうち自身より大きいものの中から最小のものに重ねて、場にあるどのカードよりも大きい場合は末尾に追加されるためソートせずともリストは昇順になります）カードを重ねる際に、重ねる対象のカードから代表カードの情報を引き継ぎます。これにより、重ねられている枚数と終了ターンを管理します。代表カードをキーに、重ねられているカード数を参照し、規定の枚数ならば、代表カードの終了ターンを更新して、場から対象のカードも削除します。
import bisect
N,K=map(int,input().split())
P=list(map(int,input().split()))
field = []
bottom = [0]*N #自分が所属する代表カードの情報を記憶
num_card = [0]*N #重ねられた山の枚数。代表カードのみ記憶
end_turn = [-1]*N #終了ターンを記録。代表カードのみ記憶
for i in range(N):
p = P[i]
if not field:
if K == 1: # K = 1の時は、枚数と場の管理は不要
end_turn[p-1] = i+1
bottom[p-1] = p
continue
else:
field.append(p)
num_card[p-1] += 1
bottom[p-1] = p
else:
t = bisect.bisect_left(field,p) #重ねる対象のインデックス
if t == len(field): #場のどのカードよりも数字が大きい時
field.append(p)
num_card[p-1] += 1
bottom[p-1] = p
else:
bottom[p-1] = bottom[field[t]-1] #代表カード情報を引き継ぐ
if num_card[bottom[p-1]-1] >= K-1: #重ねる枚数がK枚に達する。代表カードをキーに枚数を覚える
end_turn[bottom[p-1]-1] = i+1 #食べられるターン。代表カードだけに記憶すれば十分
field.pop(t) #重ねる対象を削除する
else: #重ねる枚数がK枚に達しない場合
num_card[bottom[p-1]-1]+=1
field[t] = p #重ねる対象を更新
for i in range(N):print(end_turn[bottom[i]-1]) #各カード、自分が所属する代表カードの終了ターンを参照