Pythonで毎日AtCoder #44

はじめに

前回
Boot campの問題を5問解きます

#44

ABC056-C

考えたこと
iまでの非負整数の和は$\frac{1}{2}n(n+1)$となり}}ます。この和が$X$になるのは$\frac{1}{2}n(n+1)=X$のときで、$n$について解くと、$n=\frac{-1\pm{\sqrt{8X+1}}}{2}$となります。この式の解にceil記号を付けると$\lceil \frac{-1\pm{\sqrt{8X+1}}}{2} \rceil$となります。これが答えになります。

import math
x = int(input())

f = (-1+math.sqrt(8*x+1)) / 2
print(math.ceil(f))

ABC066-C

考えたこと
操作のたびにreverseしてると死ぬので、反転しているかをboolで管理します。データの左右にしかアクセスしないのでdequeを使います。あとは、操作を実装するだけ

from collections import deque
n = int(input())
a = list(input().split())

b = deque([])
r = False
for i in range(n):
    if r:
        b.appendleft(a[i])
    else:
        b.append(a[i])
    r = not r

if r:
    b = reversed(b)
ans = ' '.join(b)
print(ans)

類題

ARC069-C

考えたこと
まずはcをsに合成せずにいくつのsccを作成できるかを考えます。cをsに合成せずに作れるsccは$min(N,M//2)$となります。
次は合成した場合を考えます。合成すると2個のcが1個のsになるので、cからsを作ろうとすると4個のcが必要になります。あとは実装するだけです。

n, m = map(int,input().split())

if m - 2 * n >= 0: #合成せずにsccが作れるかどうか
    ans = n + (m-2*n)//4
    print(ans)
else:
    print(m//2)

ABC130-C

考えたこと
分割する点が中心にあるなら分割方法は無数に存在します。また、分割したときの大きくない方の面積は全体の半分です。

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

s = w * h / 2
if 2*x == w and 2*y == h:
    print(s,1)
else:
    print(s,0)

ARC081-C

考えたこと
$A_i$の要素についてcountするとおそらくTLEするので、別の方法でカウントしていきます。sortして値の区切りでカウントしていく方法で実装します。一番長い辺が4本以上あればそれ辺で作れる正方形が最大になります。そうでなければ、二本ある一番目の辺と二本ある二番目の辺の長方形になります。

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

a.sort(reverse=True)
c = 0
v = []
for i in range(n-1):
    if a[i] != a[i+1]:
        c += 1
        if c >= 2: #辺が二本以上のときのみappend
            v.append([a[i],c])
        c = 0
    else:
        c += 1
if a.count(a[-1]) >=2:
    v.append([a[-1],a.count(a[-1])])
if len(v) == 0: #vが空なら四角形は作れない
    print(0)
elif v[0][1] >= 4: #正方形になる
    print(v[0][0]**2)
elif len(v) >= 2: # 長方形
    print(v[0][0]*v[1][0])

まとめ

これくらいなら解ける。ではまた、