ABC329の解説記事 (PyPy3 ABCD)

はじめに

問題はこちら
初心者（灰色〜茶色）向けです。

A - Spread

考え方

文字列を1文字ずつのリストとして受け取り、半角スペース区切りで表示すればよいです。
リストを「*」をつけて引数として渡すと、各要素が個別変数として渡されます。
このとき、各要素間の区切り文字はデフォルトで半角スペースです。

解答例

私の解答

print(*list(input()))

B - Next

考え方

重複を除き2番目に大きい自然数を表示する問題です。
重複を除く　→　Setを利用すればよさそう
と考えられるとシンプルに解けます。

1. 入力をSetとして受け取る
2. Setをリスト化し、昇順ソート
3. 二番目に大きい値を表示する

というイメージです。

解答例

私の解答

n = int(input())
print(sorted(list(set(map(int, input().split()))))[-2])

C - Count xxx

考え方

各英小文字が最大何文字連続しているかを保持し、合計すればよいです。
これは、文字の位置の取り方によらず、得られる部分文字列が同じであれば重複して計算しない、と指定があるからです。
実際、位置や取り方によらず同じ文字列であれば1つとして数えるので、ある文字Xの1種類の部分文字列は、
「X」、「XX」、「XXX」、、、ですから、最大の部分文字列の文字数を数えれば良いです。

また、公式解説などにもありますが、下記のように（値名、連続回数）の繰り返しの文字列に変換する圧縮方法をランレングス圧縮と言います。
「ssskkyskkkky」　→　「s3k2y1s1k4y1」
同じ値が連続して続く場合には効率の良い圧縮です。
私の解答は各英小文字の最大の文字列のみ記録しておき、合計するという方針をとっています。

解答例

私の解答

from collections import defaultdict
n = int(input())
s = input()
cnts = defaultdict(int)
now,cnt = s[0],0
for i in range(n) :
    if s[i] != now :
        cnts[now] = max(cnt, cnts[now])
        now,cnt = s[i],1
    else :
        cnt += 1
    if i == n-1 :
        cnts[now] = max(cnt, cnts[now])
print(sum(map(lambda x:cnts[x],cnts)))

D - Election Quick Report

考え方

各投票者の名前と投票数のtupleを優先度付きキューで管理し、最小値を毎度表示します。
各投票者の投票数の保持にはdictを用いました。

また、キューへの格納方法は(投票数×-1, 候補者の番号)としています。
それは、tupleは、第一成分の昇順、同一であれば、第二成分の昇順、、、、といった要領でソートされるからです。

加えて、同一の投票者の過去時点のデータを削除せずに最新のデータを追加しています。
これは、過去の時点のデータが選ばれることはないためです。
同一の投票者の過去時点のデータと最新データであれば、最新データが必ず先の番号にソートされる形になるためです。
計算量は$O(MlogM)$です。

解答例

私の解答

import heapq
from collections import defaultdict
n,m = map(int, input().split())
a_n = list(map(int, input().split()))
d = defaultdict(int)
ans = []
heapq.heapify(ans)
for i in range(m) :
    d[a_n[i]] += 1
    heapq.heappush(ans,(-d[a_n[i]],a_n[i]))
    score,a = heapq.heappop(ans)
    print(a)
    heapq.heappush(ans,(score,a))

参考文献

感想

今回もDが解けてよかったのですが、1ペナでした。（最初はSetで管理すれば間に合うと思ったのですが間に合いませんでした、、、）
Dまで解けたのに、レートが下がってしまい、まだまだ精進だなと思いました。

年内入緑目指して頑張ります。