ferinの競プロ帳

競プロについてのメモ

ABC019を解いてみた

A問題

 入力を配列として受け取り、sort関数を用いてsortしたあと中間の要素を出力しました。

a = [int(i) for i in input().split()]

a.sort()
print(a[1])

B問題

 変数sに入力の文字列を受け取り、先頭から連続した文字が何個続くのかを求め、文字と続く個数を答えの変数に追加、そして答えに入力した分を文字列sから取り除きます。この処理をsがなくなるまで繰り返すことで答えを求めました。

# 文字列sの先頭から同じ文字が何個連続しているのかを返す
def countConsectiveCharacter(s):
    # 少なくとも1文字は連続している
    cnt = 1
    for i in range(len(s)-1):
        if(s[i] == s[i+1]):
            cnt += 1
        else:
            return cnt
    return cnt

# 入力
s = input()

i = 0
ans = ""
while len(s) > 0:
    c = countConsectiveCharacter(s)
    ans += s[0] + str(c)
    # sがなくなったら終了
    if len(s) == c:
        break
    # c番目からの文字を切り出してsに代入
    else:
        s = s[c:]
    #print("s[i], c, ans")
    #print(s, c, ans)

print(ans)

C問題

 全探索ではO(n^2)と部分点の制約しかクリアできそうにありません。そこで工夫した方法を考えると、xと2xが等しくなるならば要素の値を2で割り切れなくなるまで割っていき、異なる要素の個数を数えることで結果を求めることができます。これならば計算量はO(n)で実行時間には問題なさそうです。

n = int(input())
a = [int(i) for i in input().split()]

# 各要素について適用
for i in range(len(a)):
    # 2で割り切れなくなるまで割っていく
    while(a[i] % 2 == 0):
        a[i] = int(a[i]/2)

# setでリストの重複を取り除き、listで配列化 lenでその要素数を数える
print(len(list(set(a))))

D問題

 問題文を読んでまず出力の形式に驚きました… 解説に基づいて実装しました。