どうもこんにちは！
今週もAtCoderのコンテストに参加できたので記録がてら振り返ります。
今回はBまでの完答。前回はCまで解けていたんですが残念。
問題
問題は以下のリンクから。取り組めたA~Cまでを振り返ります。
A - Thermometer -
体温が入力されるので、高熱(38.0以上)・発熱(37.5以上38.0未満)・平熱(37.5未満)を判定する問題。入力をif文で判定すれば解けますが、入力が小数点であることに注意ですね。ソースコードですがif-elseの順番は個人的書きやすい順で並べています。
t = float(input())
if t >= 38:
print(1)
elif t < 37.5:
print(3)
else:
print(2)
B - Ticket Gate Log -
入力されたiとoで構成される文字列に、長さが偶数で奇数文字目がiで偶数文字目がoとなるように文字を挿入していくとすると、最小で何文字の追加が必要かを判定する問題。求められている解法かよくわかりませんでしたが、シンプルに1文字ずつ見て奇数文字目がiでなければiを挿入、偶数文字目がoでなければoを挿入するとしました。
s = list(map(str,input()))
count = 0
for i,j in enumerate(s):
if i % 2 == 0 and j != 'i':
count += 1
s.insert(i,'i')
elif i % 2 == 1 and j != 'o':
count += 1
s.insert(i,'0')
elif i == len(s)-1 and len(s) % 2 ==1:
count +=1
s.append('o')
print(count)
C - Variety Split Easy -
入力として長さNの整数列が与えられ、Aを1か所で区切って分割してそれぞれの数列に含まれる要素の種類の和の最大値を求めるという問題。例えば1 2 3 3 3 4という数列があって前4個と後ろ2個の数列に分割するとき、前の数列は1,2,3の3種類、後ろは3,4の2種類で計5種類となります。なお数列Nの長さは最大で$3×10^5$。
Cで要素数の多いデータを扱うのが定番なんですね。シンプルで解けるものではないと思いつつもとりあえず、区切る位置を前から1つめの場合、2つめの場合と全部探索して最大値を探すようにしました。ソースは以下。
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(1,n):
ans = max(ans,len(set(a[:i]))+len(set(a[i:])))
print(ans)
結果は制限時間オーバーでエラー。ですよねー。for文自体はn回ですがテストケースでの要素数が多いのでクリアできないと。ここで解法が思いつかず断念しました。集合を使っての累積和を使えるかも考えたんですが、左から見たときには増えますが、右から見たときには減っていくんですよね。集合が減らす方法が思いつかず。要素そのものを扱うとすると最初の考え方と処理的には同じで意味なさそうかなと。
おわりに
3月中のコンテストはあと2回、4問完答を目標に引き続き取り組んでいきたいと思います。
ではでは。