agc 024 B,C (python)

文字列操作の問題２問。両方いけた。同じコンテストで連続して似たような題材を出すのはABCにはない感じがする。
どちらも操作回数の最小値を求めるものであるが、数え方が違った。

Bは操作を行う必要がないものについて考えると上手くいく。
少なくとも文字列のうちの一つは一回も触らずに完成できるので、最大でも N-1 回である。
例えば 1, 3, 4, 6, 2, 7, 5 とかだとすると、文字列のなかで既に 3,4,5 と 6,7 の並びは完成しているので
3,4,5 以外を操作すると、7-3 = 4 回、6,7 以外を操作すると 5 回かかる。
なので求める最小値は (文字列の長さ - 最初の状態で完成している並びの長さの最大値)
となる。
実装は i が文字列C の何番目にあるかをリストS に入れて、S を前から見ていったときに
S[i] < S[i+1] が最大何回続くかを求めた。

n = int(input())
c = [int(input()) for i in range(n)]
s = [0]*n
for i,ci in enumerate(c):
  s[ci-1] = i
cnt = 1
ans = n-1
for i in range(n-1):
  if s[i] < s[i+1]:
    cnt += 1
  else:
    ans = min(n-cnt,ans)
    cnt = 1
ans = min(n-cnt,ans)
print(ans)

C は前から最小回数になるような求め方ができる。こっちのほうが素直で解きやすいかも。
まず a[0] は必ず０である必要がある。
また A[i+1] - A[i] は最大でも 1 である。
逆にこれさえクリア出来れば A を作ることができる。
まず、0, 1, 2, 3,... , n-1, n を作る最小回数は n 回である。（ n を作るのに最小でも n 回かかり、前から順番に操作すると実現可能）
また例えば 0, 1, 2, 3, 2, ... を作ろうと思ったら、まず末尾の 2 をつくるために
0, 0, 0, 1, 0 → 0, 0, 0, 1, 2 と２回かかり、そこから 0, 1, 2, 3 で３回かかる。
よって最小回数は
A[i+1] = A[i] + 1 なら +1回
A[i+1] >= A[i] なら +A[i+1] 回増える。厳密な証明は解説読んでください。

n = int(input())
a = [int(input()) for i in range(n)]
if a[0] != 0:
  print(-1)
  exit()
  
ans = 0
for i in range(1,n):
  if a[i] > a[i-1] + 1:
    ans = -1
    break
  if a[i] == a[i-1] + 1:
    ans += 1
  else:
    ans += a[i]
    
print(ans)