どうもこんにちは！
今週のコンテストはBまで完答。CはTLEにはなるコードをなんとか書けたという程度でした。
問題
問題は以下のリンクから。解説を踏まえてCまでを振り返ります。
A - Conflict -
長さNの数列が2つ与えられ、いずれかの番目の値が〇で一致するならYes,一致するところがないならNoを出力する問題。
シンプルに数列を最初から順番に比較して、いずれかの場所で一致しかつ値が〇のところがあればYesを出力するとしました。なお、コンテスト時は値が〇で一致するというところをケアしておらず2つ×を付けました。。
n = int(input())
t = list(input())
a = list(input())
ans = False
for i in range(n):
if t[i] == a[i] and t[i] == 'o':
ans = True
break
if ans == True:
print('Yes')
else:
print('No')
B - Citation -
長さNの非負整数列が与えられるので、この数列にx以上の要素が重複を含めてx回以上現れる最大の値xを求めるという問題。例えば数列が1 2 2 3 1なら、x = 2としたときに3回現れますが、x = 3 だと1回しか現れないので答えは2となります。なお数列の長さの最大は100です。つまりxとなりうる最大値は100です。
さて、解説をみると、長さNということはxとなりうる値はN以下なので、全部数えたら終わりということでした。コンテスト中はものすごく難しく考えたらしく、前回のコンテストであったいもす法を使って0からそれ以上の値が何個あるか計算してみたいなことやってました。。変に勉強するとそれを使いたくなるやつですかね。なんとか完答はしていますが、この時点でだいたい1時間ほど使っていました。
n = int(input())
s = [int(x) for x in input().split()]
count = [0 for _ in range(101)]
total = [0 for _ in range(101)]
for i in s:
count[min(100,i)] += 1
total[100] = count[100]
for i in range(99,-1,-1):
total[i] = total[i+1] + count[i]
ans = 0
for i in range(101):
if total[i] >= i:
ans = i
else:
break
print(ans)
C - Equilateral Triangle -
円周がLの円があり、この円周上にN個の点が配置されています。1個目を基準として、i+1番目の点はi番目から$d_i$進んだ位置にあるして与えられます。円周上の点a,b,cがすべて異なる位置にあり、この3点を頂点とする参加角形が正三角形になる点の組み合わせの個数を求めるという問題。円周および円周上の点の数は最大で$3×10^5$です。
円周上の3点を結んで正三角形になるには、各点間の長さが同じになるはずです。円周をちょうど3分割する形ですね。
あまりに時間がなくてすべての点の組み合わせでそのようになるかを判定するコードを実装まではできたんですが、TLEとなりました。以下はコンテスト中に作ったコードです。。
n, l = map(int,input().split())
s = [int(x) for x in input().split()]
s.insert(0,0)
length = [0 for x in range(n)]
for i in range(1,n):
length[i] = (length[i-1] + s[i]) % l
ans = 0
for i in range(n):
for j in range(i,n):
for k in range(j,n):
a = length[j]-length[i]
b = length[k]-length[j]
c = length[i]-length[k]
if a < 0:
a += l
if b < 0:
b += l
if c < 0:
c += l
if a == b and b == c and a > 0 and b > 0 and c > 0:
ans += 1
print(ans)
解説をみると、円周をL等分してそれぞれの位置に何個点があるかを計算し、基準点から$L/3$先の点と$2L/3$先の点の数を掛けたのを足し合わせたのが答えということでした。例えば円周が6なら、$d_1$と$d_3$と$d_5$にある点の数をかけたものと、$d_2$と$d_4$と$d_6$にある点の数をかけたものの合計ということでした。各点の位置ではなく、位置ごとの点の数に着目するのがポイントだったんですね。
ではでは。