atmark680の日記

投稿される記事の内容はすべてフィクションであり、いかなる所属する団体の見解とも一致しません

競プロ日記 ABC336 ABCDまでPythonで

せっかくやってるので記録を残していくことに

 

本番のコードまま貼っていきます

パフォーマンスはぎり水色ぐらい。Dがもっと早く解けてればねー

 

ただ文章を出力するだけなので難しいところはないでしょう

atcoder.jp

N = int(input())
print("L"+"o"*N+"ng")

 

 

atcoder.jp

2で何回割り切れるか聞かれてるのでそのままコードにしました

 

N = int(input())
ans = 0
while N % 2 == 0:
    ans += 1
    N = N // 2
print(ans)

 

 

atcoder.jp

5進法で表して、1234を2468に置換すればいいだけだとわかったので、なんかそのまんま解く。n進法に直すコピペ部分はchatgpt産

置換するところは関数とか探す方が面倒だったので地道に置換

 

chatgptの生のコメントが残ったままコピペしていたりと、いろいろ生々しいACコードです

N = int(input())

def to_quinary(N):
    if N == 0:
        return '0'

    quinary_representation = ''

    while N > 0:
        remainder = N % 5
        quinary_representation = str(remainder) + quinary_representation
        N //= 5

    return quinary_representation

# 例として、Nを指定してください
result = to_quinary(N-1)

result = str(result).replace("4","8")
result = str(result).replace("3","6")
result = str(result).replace("2","4")
result = str(result).replace("1","2")
print(result)

 

atcoder.jp

 

今回はここまでしか解けず。もっと勉強せんとね。

手の付け方から迷ったんだけど、

  • 減らすことはできる
  • 削除もできる

ということから、自身を起点に左右へどれぐらい伸ばすことが出来るかが問われていると理解。なので、n箇所について、自信を中心にしたときにサイズはいくつが最大かをそれぞれ求めて、その答えを答えにすることに。

 

例えば

1 2 3 1 2

だと、真ん中の3は左に1 2 3となるので、左へ3

右には3 1 で終わるので右へ2

となる

 

もし、1 2 3 4 2 だと、真ん中の3は1 2 3,3 2 1の両方が出来るのでサイズ3が答えになる。

 

で、問題の左右のサイズだけど、ここは両端累積和を使う。例えば、1 2 3 2 1 なら、

1 2 3 の3の時点で左にいくつまで伸びるかは、 1 2の時点の連続数を確認して、次が3以上だったら1 2 3と左に連続。次が2で1 2 2 だったら連続数は2。1だったら連続数は1 2 1 の1。

ということで、直前の累積数より大きければ +1。そうでなかったら自分自身を当てはめるという累積和を左右両方からやって、左側への連続数と右側への連続数を求める。それで、その2つのうち小さい方がその数を中心としたときの連続数の最大値。

それを全部の位置で求めて最大値を求めましょう

 

最小値の最大値とかだから二分探索を使うのかとか少し迷走してしまって、時間をとってしまった。

N = int(input())
A = list(map(int , input().split()))
l = [1]*N
r = [1]*N

if N == 1:
    print(1)
else:
    for i in range(1,N):
        if A[i]>l[i-1]:
            l[i] = l[i-1] + 1
        else:
            l[i] = A[i]
        if A[-i-1]>r[i-1]:
            r[i] = r[i-1] + 1
        else:
            r[i] = A[-i-1]
    ans = 1
    for i in range(N):
        now = min(l[i],r[-i-1])
        ans = max(ans,now)  
    print(ans)