AtCoder Beginner Contest 143 ／ Python

●　初学者です。（ 2019 / 9 ～ 現在３ヵ月目 ）
●　AtCoder の問題に Python で取り組んでいます。
●　ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントくださいませ。

A - Curtain

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

if a >= b*2:
   print(a-b*2)
   
else:
   print(0)

B - TAKOYAKI FESTIVAL 2019

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

ans = 0

for i in range(n-1):
   
   for j in range(n-1-i):
       a = d_list[i]*d_list[i+1+j]
       ans += a
       
print(ans)

メモ：itertools で組合せを列挙する

import itertools

n = input()
d_list = list(i.combinations(list(map(int,input().split())),2)

ans = 0

for i in d_list
   
   a = i[0] * i[1]
   ans += a
       
print(ans)

最初の入力要らんやん。

C - Slimes

n = int(input())
s = list(input())

ans = 1

for i in range(n-1):
   
   if s[i] != s[i+1]:
       ans += 1

print(ans)        

D - Triangles

※　実行時間制限超過

import itertools

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

a = list(itertools.combinations(l,3))
b = []

for i in a:
   b.append(tuple(sorted(i)))

c = list(set(b))

count = 0

for i in c:
   
   if i[0] < i[1] + i[2] and i[1] < i[0] + i[2] and i[2] < i[0] + i[1]:
       count += 1
       
print(count)        

地道に求めるコードを書いたが、デカい数に耐えられない。

メモ：要「二分探索」

追記：

出来てるかよくわからん二分探索。

[1,1,1,2,2,3,3,3,3] から 2 以上になる位置を求める。

input_list = [1,1,1,2,2,3,3,3,3]
check = 2

low = 0
high = len(input_list) - 1
       
while low < high:
           
   mid = (low + high)//2
           
   
   if check > input_list[mid]:
               
       low = mid + 1
           
   else:    
               
       high = mid 
else:
   print(low)

2 が複数個あるとき、右端を求める。

input_list = [1,1,1,2,2,3,3,3,3]
check = 2

low = 0
high = len(input_list) - 1
       
while low < high:
           
   mid = (low + high)//2
           
   
   if check >= input_list[mid]:
               
       low = mid + 1
           
   else:    
               
       high = mid 
else:
   print(low - 1)

書き直してみたが、結局、実行時間制限超過。

n = int(input())
l = sorted(list(map(int,input().split())))

check_i = 0
check_j = 0
count = 0 

for i in reversed(range(0,n)):
   if l[i] == check_i:
       check_i = l[i]
       continue
   
   for j in reversed(range(1,i)):
       
       if l[j] == check_j:
           check_j = l[j]
           continue
       
       
       
       if l[i] - l[j] >= l[j-1]:
           continue
       
       low = 0
       high = j-1
       
       while low < high:
           
           mid = (low + high)//2
           
           if l[i] - l[j] >= l[mid]:
               
               low = mid +1
           
           else:    
               
               high = mid
       else:
           
           count += len(set(l[low:j]))
print(count)            

もう無理。

AtCoder Beginner Contest 143 参戦記 - Qiita

正解を書いてくださっている方がいた。

from bisect import bisect_left

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

L.sort()
result = 0
for i in range(N - 2):
   for j in range(i + 1, N - 1):
       result += bisect_left(L, L[i] + L[j]) - j - 1
print(result)

こんな短いんかい、というか二分探索って標準ライブラリにあるんかい。

追追記：

悔しいから結局しつこくやっていた。

今更だけど、棒は同じ長さでも区別できる設定だった。

やっと通ったやつ。二分探索は自分で書いている。

n = int(input())
l = sorted(list(map(int,input().split())))

count = 0 

for i in range(n-2):
   for j in range(i+1,n-1):
       
       if l[i] + l[j] > l[n-1]:
           count += n-j-1
           
           continue
       
       low = j+1
       high = n-1
       
       while low < high:
           
           mid = (low + high)//2
           
           if l[i] + l[j] > l[mid]:
               
               low = mid +1
           
           else:    
               
               high = mid 
       else:
           
           count += low - j -1
print(count)            

これも Python では通らない、が、PyPy なら通った。

PyPy について、知らんけど Python の早いやつ、くらいの認識しかないが、こういうことになるなら少しちゃんと知っておかないといけないかも。

いやぁ、やっっっと、この問題から解法された、結局10時間くらい考えていたのではないだろうか。本当にスッキリした。やっと142回に進める。

E - Travel by Car

考えてない。

メモ：要「ワーシャルフロイド法」

F - Distinct Numbers

見てもない。

マガジン：他の回もやっていきます。

AtCoder Beginner Contest｜もやし｜note