2020-09-10

Python3で解く AtCoder Beginner Contest 149 D - Prediction and Restriction

じゃんけんにおいて、事前に相手が出す手がわかっていて、何を出して勝ったかで得点が異なる時に、何回かじゃんけんして特典の最大値を求める問題（ほぼ概要だな）。

概要

問題

$n$ 回じゃんけんを行う。
プレイヤーがじゃんけんで勝った場合、プレイヤーは出した手に応じて以下のスコアを得る (あいこや負けは 0点)。
- グーで勝った場合 $r$ 点
- チョキで勝った場合 $s$ 点
- パーで勝った場合 $p$ 点
$k$ 回前のじゃんけんで出した手と同じ手を出すことはできない。
プレイヤーは能力者で相手が何を出すかが予知できる。
文字列 $t$ の左から $i$ 文字目に相手の手が書かれている。
例えば $rsp$ なら、グー・チョキ・パーの順でと出すと予知したという事。
この時、得られる最大値は？

解くときに考えた内容

回目までとそれ以降で考える。
- $k$ 回目までは、何も考えず勝てばいい。
- $k$ 回目より後だと、例えば、 $t = rsrpp$ の時に、最初の $rs$ はよくて、３回目の $r$ はとにかく勝てない。でもここで $s\ p$ をのどちらかを選べるが５回目の $p$ の時に勝つためには３回目の時に $p$ を出しておく必要がある。
- ということは、勝てない時は負けてもあいこでも得点が変わらないので、「遊びがある」状態なので、 $t_i$ と $t_{i-2}$ が同じ時は勝てないと考えるでよい。
あとは $t_i$ と $t_{i-2}$ が異なる時の $r,\ s,\ p$ を数えてそれぞれの得点を掛け合わせた時が最大値となる。

コード

from collections import Counter

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(input())
l = list()
ans = 0
for i in range(k):
    l.append(t[i])
for i in range(k, n):
    if l[i-k] == t[i]:
        # 勝てない状態
        l.append(None)
    else:
        # 勝てる手を必ず選べる
        l.append(t[i])
res = Counter(l)
ans = res['r'] * p + res['s'] * r + res['p'] * s
print(ans)

書籍

アルゴリズムの参考書籍

まだ、発売されていないが内容に期待している一冊。

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

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

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

drken1215.hatenablog.com

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

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

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

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

Python3で解く AtCoder Beginner Contest 149 C - Next Prime

AtCoder 競プロ ABC-C 素数エラトステネスの篩二分探索

自分自身以上の素数を求める問題。テストサンプルに制約の中で最大の素数のヒントがあるので、そこまでのテーブルがあればいい。あとは二分探索で探す。bisect_left, bisect_rightどちらでもできるが、たまに混乱するので、どういう風に考えて使うか軽くまとめた。

概要

問題
1. $x$ 以上の素数のうち、最小のものは？

制約

$2 \leqq x \leqq 10^5$

解くときに考えた内容

$x$ よりも一つ大きい素数を求める方法はよくわからん。
その場合、どうやるか。
制約の範囲内 + 範囲外の最小の素数のテーブルを持つ
素数テーブルの求め方
エラトステネスの篩
1. 2から $x$ （今回は100003）までの探索リストを作成する。
  (テストサンプルに100000を超える最小の素数の答えがある。)
2. 探索する先頭の数を素数リストに移動する。
3. その定数倍の値を探索リストからふるい落す。
4. 振い落としの素数リストへの移動と探索リストのふるい落としのステップを素数リストに移動する値がxの平方根まで行う。
5. 探索リストに残った数を素数リストに移動する。
6. 出来上がったのが素数テーブル
その後に、 $x$ をテーブル内で二分探索する。

二分探索
1. bisect_left(P, x)とすれば $P_i \lt x$ になるような個数が返ってくる。その個数とは求めたいindexであるので $P[bisect\_left(P, x)]$ が求めるもの。

参考

P = [2, 3, 5, 7, 11, 13, 17 ,19 ,23]
x = 19
bisect_left(P, 19) というのはリスト内の19未満の要素の個数 = 7
これは19以上で最も小さい素数のindexでもある。
bisect_right(P, 19)というのはリスト内の19以下の要素の個数=8
なので、今回bisect_rightを使う場合は、素数であるかどうかで分けてからならそれでもいい。

コード

bisect_left

from bisect import bisect_left

def eratosthenes(n):
    A = [i for i in range(2, n+1)]
    P = []
    i = 2
    while i**2 <= n:
        prime = min(A)
        P.append(prime)
        j = 0
        while j < len(A):
            if A[j] % prime == 0:
                A.pop(j)
                continue
            j += 1
        i += 1    
    for a in A:
        P.append(a)
    return P
    
x = int(input())
prime_table = eratosthenes(100003)
idx = bisect_left(prime_table, x)
ans = prime_table[idx]
print(ans)

bisect_right

from bisect import bisect_right

def eratosthenes(n):
    A = [i for i in range(2, n+1)]
    P = []
    i = 2
    while i**2 <= n:
        prime = min(A)
        P.append(prime)
        j = 0
        while j < len(A):
            if A[j] % prime == 0:
                A.pop(j)
                continue
            j += 1
        i += 1    
    for a in A:
        P.append(a)
    return P
    
x = int(input())
prime_table = eratosthenes(100003)
prime_set = set(prime_table)
if x in prime_set:
    print(x)
else:
    idx = bisect_right(prime_table, x)
    ans = prime_table[idx]
    print(ans)

書籍

アルゴリズムの参考書籍

まだ、発売されていないが内容に期待している一冊。

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

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

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

drken1215.hatenablog.com

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

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

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

【書評】機械学習スタートアップシリーズゼロからつくるPython機械学習プログラミング入門

書籍紹介機械学習

八谷さんのゼロからつくるPython機械学習プログラミング入門を読んだので感想。

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

作者:八谷大岳
講談社

Amazon

Jupyter notebookでインタラクティブにやりたかったのでフォークしてnotebook形式で作成したものをGitHubにあげた。

github.com

cloneしてもらってjupyter notebookを立ち上げれば、参考コードがかかれているので、データセットを変更したり、パラメーター変えたりを自由にできます。基本的にAnaconda環境で、Python3.6以上ならそのまま叩けば動くはず。できたら、そのうちColabでも実行できるようにする予定。

感想
本書の概要
どんな人向け？
終わりに
そのほか関連書籍
お願い（欲しい書籍リスト）

感想

全体的に非常に丁寧に書かれていて、わかりやすかった。機械学習に入る前に、線形代数・確率・統計の基礎を一通りおさらいしてから始まる。数式も多いが、図も多くイメージを掴みやすい印象だった。その後に回帰・分類・カーネルモデル・ニューラルネット・強化学習・教師なし学習という流れだった。サポートベクトルマシーンとカーネルモデルの説明は図も多く実際のコードからも理解がしやすい。いろんな本を読んできたが、ソフトマージン最大化や線形モデルからカーネルモデルへの拡張の説明は一番しっくりきた。あとは教師なしのPCAの主成分の最適化問題の説明もかなりわかりやすかった。全体的にバランスの良い構成になっていると感じた。
ちょっと残念だったのは、.py形式のサンプルしかなかったのでインタラクティブにできなかったこと。とりあえず4章以降は自分でJupyter対応した。

本書の概要

第1章機械学習とは何か

これまでの機械学習の歴史であるとか、昨今使われている理由などの説明。

第2章 Python入門

Pythonを使ったことない人向けに、Anacondaの環境設定からプロット、for文、if文の説明。あとは強化学習がはいっているのでOpenAIの簡単な説明がある。結構丁寧にかかれているので、本当にゼロからの人でもできると思う。

第3章数学のおさらい

ここは、避けては通れないところで、線形代数・最適化・確率・統計について復習。最適化とか確率については図が豊富で理解を促してくれる。初学者はもちろん、復習に役立つイメージだった。ここはnotebookにしなかったけど、4章以降のnotebookを見れば対応できると思う。

第4章回帰分析

基本的な線形回帰とロジスティック回帰について書かれている。一般化線形モデルの説明は行列の計算の図をたくさん使って説明してくれているので初学者が理論を知るにはいい内容だと思った。

第5章分類

サポートベクトルマシーンの説明がめちゃわかりやすくて、こういう風に説明すればすっと入ってくるんだなっていう感じがした。決定木の結果を文字で分けて出力していたのは、ちょっと面白かった。

第6章カーネルモデル

カーネルモデルの説明と線形モデルからの拡張のところは、式も図も多くて理解しやすい内容だった。初めから図6.2や図6.3のようなわかりやすいイメージと式を同時に見ていると理解しやすかったんだろうなと思った。なので少し機械学習に慣れてきた頃に見直すと非常に理解が進むと思う。

f:id:black_tank_top:20200901212920p:plain — 多項式カーネル SVMの例

第7章ニューラルネットワーク

一般的な、話が主でMNISTを題材にしている。ただこれもまた図がかなり丁寧に書かれているので他の書籍で畳み込みのイメージがよくわからないとか、計算過程がよくわからないとかそんな人向けの章と思う。

第8章強化学習

CartPoleではなくMountainCarが題材、何気に初めてやったかも。毎回成功させるのは難しいけど、まぁ一応書籍通り学習すればこんな感じになる。

f:id:black_tank_top:20200901164750g:plain — MountainCarを学習した結果

可視化されるとやっぱり嬉しいね。ここで強化学習に興味を持ったらそのほか関連書籍の強化学習本をみるといい。

第9章教師なし学習

個人的には、教師なし学習の項目が結構参考になった。主成分分析だけでなく因子分析についても図が豊富で理解を促してくれた。因子分析のところはレーダーチャートで結果が出るようになっててかなりわかりやすかった。クラスター分析も初めて教師なしを学ぶ初学者には説明が豊富でコードもわかりやすいので良いと思う。

f:id:black_tank_top:20200901212858p:plain — PCAの3Dプロットの例

どんな人向け？

まだ機械学習にほとんど触れたことない人で、比較的コードや数式に慣れている人に合っていると思う。数式の展開は丁寧なので追いやすいが、数式苦手な人はコードがGitHubにあるので、どのように実装されているか判断するのも良いと思う。

また、全体的に総復習をかけたい人にも一通り読むと良いと思う。個人的には以下の復習になった。

ラグランジュの双対問題
ID3とCARTの違い
正定値関数
スペクトル分解による因子負荷量の推定

終わりに

全体的に、ひろーく全般的に取り扱っている印象。図と数式が豊富で、初学者でもコードを理解できればアルゴリズムの理解の手助けになる良い一冊という感じ。自分的には復習になってすごくよかった。実際にコード叩きながら楽しめた。

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

作者:八谷大岳
講談社

Amazon

そのほか関連書籍

機械学習の文脈で初学者向けなのは、どちらから読んでも良いと思う。こちらの方が比較的範囲は狭いので簡単めの印象。中井さんの本なので非常にわかりやすい。

ITエンジニアのための機械学習理論入門

作者:中井悦司
技術評論社

Amazon

こちらは同じ、機械学習スタートアップシリーズのベイズ推論による機械学習入門。少し難しめだが、こちらも一読することをオススメする。

機械学習スタートアップシリーズ　ベイズ推論による機械学習入門

作者:須山敦志
講談社

Amazon

記事中にも出したけど、強化学習をもう１段階理解したい場合はこちらがオススメ

ITエンジニアのための強化学習理論入門

作者:中井悦司
技術評論社

Amazon

blacktanktop.hatenablog.com

ちょっとずれるけど、統計モデリングにも挑戦したい方はこちらがオススメ

実践Ｄａｔａ　Ｓｃｉｅｎｃｅシリーズ　ＲとＳｔａｎではじめる　ベイズ統計モデリングによるデータ分析入門 (ＫＳ情報科学専門書)

作者:馬場真哉
講談社

Amazon

blacktanktop.hatenablog.com

お願い（欲しい書籍リスト）

ずうずうしいのですが、ブログを続けるのも大変で、基本自分の学習メモのためですが、サポーター募集です。ポチッとしてくれると嬉しいです。

https://www.amazon.jp/hz/wishlist/ls/2EDNNTYRW2BJE?ref_=wl_share

もしくは、レビューなど書くので、献本していただけたらものすごく喜びます（お問い合わせ or TwitterのDMからお問い合わせ下さい。）

2020-08-30

Python3で解く AtCoder Beginner Contest 177 D - Friends

AtCoder 競プロ ABC-D BFS(幅優先探索) Union-Find

グラフの連結

概要

問題
1. $n$ 人いる。
1. $m$ 個の友人関係情報が与えられる。
1. 直接友人でなくても、友人の友人は友人であるとする。
1. この時に、友人同士を含まないようにするグルーピングを考える。
1. 最小のグループ数は？

解くときに考えた内容

BFS

強い人はUnion-Findとすぐわかる。
直感的には最大グループ人数が求める答え。
- $x$ 人のグループが最大とすると、x人をそれぞれ違うグループにする事が課題になる。それ以下の人数のグループは、それに応じて分ければいいだけなので。
今回はBFSで、各頂点から最短で繋がっている部分の距離をはかる。（正確には一人分を1として距離+1（自分自身だけでも1としたいから））
1人のグループなら1となって、2人なら1+1で2となるように実装する。
これは単純にBFSで、 (事前に隣接行列は作る。)
- 各頂点ごとに調べます。
- 頂点に行った事があるかないかを記録する。
- 行った事がある頂点だったら、次の頂点へ。
- 行った事がない頂点だったら、キューに加えて、キューがなくなるまで、探索。探索した頂点は行ったと記録する。
- 行った事がない場所には隣接行列から違う頂点に行った事がなければ、行く。その時に「距離として（グループ内の友人数として）」+1する。

Union-Find

よく知らなかったけど、このページ見た方が多分わかる。

atcoder.jp

とりあえず、ちょっと変形して実装し直して、グループの人数が増えるとparentが負になって行くので、戻して最大の値をとれば、答え。もうちょっとちゃんと説明できるように別記事にする。

コード

BFS

n, m = map(int, input().split())
# 隣接行列は作っておく
g = [[] for i in [0]*(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
def bfs(n, m, adj):
    visited = [0 for i in [0]*(n+1)]
    ans = 1
    for i in range(n+1):
        if visited[i]:
            continue
        Q = deque([i])
        group_friend = 1
        while Q:
            q = Q.popleft()
            visited[q] = 1
            link = adj[q]
            for j in link:
                if visited[j]:
                    continue
                visited[j] = 1
                group_friend += 1
                Q.append(j)
        ans = max(ans, group_friend)
    print(ans)  
bfs(n, m, g)

Union-Find

def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]

def is_same(x, y):
    return find(x) == find(y)

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x

# 今回これ使わないけど、どこに誰がいるのかはこれでわかる
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root < 0]
n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

書籍

アルゴリズムの参考書籍

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

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

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

2020-08-30

Python3で解く AtCoder Beginner Contest 177 C - Sum of product of pairs

AtCoder 競プロ ABC-C 累積和 mod

要求されている掛け算の和を累積和を使ってシンプルにする事ができるかどうかを試されている。

概要

問題
1. $n$ 個の整数が与えられる。
1. $\displaystyle{\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(a_i\ \times \ a_j)}$ を $10^9+7$ で割った余りは？

制約

$2 \leqq n \leqq 2 \times 10^5$
$1 \leqq a_i \leqq 10^9$

解くときに考えた内容

愚直にいったらTLE
数式を整理すると、まずの時を考えると
- $a_1 \times a_2 + a_1 \times a_3 ... a_1 \times a_n = a_1 \times ( a_2 + a_3 + ... + a_n)$
- なので、 $( a_2 + a_3 + ... + a_n)$ の部分は各項までの累積和を出しておいて、全体の和（もしくは累積和の最後の項）から左側からかける値までの累積和を引けばいい。
これを $a_1$ から $a_{n-1}$ まで行えば良い。

f:id:black_tank_top:20200830121540j:plain — 求めたい累積和の算出イメージ

あとmodはPythonなので、最後にmodととした。制約上問題ない。

コード

n = int(input())
A = [int(x) for x in input().split()]
mod = 10**9+7
a_cum = [0] * (n+1)
# 累積和の計算
for i in range(n):
    a_cum[i + 1] = a_cum[i] + A[i]
ans = 0
for i in range(len(A)-1):
    # a_cum[n]は全ての合計と同義。a_cumはindexが1つずれているので以下のようになる。 
    ans += A[i] * (a_cum[n] - a_cum[i+1]) % mod
ans %= mod
print(ans)

書籍

アルゴリズムの参考書籍

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

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

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

2020-08-30

AtCoder Beginner Contest 177 参加ログ・感想

AtCoder 競プロ参加ログ部分文字列

ABまでできた。Bが案外難しかった。Cは勘違いしてた。Cは単純に累積和を別リストにもって頭から順番に足していけばいいだけだったのに過去問にひきづられて困惑。DはUnion-Find（実装したことなく、無理だった）。本番弱いなぁ。

内容
結果
どう考えたか + α
おわりに

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。
E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

Aは割り算の値の大小比較。Bは検索対象側を検索ワードの幅で固定して、スライディングウィンドウしていくイメージ。ここに気づくのにめちゃ時間をかけてしまった。Cは愚直にやると無理なので先に計算しておくべき和を計算するんだけど問題を勘違いして終了。DはUnion-Findっていうのを使うんだろうなーとおもいつつ、実装したことなくて手をつけられず。BFSでもできそう。

どう考えたか + α

A - Don't be late

問題タイプ：条件分岐

$d$ を $s$ で割って、t以下かどうかでif文で分岐すればいい。

d, t, s = map(int, input().split())
if d / s <= t:
    print('Yes')
else:
    print('No')

B - B - Substring

問題タイプ：部分文字列探索

結構難しい。Pythonでは文字列がitereableなので、文字列として読み込む。 $S$ を $T$ でスキャンしていくイメージ。 $S$ の頭から、 $T$ の長さ分文字列をとって、それが $T$ のそれぞれの文字列と異なる箇所があったら、カウントする。というのを $S$ のなかで、 $T$ と同じ長さ取得できるところまでチェックして、最小のカウントが答え。

f:id:black_tank_top:20200830113652j:plain — B - Substring：Sの頭からTをスキャンしていくイメージ

S = input()
T = input()
minv = len(T)
cnt = 0
if T in S:
    print(0)
    exit()
else:
    for i in range(len(S)-len(T)+1):
        for s, t in zip(S[i:len(T)+i], T):
            if s != t:
                cnt += 1
        minv = min(minv, cnt)
        cnt = 0
print(minv)

C - Sum of product of pairs

問題タイプ：mod・累積和

$\frac{(n\times(n-1))}{2}$ パターンの掛け算の和のmodを計算する。愚直に全て計算すれば $O(n^2)$ でTLEなので、累積和を使って工夫する。これは別記事にする。

追記：

blacktanktop.hatenablog.com

D - Friends

問題タイプ：グラフ・BFS（幅優先探索）・Union-Find

グラフの問題。パッと見るとUnion-Findらしいが、実装はしたことなかったので、これを機会に実装をチャレンジした。また、おわってからBFSならスムーズにできる事がわかった。別記事にする。

追記

blacktanktop.hatenablog.com

E - Coprime

問題タイプ：素数・素因数分解当然ここまで行ってないが、素数の列挙さえ高速にできれば、できそうな問題。挑戦してみたい。

おわりに

当面の目標は、ABC完答できればDまでということで、ABで終了。Cは先週と同じく線形探索（順番に見ていくだけ）と累積和に気づけず。あとから悶絶。Cはこのパターンが多い。一度しかなめないでやるにはどういう工夫が必要かを落ち着いて考えればさっといけるようになるはず。

2020-08-28

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

AtCoder 競プロ ABC-D Greedy

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

概要

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

制約

$1 \leqq n \leqq 2 \times 10^5$
$1 \leqq a_i \leqq n$

解くときに考えた内容

1が書かれているレンガがなかったら "-1"
- Pythonでは（他の言語でもだと思うけど）if a in listは遅い。
- そのため、setで重複を削除してif 1 in set(list)のように存在を確認する。
- この処理は以下の処理の前にやる必要はないが、全部壊しても無理だったら-1としてもいいが効率が悪い気がしたので。
最終的に1, 2, 3 ... となってて欲しいのでこの順番を管理する。 (orderとする。初期値は1)
あとは並んでいるレンガがの $i$ 番目がorderじゃなかったら、壊した数をインクリメントする。
並んでいるレンガがの $i$ 番目が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)

書籍

アルゴリズムの参考書籍

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

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

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

目次

概要

解くときに考えた内容

コード

書籍

アルゴリズムの参考書籍

最近ポチった書籍

目次

概要

制約

解くときに考えた内容

参考

コード

bisect_left

bisect_right

書籍

アルゴリズムの参考書籍

最近ポチった書籍

感想

本書の概要

第1章 機械学習とは何か

第2章 Python入門

第3章 数学のおさらい

第4章 回帰分析

第5章 分類

第6章 カーネルモデル

第7章 ニューラルネットワーク

第8章 強化学習

第9章 教師なし学習

どんな人向け？

終わりに

そのほか関連書籍

お願い（欲しい書籍リスト）

目次

概要

解くときに考えた内容

BFS

Union-Find

コード

BFS

Union-Find

書籍

最近ポチった書籍

アルゴリズムの参考書籍

目次

概要

制約

解くときに考えた内容

コード

書籍

最近ポチった書籍

アルゴリズムの参考書籍

内容

結果

どう考えたか + α

A - Don't be late

B - B - Substring

C - Sum of product of pairs

D - Friends

E - Coprime

おわりに

目次

概要

制約

解くときに考えた内容

コード

書籍

最近ポチった書籍

アルゴリズムの参考書籍

第1章機械学習とは何か

第3章数学のおさらい

第4章回帰分析

第5章分類

第6章カーネルモデル

第7章ニューラルネットワーク

第8章強化学習

第9章教師なし学習