AtCoder ABC130

概要

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

この記事の対象

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

本編

AtCoderとは

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

ABC130

院試の勉強に疲れたので気分転換に競プロやるぞ！って感じでやっていきます。

A Rounding

今まで見たA問題の中でも1,2を争う簡単さでした。70秒くらいで提出できたの、新記録かもしれない。

X,A = map(int,input().split())
if X < A:
  print(0)
else:
  print(10)

B Bounding

問題設定は簡単だと思ったけど、実装がこんがらがって2回WAを出してしまった挙句汚いコードを提出。
IndexErrorを出さないためにbreak文を書いておいて、最後のバウンドもXに含まれる場合を最後にif文で調整した。2WAは本当に反省。

N,X = map(int,input().split())
L = list(map(int,input().split()))

cnt = 0
D = 0
while D <= X:
    D += L[cnt]
    if cnt == len(L)-1:
        break
    cnt += 1

if D <= X:
    cnt += 1

print(cnt)

C Rectangle Cutting

本当に300点問題？ってくらい簡単だった。
長方形の対角線の交点をMとすると、M以外の点A(x,y)が指定されたときに、直線MAは長方形を２分割する直線となり、このときが最適な分割方法。 線の引き方が複数通りある場合はM=Aとなる場合のみ。

W,H,x,y = map(int,input().split())
if x == W/2 and y == H/2:
    s = 1
else:
    s = 0

print(W*H/2,s)

D Enough Array

C問題まで10分ほどで解けたので（B問題のWAは気づいてなかった）今回は新記録狙えるのでは？と期待しながらD問題へ突入。
a_1から順に、「a_iから始まり、かつ題意をみたす連続列」をカウントしていくことで、全てを網羅できます。 もう少し詳しく説明すると、a_1を考えたときに「a_1から始まり、かつ題意をみたす連続列」をすべてカウントしておくことで、a_2を考えるときにa_1を含む場合はすでにカウント済みなので「a_2から始まり、かつ題意をみたす連続列」をカウントすることで残りを網羅できます。これを最後まで繰り返すことで重複なく部分列を数えることができるというわけです。
さてこのとき「a_iからの累積和が初めてKを超えるようなa_j(i<j)」を見つけることになりますが、これを最初の実装では愚直な方法で行ってTLEに引っかかってしまいました（最悪O(N²)なので当たり前だった）。
そこでもう一度考えると、二分探索が使えるじゃないかということで書き直して通しました。
なお、二分探索にはpythonのbisectを利用しました。

import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))

acc = []
tmp = 0
for i in range(len(A)):
    tmp += A[i]
    acc.append(tmp)


cnt = 0
for i in range(len(A)):
    if i == 0:
        index = bisect.bisect_left(acc,K)
    else:
        index = bisect.bisect_left(acc,K+acc[i-1])
    cnt += N-index

print(cnt)

まとめ

今回はかなり簡単なセットだったと思うので（Dまでしか見てないですけど）、チャンスをフイにしてしまって悔しいです。
Bの細かい修正に手こずったのが１番痛かったですね。 また次回。