Atcoder 備忘録_N個の整数からX個を選択

概要

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

取り組む内容

• 鉄則本 に沿って実施する。
• 
• 言語は 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ではその機能が無さげなのが残念
• とはいえ、ならでは機能もあるのでしばらくはこっちでしてみる。