Pythonで毎日AtCoder #49

はじめに

前回
昨日のABCの結果

今日は、Boot camp for Beginners Mediumを解きます。

#49

キーエンスコンテスト2020-C

考えたこと
問題文はちゃんと読みましょう。$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)

キーエンスコンテストだけページの色が違うのは仕様?

ABC137-C

考えたこと
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))

ABC072-D

考えたこと
[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)

まとめ

日本語難しい。実装もきれいになりたい。ではまた。