AtCoder ABC134

概要

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

この記事の対象

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

本編

AtCoderとは

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

ABC134

最近は信号処理の勉強をしています。
FS,FT,DTFT,DFTの関係が綺麗だな〜なんて感動してますが、院試まで時間なさすぎて焦ってます。
さて、そんなわけですがABCは今はまだ参加。

A Dodecagon

はい。

r = int(input())
print(3*r*r)

B Golden Apple

一人の監視員が見られる範囲を最初2Dだと勘違いしてWAやらかしました。

N,D = map(int,input().split())
if N%(2*D+1) == 0:
    print(N//(2*D+1))
else:
    print(N//(2*D+1)+1)

C Exception Handling

今回はCまでかなり簡単ですね。
1番目に大きい数とそのindex、２番目に大きい数、この３つが把握できれば出力できます。

N = int(input())

f = 0
s = 0
index = 0
for i in range(N):
    a = int(input())
    if a > f:
        index = i
        s = f
        f = a
    elif a > s:
        s = a

for i in range(N):
    if i == index:
        print(s)
    else:
        print(f)

D Preparing Boxes

これははじめ解く方法がよくわからなくて時間を溶かしてしまいました。
数字の大きい順に定めていくと、必ず辻褄を合わせたボールの入れ方ができます。
この手法だとオーダーがN²とかになりそうだななんて勝手に悩んでたんですがそうでもなかったようです。

N = int(input())
a = list(map(int,input().split()))

b = [0 for i in range(N)]

def check(i):
    cnt = 0
    n = i
    while n <= N:
        cnt += b[n-1]
        n += i
    return cnt

for i in range(N-1,-1,-1):
    if (a[i] + check(i+1))%2 == 1:
        b[i] = 1

ans = []
cnt = 0
for i in range(N):
    if b[i] == 1:
        cnt += 1
        ans.append(i+1)

print(cnt)
L = [str(int(i)) for i in ans]
print(' '.join(L))

E Sequence Decomposing

さて、Dまで１時間くらいで解き終わって、いつもどおりだったなと思いYouTube見てたんですけど、Eもよく見たらグラフの問題じゃなくて解けそうだったので手を出すことにしました。
結論から言えば間に合いませんでした。Pythonのbisectが降順配列にも対応してたらいけたと思うんだけどな〜。悔しい。

考え方としては、空の配列を用意し、出てくる数字xを順番に

1. 配列にxより小さい数字yがあるなら、yをxに換える（ただしx-yが出来るだけ小さくなるようにyを選ぶ。yが同じ値で複数個あるときは１番右にあるyを選択する。）
2. 配列にxより小さい数字がないなら、xを配列にappendする

この操作を順番に行っていくと、最後に配列に残った数字の数が必要な色の数となります。
また、配列は常に降順で保たれます。（コード的にはinsertを使うと時間が間に合わないので、appendを使います。そのため降順ソートになります）
bisectは昇順ソートにしか対応していないので、自分で改造します。（これに少し手こずってしまいました）
まあ、普通に二分探索なんですけどね。パッと書けないあたりまだまだだな、と痛感しました。

N = int(input())

def bisect_right_reverse(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return hi

c = []
for i in range(N):
    n = int(input())
    index = bisect_right_reverse(c,n)
    print(index)
    if index == len(c):
        c.append(n)
    else:
        c[index] = n
    print(c)

print(len(c))

まとめ

前回2足りなかった緑についに到達です！スローではありますがのんびりとレートを伸ばせてます。
そろそろEも解くようにしないといけなさそうなんで、次からはなるべく挑戦してみます。
その前に院試勉強を頑張らないとですが…
それではまた次回！