Python3で解く AtCoder Beginner Contest 148 D - Brick Break

かなりシンプルな問題。砕いて残ったものが1, 2, 3...という風に並んでる状態を目指す。左から順番に砕くか判定していく。

目次

概要

問題
1. 個のレンガが並んでる。
1. そのレンガには整数が書かれている。
1. レンガを砕くことによって、残った個になる。
1. その時番目の個のレンガに書かれている整数がiであるようにしたい。
1. レンガを砕く最小の数は？

制約

• 
• 

---

解くときに考えた内容

• 1が書かれているレンガがなかったら "-1"

  • Pythonでは（他の言語でもだと思うけど）if a in listは遅い。
  • そのため、setで重複を削除してif 1 in set(list)のように存在を確認する。
  • この処理は以下の処理の前にやる必要はないが、全部壊しても無理だったら-1としてもいいが効率が悪い気がしたので。

• 最終的に1, 2, 3 ... となってて欲しいのでこの順番を管理する。 (orderとする。初期値は1)
• あとは並んでいるレンガがの番目がorderじゃなかったら、壊した数をインクリメントする。
• 並んでいるレンガがの番目がorderだったら、orderをインクリメントする。

---

コード

n = int(input())
a = [int(x) for x in input().split()]
a_s = set(a)
cnt = 0
order = 1
if not 1 in a_s:
    print(-1)
    exit()
else:
    for i in range(len(a)):
        if a[i] != order:
            cnt += 1
        if a[i] == order:
            order += 1
print(cnt)

---

書籍

最近ポチった書籍

• ゼロからつくるPython機械学習プログラミング入門

機械学習スタートアップシリーズ ゼロからつくるPython機械学習プログラミング入門 (KS情報科学専門書)

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク・強化学習・教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。これは別記事で紹介する予定である。

• 実用的でないPythonプログラミング

バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。

実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!

blacktanktop.hatenablog.com

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

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

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

drken1215.hatenablog.com

アルゴリズムの参考書籍

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

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

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