概要

競技プログラミングを始めてみた。
せっかくなので１テーマごとに解法と学びをアウトプットしてみる。

取り組む内容

鉄則本に沿って実施する。
言語は Python
今回テーマは「B03 - Supermarket 1」

問題文

N 個の商品があり、商品i(i=1,2,⋯,N) の価格はAi円です。
異なる3つの商品を選び、合計価格をピッタリ1000 円にする方法は存在しますか

制約

3≤N≤100
1≤Ai≤1000
入力はすべて整数

出力

合計を1000円にする方法が存在する場合Yes、そうでない場合Noと出力してください。

解法

1回目

N = int(input())
A = list(map(int, input().split()))
Answer = False

binary_list = [[int(digit) for digit in format(i, f"0{N}b")] for i in range(2**N)]
candidate_list = []
for list_i in binary_list:
    if sum(list_i) == 3:
        candidate_list.append(list_i)

for list_i in candidate_list:
    sum_kakaku = sum([x for x, y in zip(A, list_i) if y == 1])
    if sum_kakaku == 1000:
        Answer = True
        break

if Answer:
    print("Yes")
else:
    print("No")

結果

1回目

TLEでタイムアウト
Runtime： 1112 ms
メモリ：120016 KB

正解はできるが処理効率が悪く、タイムアウトエラー
リスト内包表記も含めるとfor文を回しすぎか...

解法

2回目

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

Answer = False
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if A[i] + A[j] + A[k] == 1000:
                Answer = True
                break

if Answer == True:
    print("Yes")
else:
    print("No")

結果

2回目

AC
Runtime： 27 ms
メモリ：8704 KB

一気に数値がよくなった。
1回目と比較して無駄な処理（sum(list_i) == 3のところとか）を除外した。

思想

リストAiからいくつかの要素をピックアップするのに二進法を使ってやってみた

学び

二進法を使うアイデア自体は悪く無いとおもいつつ、今回は無理にfor文を使用して整形する必要があったのでかえって逆効果だった
やっぱりfor文は無闇やたらに使いすぎるのは良くない

感想

At coder始めてみた。Leet codeでは投稿者全体分布のうち自分のランタイムがどの位置にいたかがわかったがAt coderではその機能が無さげなのが残念
とはいえ、ならでは機能もあるのでしばらくはこっちでしてみる。