Python3で解く HHKB プログラミングコンテスト 2020 C - Neq Min

順番に与えられる、 $p$ を集合で管理して、その中に前回出力した値が含まれるかどうかを判定してあげるっていうこと。

概要

問題

長さ $n$ の数列 $p_1, p_2, ... , p_{n-1}, p_n$ が与えられる。
各 $i (1, 2, ..., n)$ について、 0以上の整数で $p_1, p_2, ... , p_i$ のいずれとも等しくない値のうち最小値は？

解くときに考えた内容

出力したい値をsetとリストで管理する（TLE）

出力する値は0~nまでの値なので、 $p_i$ と一致しないように、 $p_i$ の「値を削除」してその時の一番小さい左側の値を出力する。

$0, 1, 2, ..., n$ という集合(n_set)とリスト(n_list)を作る。
n_setに $p_i$ があったら、n_setとn_listから $p_i$ を取り除く。
n_listのindexが0を出力する。

ただこれでは、すべての $i$ をforで処理することで $O(n)$ でその中で「値を削除」する処理が $O(n)$ （さらにそれを２回）なので $O(n^2)$ になってしまう

既出のpをsetか配列かで管理する

出力予定の値(ans)ではなく、 $i$ 番目ごとの $p_i$ までの値を集合(p_set)で管理して、p_setにansが「含まれない状態になる」までansをインクリメントする。

出力用の変数(ans)を0とする
forで $p_i$ を回すたびに集合(p_set)に加える。
p_setにansがなくなるまで、ansをインクリメントする。
ansを出力する。

ちなみにリストで管理する方法もある。コードは載せておく。（集合の方がわかりやすいとは思う。）

全体的なイメージだと $p_i$ を回すたびにp_setに加えられて、ansのインクリメントは多くても $n$ 回しか行われないっていうところに気付けるかがポイント。

# ansがどんどこ伸びていく感じ
# だけど、一度増えたらそこからまた増やすから
# インクリメントは最大でもn回
0 ... ... ... ... ... .. n
--->->--->----------->->

しゃくとりっぽい感じ。このように平均的にクエリの計算量が $O(1)$ になるようなもの（もしくは計算量が平均的にならされるものってことだと思うんだけど）をならし計算量というそうだ。

詳細は、けんちょんさんのブログを見るといい。

drken1215.hatenablog.com

コード

答えをリストで管理する場合（TLE）

n = int(input())
P = [int(x) for x in input().split()]
n_list = list(range(n))
n_set = set(n_list)
for p in P:
    if p in n_set:
        # この処理はO(n)
        n_set.remove(p)
        n_list.remove(p)
    print(n_list[0])

pをsetで管理する場合（AC）

n = int(input())
P = [int(x) for x in input().split()]
p_set = set()
ans = 0
for p in P:
    p_set.add(p)
    # ansが含まれなくなるまで+1する
    while ans in p_set:
        ans += 1
    print(ans)

pをリストで管理する場合（AC）

n = int(input())
P = [int(x) for x in input().split()]
u = [False for _ in range(200001)]
ans = 0
for p in P:
    u[p] = True
    while u[ans]:
        ans += 1
    print(ans)

書籍

アルゴリズムの参考書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい）ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆
発売日: 2015/01/30
メディア: Kindle版

くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、