はじめに
前回
昨日のABCの結果
今日は、Boot camp for Beginners Mediumを解きます。
#49
考えたこと
問題文はちゃんと読みましょう。$A_i$の要素は$10^9$以下でないといけません。
サンプルのように複数個の要素の和を計算するのは面倒です。そこで、$K$個の$S$を用意すれば楽になります。もし、$S$が$10^9$でないなら他の要素は$S$以上であればACです。もし$S$が$10^9$なら問題文より、$10^9$以下の整数にしなければなりません。ここで1以外の整数だと和が$10^9$になる可能性があるので、他の要素は1になります
n, k, s = map(int,input().split())
if s < 10**9:
ans = [s] * k + [10**9] * (n-k)
print(*ans)
else:
ans = [s] * k + [1] * (n-k)
print(*ans)
キーエンスコンテストだけページの色が違うのは仕様?
考えたこと
greenなのに茶diff。アナグラムである文字列は要素の数が同じであればいいので、文字列ごとにsortしてCounterに入れてます。←もっと簡単に書けると思います。
あとは、CounterのValueが2以上である要素に対してコンビネーションを計算します。math.factorialだとREになったので、scipyを使います。
from collections import Counter
from scipy import misc #scipyのバージョンに注意
n = int(input())
s = [list(input()) for _ in range(n)]
ss = []
for i in range(n):
a = sorted(s[i])
a = ''.join(a)
ss.append(a)
ss = Counter(ss)
ans = 0
n = len(ss)
k = ss.keys()
for i in k:
if ss[i] == 1:
continue
if ss[i] >= 2:
ans += round(float(misc.comb(ss[i],2)))
print(int(ans))
考えたこと
[False]*Nのlistをmとします。$P_i = i$のとき$m[i]$をTrueとし、これから$m[i]=True$をT、$m[i]=False$をFと書きます。mの要素の並びを分割すると(TT,TF)の二つになります。(TFT)も(TF),(FT)に分解できます。(TT,TF)のどちらも1回のswapで(FF)にできます。なぜなら、$P$に同じ要素はないので、(TF)をswapして(TT)となるようなことはありません。(TF)にも同じことがいえます。そして、swapは連続して行うことはありません。
以上のことから、$m[i]$がTならば必ず一回のswapでFにできます。
n = int(input())
p = list(map(int,input().split()))
m = [False] * n
for i in range(n):
if p[i] == i+1:
m[i] = True
ans = 0
flag = False #一個前のswapの有無の確認
for i in range(n):
if flag:
flag = False
continue
if m[i]:
flag = True
ans += 1
print(ans)
まとめ
日本語難しい。実装もきれいになりたい。ではまた。