AtCoder Beginner Contest 130 A～DをPythonで解く

このブログ、ほぼAtCoderの振り返りしか書いてない

相変わらずのA～C3完だったのですが、今日は簡単な回だった気がします

A - Rounding

正の整数Xを0か10に丸め込む閾値をAに設定する、という問題
のんびり慎重派なので、どれだけ簡単そうな問題でも文中の入力例は全て試します

x, a = map(int, input().split())

print(0 if x < a else 10)

B - Bounding

0から順に入力値を足していった時にXより大きくなるのはいつか、という問題
最後までXを超えないケースが漏れるコード設計をしてしまい一度WAをくらいました
慎重派じゃなかったのかよ...

n, x = map(int, input().split())
distances = list(map(int, input().split()))

d = 0
cnt = 1
for l in distances:
  d += l
  if d <= x:
    cnt += 1
  else:
    break

print(cnt)

C - Rectangle Cutting

長方形の内部または辺上のある一点を通って二分するとき、小さい方の最大値を求める
またその最大値となる切り方がただ一つか複数あるかを求める問題

AtCoderで初めてこんなにしっかりした算数、数学の香りがする問題に出くわした気がして狼狽えました
10分ぐらいあれこれ切り方を考えてるときに
あれ...中心通る線ならいつでも半分にできるくない...？
と脳内のギャルが閃きました
もっと早く分かりたかったという謎の傷を心に負ったまま「最大値になる(ある一点と中心を通る)切り方が複数パターンあるのは、ある一点が中心そのものである時だけ」という条件を加えて無事AC

w, h, x, y = map(int, input().split())

area = w * h
if x * 2 == w and y * 2 == h:
  center = 1
else:
  center = 0
  
print('{} {}'.format(area/2, center))

いつものCより解ける人多いから今日のパフォ下がりそうだなという生温かい気持ち

D - Enough Array

自然数列Aの連続する部分列のうち、その和がKを超えるものはいくつあるかという問題
解き方まで含めて典型問題としてどこかにありそうな気がしませんか？
N^2の愚直実装(以下)をそっと出して撤退したんですけどね

n, k = map(int, input().split())
numbers = list(map(int, input().split()))

cnt = 0
for i in range(n):
  for j in range(i, n):
    if k <= sum(numbers[i:j+1]):
      cnt += 1
      
print(cnt)

このやり方に無駄が多いのは明らかで、ポイントとしては

ある部分和がK以上なら、それが含まれている部分列は全て和がK以上
連続する部分列を考えるので、最初に左端の要素1つだけの部分列から始まって左右の仕切りが右端に辿り着けば求め終わっている

みたいなところがあるんじゃないかなと思いました

しゃくとり法というんですね
言われてみれば確かにそういう名前をしています(無知)
「競プロの勉強時間」もインターンひと段落したら取っていきたい
その頃には低めにレート出るやつもなくなって頭打ちになってると思うので頑張れそうです

解説だけ読んでPythonでACすることができました

n, k = map(int, input().split())
numbers = list(map(int, input().split()))

cnt = 0
right = 0
s = 0
for i in range(n):
  while s < k:
    if right == n:
      break
    else:
      s += numbers[right]
      right += 1
  if s < k:
    break
  cnt += n - right + 1
  s -= numbers[i]
  
print(cnt)

「持っとける値は全部持っといた方がいいことある」という学び

雑記

大学時代に知り合った人が最近とんでもない勢いで結婚を始めています
数えてみたら学部、軽音、働いていたバーで計25組35人くらいの知り合いが結婚しました
さらに結婚しそうな人たちを同じくらい知っています

並みのメンタルでは結構焦ると思いますが、現段階での

やりたい仕事
やりたい勉強
人生設計

をなかなかしっかり決めて持ってると思っているのでただただおめでとうみんなという気持ちです

本気で人類みんな幸せになってくれと思っているので
知っている人たちが幸せになるのは特にめちゃくちゃ嬉しいことです

俺に関わったことで関わってくれた人たちの人生がいつかどこかで何かしら少しでも良くなったら、という気持ちが行動原理のかなりの部分を占めているので
何か気づきや幸せを与えれる人になっていきたいですね

今日は雑記多かった
ブログっぽい(？)