解いた問題の振り返りを行うための自分用のメモです。

@sharu0321 から修正案をもらって修正しました（フォローしてあげてね）。

A問題 – Spread

入力された文字をイテラブルとしてアンパックする。Pythonのprint()関数は自動的にスペースを挿入するので、以下のコードで通る。

print(*input())

実際の提出

B問題 – Next

要素をset()に入れてから sorted() に通す。返り値はソートされたリストなので、そのまま最後から2番目の要素、すなわち2番目に大きいものを参照すれば答えとなる。

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

実際の提出

C問題 – Count xxx

オリジナルの文字列に連長圧縮（ランレングス圧縮）を適用する。ランレングス圧縮の実装はほかのウェブサイトの記事に任せるとして、itertools.groupby() とリスト内包表記を使った簡潔な実装を見つけたので紹介しておく。

それぞれ文字の種類と、それに対してSの最長の部分文字列としてどれだけ長いのかを格納する辞書を作る。具体的には、先ほど作ったリスト内の各ペアを調べ、その文字について繰り返し同じ文字が出現した回数が今までのその文字のそれより大きい場合にその回数を更新するようにして、最後にそれらを足し合わせれば、Sの部分文字列であって、1 種類の文字のみからなるものの数が求まる。

from collections import defaultdict
from itertools import groupby

N = int(input())
S = input()
compressed = [(k, len(list(g))) for k, g in groupby(S)]
charset = defaultdict(int)
for char, count in compressed:
    charset[char] = max(charset[char], count)
ans = 0
for v in charset.values():
    ans += v
print(ans)

提出コード

D問題 – Election Quick Report

方針としては、A を反復させながら投票結果を追っていく方針が最適だろう。

まず、カウント用の配列を用意して、配列の i 番目には A[i] 人に投票された人数を格納するようにする。そのカウントが増えるたびにその配列を全走査して、最大値が見つかったらそのインデックス番号を出力すれば、一応問題を解いたことにはなる。

しかし、このアルゴリズムでは N の要素数にしたがって、処理時間がN^2 のオーダーで増えていくため、制約の N = 200,000 には間に合わない。

N, _ = map(int, input().split())
A = [*map(int, input().split())]
a = [0 for _ in range(N)]
for v in A:
    a[v - 1] += 1
    mx = 0
    mxidx = 0
    for seq, i in enumerate(a, 1):
        if i > mx:
            mx = i
            mxidx = seq
    print(mxidx)

そこで、優先度付きキューを、今回の問題の解答に利用できる。Pythonには heapq という備え付けのモジュールがあり、要素内の最小値を時間計算量 O(log N) で参照できる。今回はこれを用いた実装を試みる。

そこでまず、カウント用の配列はそのままに、優先度付きキュー heap[] を用意し、配列 A に対してループを回す。それぞれ優先度として、人 v に投票された人数をa[v - 1]（-1 しているのは 1-indexed だから） 、現在 for 文で回している値 v を比較値として2つをタプルとしてヒープに挿入する。なお、Python の優先度付きキューは最小ヒープで実装されているため、今回の問題では取り出されるべき最小値が現在最も得票数の多い候補者とならなければいけない。したがって、ヒープに挿入する優先度には、マイナスが付与される必要がある。

また、タプルとして挿入している理由は、最も得票数が多かった候補者が複数いる場合、最も番号の小さい候補者がまず最初に出力されるように、キューの優先度が重複した場合に最小値をどのような順序で取り出すべきかという優先度をつけるためである。

以上を踏まえたうえで、ヒープからルートの値 heap[0] を取得すると、現時点でもっとも得票数が多く、かつ最も番号の若い候補者 mxidx を出力していくことができる。あとはこの操作を N 回繰り返せば OK。

import heapq

N, _ = map(int, input().split())
A = [*map(int, input().split())]
a = [0 for _ in range(N)]
heap = []

for v in A:
    a[v - 1] += 1
    heapq.heappush(heap, (-a[v - 1], v))
    _, mxidx = heap[0]
    print(mxidx)

提出コード

感想

今回、C問題を通すことができなかった一方で、興味本位で解いてみた D 問題を解くことができた。解けた時は狂喜してパフォーマンスが上がるのではないかと予期したが、後で難易度を AtCoder Problems で確認したところ C 問題および D 問題共に灰 Diff だったし、パフォーマンスも 405 と悲しき結果に終わった。悔しいけれども、着実にアルゴリズムを身につけるということが大事ということを念じて、今後もゆっくり楽しんでいきたいと思う。Happy coding!