AtCoder Grand Contest 040
はい。リアタイで問題見ていたのですが脳が思考を拒否して提出なしでした。
https://atcoder.jp/contests/agc040
A - ><
PyPy3
s=input() ans=chk=0 ans=[-1]*(len(s)+1) if s[0]=="<": ans[0]=0 if s[-1]==">": ans[-1]=0 for i in range(len(s)-1): if s[i]==">" and s[i+1]=="<": ans[i+1]=0 for i in range(len(s)): if s[i]=="<": ans[i+1]=ans[i]+1 for i in range(-1,-len(s)-1,-1): if s[i]==">": ans[i-1]=max(ans[i-1],ans[i]+1) print(sum(ans))
よく問題文を読んでよく考えていればコンテスト中にAC出来たかもしれません。サンプル1の <>>
で良い非負整数列 0,2,1,0
は、?<?>?>?
の?の箇所に、不等号の両端に数を入れ込むような感じです、多分。
仮に全て-1で初期値を設定します。 -1 < -1 > -1 > -1
それからで左端の <
と右端の >
と中間の ><
の小さくなる箇所は0で確定出来ます。 0 < -1 > -1 > 0
とりあえずは左から見て <
があったら左の数+1を右の数にします。 0 < 1 > -1 > 0
次に右から見て >
があったら右の数+1か、既に入っている数と比較して大きい方にします。 0 < 2 > 1 > 0
これが上記のコードで解になる非負整数列を作成する流れです。
右から見た時に比較して大きい方にというのは、左から見終わった後に 0 < 1 < 2 > 0
となっていて、右から見て比較しないで数を決めると 0 < 1 < 1 > 0
となり不等号が成立しなくなるのを防ぐためです。