AtCoder ABC132

概要

AtCoderの記録です。全部Pythonで頑張ります。
E,Fは解いてないです。

この記事の対象

• AtCoderについてある程度知っている人
• Pythonがある程度読める人

本編

AtCoderとは

競技プログラミングコンテストを開催している会社です。 atcoder.jp

ABC132

院試まで２ヶ月を切ってきましたが参戦です。

A Fifty-Fifty

Aにしては難しいと思いました。少し戸惑った。setで文字列の要素をuniqueにし、含まれてる文字が２種類であるかのif分岐の後、それらの数をカウントしもう一つ分岐させました。

s = input()
l = [s[0],s[1],s[2],s[3]]
setlist = list(set(l))

if len(setlist) == 2:
    if l.count(setlist[0]) == 2:
        print('Yes')
    else:
        print('No')
else:
    print('No')

B Ordinary Number

逆にBは簡単です。順に見ていくだけです。

n = int(input())
p = list(map(int,input().split()))

cnt = 0
for i in range(1,n-1):
    if (p[i] < p[i+1] and p[i] > p[i-1]) or (p[i] > p[i+1] and p[i] < p[i-1]):
        cnt += 1

print(cnt)

C Divide the Problems

ソートがメインの問題ですけど、.sort()メソッドを使ってズルします。
昇順ソート後の配列の真ん中の２値をp1,p2として、Kがp1<K<=p2を満たせば、条件を満たします。 つまり条件を満たすKはp2-p1個です。

N = int(input())
d = list(map(int,input().split()))
d.sort()

print(d[N//2]-d[N//2-1])

D Blue and Red Balls

今回のD問題は数学の問題ですね。
i回の操作が必要になるボールの配置を考えていきます。

まず、青いボールK個をi個のボール群に分けることを考えます。ただし、どのボール群にも最低１つはボールがあるものとします。
このとき同じ個数の組合せの分け方でも順番が違ければ別とみなします。例えば、5個のボールを４群に分けるときに2,1,1,1と1,2,1,1の分け方は別とみなします。
このような分け方は、並べたK個の青いボールの隙間K-1箇所にi-1個の仕切りを入れて分けると考えて、K-1 C i-1通りあります。

次にそのi個の青いボール群を赤いボールの隙間のどこかに入れることを考えます。
並べた赤のボールN-K個の間と両端の合計N-K+1箇所のうち、i箇所に先ほど作った青いボール群を入れ込むことを考えて、N-K+1 C i通りです。

これら二つの場合の数は独立しているので、掛け合わせてinf値で割ったものが答えです。

一つだけ気をつけたいのは、N-K+1<iの場合です。
この場合、分け方が存在しないため、0を出力しなければなりません。（これを見落としていてかなり時間を無駄にしました…）

N,K = map(int,input().split())
inf = 10**9+7

def fact(a,b):
    tmp = 1
    for i in range(a,a-b,-1):
        tmp *= i
        #tmp = tmp%inf
    return tmp


def conv(a,b):
    if a-b > b:
        p1 = fact(a,b)
        p2 = fact(b,b)
    else:
        p1 = fact(a,a-b)
        p2 = fact(a-b,a-b)
    return p1//p2%inf

for i in range(1,K+1):
    if i-1 > N-K:
        print(0)
    else:
        print(int(conv(K-1,i-1)*conv(N-K+1,i))%inf)

ちなみに、conv()の中身で条件分岐をさせていますが、これは計算を少しでも早くしようとした工夫で、別になくても結果的に余裕で間に合いました。

まとめ

C問題までは15分以内くらいに通せて、かつD問題も解法がすぐに思い浮かんだため、これはハイスコアか！と思いましたが、見落としていたポイントがあり、WAを連発し期待ほどの順位にはなりませんでした…。（とはいえパフォーマンスは1200ちょいで一応自己ベストでした）
そろそろパフォーマンス1500とかを目指していきたいです。院試が終わったらちゃんと過去問解いてアルゴリズム勉強します。