Atcoder Beginner Contest 143 振り返り 【Python】

はじめに

AtCoder Beginner Contest 143の振り返りをします。
いつも通りD問題TLEエンドです。

atcoder.jp

A - Curtain

提出したプログラム

a,b=map(int,input().split())
c = a-b*2
if c < 0:
    print(0)
else:
    print(c)

特にコメントなし。

三項演算子使うならこんな感じ

a,b=map(int,input().split())
c = a-b*2
print(0) if c < 0 else print(c)

B - TAKOYAKI FESTIVAL 2019

提出したプログラム

import itertools
N=int(input())
d_list=[int(i) for i in input().split()]
comb = list(itertools.combinations(d_list, 2))
sum_heal = 0
for i,j in comb:
    sum_heal += i*j
print(sum_heal)

これは綺麗に書けた気がします。
でも少し計算量が気になる...。
後々考えればfor文二つの方がいいのでは？ってことで書いて検証してみました

組み合わせをfor文で書いたプログラム

N=int(input())
d_list=[int(i) for i in input().split()]
sum_heal = 0 
for i in range(N):
    for j in range(i+1, N):
        sum_heal += d_list[i]*d_list[j]
print(sum_heal)

検証は実際のコンテスト (B - TAKOYAKI FESTIVAL 2019) で行いました。
結果はこんな感じになりました。

メモリも実行時間もfor文で書いたほうがよさそうですね。

C - Slimes

連続文字を一つの文字に置き換えた後のリストの長さを出力すればいいと分かれば後は書くだけです。

提出したプログラム

from itertools import groupby
N = int(input())
List = list(input())
sum_list = []
for key, value in groupby(List):
    sum_list.append(key)
print(len(sum_list))

pythonではitertools.groupbyを使うことで連続する要素をグループすることができます。ソートしてからgroupbyをするとそれぞれの要素の合計個数を調べることもできるそうです。

D - Triangles

TLE！TLE！TLE！TLE！TLE！

そろそろコンテスト中にD問題を解きたい所存。

提出したプログラム（TLE）

from collections import deque
from itertools import islice

N = int(input())
List=list(map(int,input().split()))
List.sort(reverse=True)
flag = True
while flag:
    if len(List) <= 2:
        print(0)
        exit()
    if List[0] > List[1]+List[2]:
        List = List[1:]
    else:
        flag = False
list_que = deque(List)
sum_value = 0
while len(list_que) >= 3:
    Max_value = list_que.popleft()
    while len(list_que) >= 2 and int(list_que[0]) > Max_value/2:
        for i,v in enumerate(list_que):
            for v2 in list(islice(list_que,i+1,len(list_que))):
                if Max_value < v + v2:
                    sum_value += 1
                else:
                    break
        list_que.popleft()
print(sum_value)

最初はリストで書いていたんですけどTLEだったので、dequeに切り替えて提出しました。TLEでした。
コンテスト中に考えていたことは

1. 棒を降順に並べれば制約条件を a<b+c だけにできる
2. 降順のリストをListと定義。List[0] < List[1] + List[2] が成り立たない場合、List[0]はどんな組み合わせの棒でも成り立たないのでリストから除外できる
3. List[0]とList[1]とList[-1]で条件が成り立つなら、List[0]とList[1]と他の棒は全ての組み合わせが条件を満たす

コンテスト後にプロたちのコード読んだんですけど考え方自体は問題なさそう。

上位勢のプログラム

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N-1, 1, -1):
    s = 0
    l = i-1
    while l > s:
        if L[s] + L[l] > L[i]:
            answer += l - s
            l -= 1
        else:
            s += 1
print(answer)

スマートすぎる....。でも僕の考え方は間違えていなかったようで安心しました。
上位勢の解答をいくつか見るとみんな昇順にしてforで-1ずつずらしていたんですけど、降順にしてforで+1するんじゃだめなんですかねぇ。プロの方コメントお待ちしております。

終わりに

D問題とかを文字だけで説明するのってなかなか難しいですね。今後からはiPadとかで図を書いてわかりやすくしたいと思います！