Python3で解く AtCoder Beginner Contest 176 C - Step

その時点でのmax値を保持してその値より、小さかったら、差分を足すということを続けるだけ。

概要

問題
1. 人が並んでいる。
1. 順番に身長がである。
1. 左側に小さい身長の人がいないようにしたい。
1. 身長を+1できるステップ使って、ステップを含んだ身長で条件を満たす、最小のステップ数の合計は？

解くときに考えた内容

TLE

maxの値をさがして、それ以降をmax値にして、っていうのをリストの幅をちいさくしながら繰り返す。っていうのを考えたが、max()の計算量はなので、最初から条件を満たしているときの計算量はでダメ。

AC

左から順に考えて、その時点までのmax値(maxvとする)を保持しつつ、maxvよりも小さかったら、をカウントしていく。maxvよりも大きかったらとして、最後までforでまわせば条件を満たし、カウントの合計値が必要ステップ数の最小値になる。

矢印部分がそのときに必要な最小ステップ数のイメージ

---

コード

TLE

n = int(input())
a = [int(x) for x in input().split()]
cnt = 0
while n > 1:
    a_max = max(a[:n])
    a_max_i = a.index(a_max)
    if a_max_i != n-1:
        cnt += (n - a_max_i) * a_max - sum(a[a_max_i:n])
    n = a_max_i
print(cnt)

AC

n = int(input())
A = [int(x) for x in input().split()]
maxv = 0
ans = 0
for a in A:
    if maxv > a:
        ans += maxv - a
    else:
        maxv = a  
print(ans)

書籍

最近ポチった書籍

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

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

リンク

blacktanktop.hatenablog.com

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

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

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

drken1215.hatenablog.com

アルゴリズムの参考書籍

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

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

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

---