はじめに
こないだはじめてAtCoderのコンテストに参加してみました。過去問はほんのちょびっとだけ解いたぐらい。
マジの初心者なんですが、なんかCがむちゃ簡単でDもなんかいけるのでは？ って思ったので解いてました。時間内にはだめだったけど。
プログラミング強人（つよびと）の解答、マジのスマートすぎて初心者には難しいです。え？ そんな入力の受け取り方ある？！ その出力の仕方アリなの？！ みたいになる。精進します。
とりあえず自分で考えたアルゴリズムでどうしてダメだったのか考えていこうと思います。自分の考えた操作をきちんとコードとして書きおろせなければ意味ないので。
問題はABC148のD問題より。以下引用です（ルールに則っているつもりですが、間違っていれば教えてください）。
（どうでもよい追記）
蟻本まだ買ってないです。持ち金が少ないので。学校の図書館にあれば年末年始借りるかも。
それとなく買ってほしいな～ってパッパにねだったつもりが、方向性をミスったのでおうちにあった
・アルゴリズム教科書 -実用的なプログラムで示すアルゴリズムの基礎と応用-
・アルゴリズムパズル -プログラマのための数学パズル入門-
の本を貸してもらい、まあまずはアルゴリズムを学びたいわけだし、これでいいやと思いました。てか前者の本、わたしより年上なんですけど……
D - Brick Break
N個のレンガが横一列に並んでいます。
左からi(1≤i≤N)番目のレンガには、整数aiが書かれています。
あなたはこのうちN−1個以下の任意のレンガを選んで砕くことができます。
その結果、K個のレンガが残っているとします。
このとき、任意の整数i(1≤i≤K)について、残っているレンガの中で左からi番目のものに書かれた整数がiであるとき、すぬけさんは満足します。
すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力してください。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力してください。
考えたこと
①1から順に数字が並んで残ればいいらしい。
②じゃあ前からインデックスと一緒に確かめて、違うやつを消していけばいいか1
固有名詞ってどうやって決めてるんだろう。あと比喩の要素は何をどうしてこうなったんだ。など。
1回目
n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
#index+1がリストの要素と違ったら削除
if a[i] != i + 1:
del a[i]
#同じなら次の要素を確認
else:
i += 1
#全部消しちゃったら不可能
if len(a) == 0:
print(-1)
#残ってる要素を引いたら壊した数になる
else:
print(n - len(a))
いくつかのテストケースでTLEに。
う～～～んしばらく考えたけど何がだめなのかわかんない……絶対にあっているという自信こそないけれど。無限ループでTLEなんじゃなく、数列が長すぎるテストケースの時に時間オーバーしたとかじゃないだろうか？ あまりこのへんのしくみを完全に理解していないけれど。
このあと悩みながら途中でbreakさせたりしてたけど全然関係なかったので省略。
4回目
③一個ずつ消すから良くなかったかも。一気に消せばいいじゃん。
とのことで、
n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
#index+1がリストの要素と違ったら
if a[i] != i + 1:
#正しい要素があるか確認
if i + 1 in a:
#正しい要素の手前まで削除
del a[i:a.index(i + 1)]
#正しい要素がないなら全部削除
else:
del a[i:]
#index+1がリストの要素と同じなら次の要素へ
else:
i += 1
#全部消しちゃったら不可能
if len(a) == 0:
print(-1)
#残ってる要素を引いたら壊した数になる
else:
print(n - len(a))
これで通りました。やったね。
強人（つよびと）の解答
全然関係ないけど別に読み方きょうじんでもよいですね。狂人みたいで。2
- 現時点で最短のコード、全く意味がわからなさすぎて泣いちゃった34
- 変数にリストを入れることすらせず、直接入力を確かめている
- 正しい要素にあたる変数をおき、リストの要素を前から確かめ、同じなら+1して次へ
- print内でもifとか使えるんだ……てかこれ何……？
わたしはなぜかきれいなレンガの並びを求めようとしていたけれど、きれいに並んだレンガの数を数えるだけでよかったという感じですね。
三項演算子っていうんだね
if, else文を一行で書いていいらしいです。
（真ならこう返すよ）if（この条件で）else（偽ならこうね）
こんな感じ。コロンもいらない。便利だなあ。
なので、最後4行は
print(-1 if len(a) == 0 else n - len(a))
でよい。なるほど～！ 学び。