AtCoder Beginner Contest 130 過去問 (A~C)

参照

atcoder.jp

A問題

1分くらい。

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

B問題

3分くらい。

N,X = map(int,input().split())
L = list(map(int, input().split()))
 
D_i, count = 0,0
for l in L:
  D_i1 = D_i+ l
  if D_i1<=X: count+=1
  D_i = D_i1
print(count+1)

C問題

茶色問題。
WAを出してしまい、30、40分かかってしまいました。

長方形をある座標(x,y)を通る直線で区切り、
小さい方の面積の最大値を求める問題です。
同じ最大値となる他の二分直線の有無も出力しなければなりません。

長方形を面積差を極力小さくする二分法ですが、
ある座標(x,y)と長方形の中心(W/2,H/2)の2点を通る直線を考えます。
ある座標(x,y)を通る直線だと無限に存在するので、
これでかなり絞れます。

以下3パターンに分けて考えます。

ある座標(x,y)が長方形の中心(W/2,H/2)である場合

面積　→　長方形の1/2
同じ最大値となる他の二分直線の有無　→ Yes

ある座標(x,y)が長方形の中心線上に存在する場合

面積　→　直線を引き小さい領域の面積
同じ最大値となる他の二分直線の有無　→ No

それ以外(ある座標(x,y)が長方形の中心線上に存在しない場合)

面積　→　長方形の1/2
同じ最大値となる他の二分直線の有無　→ No

W,H,x,y = map(float, input().split())
c_w,c_h,other = W/2,H/2,0
 
if c_h==y and c_w==x:
  other = 1
  print('%f %d'%(W*H/2,other))
  
elif c_h==y or c_w==x:
  if c_w==x: print('%f %d'%(min(W-x, x)*H,other))
  elif c_h==y: print('%f %d'%(min(H-y, y)*W,other))
    
else: 
  print('%f %d'%(W*H/2,other))

最後のパターンの長方形の辺上の座標を出力するコードも書いてみました。
あまり問題には関係ないですが・・・。

else:
  y_ = (c_h-y)/(c_w-x)
  #台形計算
  if abs(y_*c_w)>=c_h:
    point_ = [[-c_h/y_+c_h,0],[c_h/y_+c_h,c_h*2]]
    S = (point_[0][0]+point_[1][0])*abs((point_[1][1]-point_[0][1]))/2
    print('%f %d'%(S,other))
  elif abs(y_*c_w)<c_h:
    point_ = [[0,-c_w*y_+c_w],[c_w*2,c_w*y_+c_w]]
    S = (point_[0][1]+point_[1][1])*abs((point_[1][0]-point_[0][0]))/2
    print('%f %d'%(S,other))