AtCoder ABC127

概要

AtCoderの記録です。全部Pythonで頑張ります。
E,Fは解いてないです。もっと自分のレベルが上がったらいつか解いて追記します。

この記事の対象

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

本編

AtCoderとは

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

ABC127

解いていきます。

A Ferris Wheel

場合分けです。（最初B/2をintにしてなくてWA出してしまったのが辛い）

A,B = map(int,input().split())

if A >= 13:
    print(B)
elif A <= 5:
    print(0)
else:
    print(int(B/2))

B Algae

問題文の通り実装すれば通ります。Algaeって聞いたことなかったけど藻類って意味らしい。

r,D,x_2000 = map(int,input().split())
x = x_2000
for i in range(10):
    x = r*x-D
    print(x)

C Prison

つい最近解いたABC106Dに設定が似てるな？って一瞬思ったんですけど、これはもっと簡単で最大のL_iから最小のR_iまでが答えになります。
すぐに気づけたので自分的にはけっこう早く解けました。ここまでで15分くらい。

N,M = map(int,input().split())
L = 0
R = N
for m in range(M):
    L_new,R_new = map(int,input().split())
    if L_new > L:
        L = L_new
    if R_new < R:
        R = R_new

if R - L <= 0:
    print(0)
else:
    print(R-L+1)

D Integer Cards

初めに言っておくと、かなり泥臭く解きました。
発想としては、「Aの小さい方からできるだけ大きいCに置き換えていく」で、解説にも書いてあったように最大B個の数字をCに置き換える操作は入れ替え可能ということに気づくことがポイントのようです。

図のように置き換えていきます。
するとあるところでC_iがまだ置き換わっていないA_iの最小値を下回り、そこから先はもう置き換えの操作はする必要がありません。（置き換えていない全てのA_iと以降に出てくる全てのC_jについて、A_i>C_jが成立するため）
ややこしいのは置き換えの終了条件の話で、B_i個をC_i個まで置き換えるときに①全て置き換えるのが最善、②全て置き換えないのが最善、③途中まで置き換えてストップするのが最善の３つが考えられます。（後から考えると②は③に含められますが、コンテスト中はこのように考えました）

一つの方法として、上の３つのように場合分けをすることができると思います。（なお、上の図では4,6,8,9,…の直前のA_iまでは全て置き換えられているとします。）
このとき、終了となるのは②と③のときです。①はこの先も置き換えをする必要がある可能性があります。つまり、条件分岐で①ならそのまま、②③ならbreakするようなループを書いて、置き換え操作をすれば良いことがわかります。 合計値は、ループ内では置き換えた後の値を累積していって、ループが終了したら残りの置き換わらなかったA_iを合計して足してやればいいです。
これを実装すると通ります。③の操作のときB_i回のfor文を回しますが、１度しか出てこないので計算量的にも特に問題はありません。
コンテスト中に小手先で想定外の挙動を回避しながら書いたのでコードは汚いです（あまり参考にならなくてすみません、時間があれば後で書き直します）。
また、言ったように②は③に含めてしまった方が簡単です。

N,M = map(int,input().split())
A = list(map(int,input().split()))
sortedA = sorted(A)
CB = []
for i in range(M):
    B,C = map(int,input().split())
    CB.append([C,B])

CB.sort(reverse=True)

cnt = 0
goukei = 0
flag = True
flag2 = False
for i in range(M):
    Bi,Ci = CB[i][1],CB[i][0]

    if Bi+cnt >= N:
        Bi = N-cnt-1
        flag2 = True

    if sortedA[cnt+Bi] <= Ci:
        if flag2:
            cnt += Bi
            goukei += (Bi+1)*Ci
            flag = False
            break
        else:
            cnt += Bi
            goukei += Bi*Ci
    elif sortedA[cnt] >= Ci:
        goukei += sum(sortedA[cnt:])
        flag = False
        break
    else:
        for x in sortedA[cnt:cnt+Bi+1]:
            if x <= Ci:
                goukei += Ci
            else:
                goukei += x
        goukei += sum(sortedA[cnt+Bi+1:])
        flag = False
        break
if flag:
  goukei += sum(sortedA[cnt:])

print(goukei)

まとめ

A~Cは簡単でした。Dもアルゴリズムというよりは丁寧な実装が求められる感じの問題だったと思います。
ちなみにコンテストでD問題が通せたのは初めてだったので（時間はギリギリではありましたが）嬉しいです。精進します。