AtCorder251｜タムタムのアウトプット

AtCorder 251に参加しました。

A, B, Cの3完でした。参加3回目で、はじめてCまで解くことができました。

このペースだと、茶や緑になるのは、いつになるのやら。先は長そうです。

今回も解けたけど解法が怪しいもの、全然手も足もでなかった問題を復習していきたいと思います。

参考にする回答はこちら
https://qiita.com/u2dayo/items/906f4811aa4470b4ffab

Contents

A Six Characters
B At Most 3 (Judge ver.)
C Poem Online Judge
D At Most 3 (Contestant ver.)
まとめ

A Six Characters

提出したコードはこちら

s = input()
ans = ""
for v in s * 6:
    ans += v
    if len(ans) == 6:
        print(ans)

考え方は会っていそうですが、コードの書き方がスマートじゃないですね。

forループを回す必要はなくて、以下のように書くことができますね。

print((s * 6)[:6])

まだまだ、競技プログラミング脳になっていないですね・・・

B At Most 3 (Judge ver.)

かなり苦戦しました。何回も提出して時間も使いました。

TLEにも遭遇しました。B問題でも、TLEになることがあるんですね。

提出したコードはこちら

n, w = map(int, input().split())
a = list(map(int, input().split()))
ans_list = []
# 1こ
for i in range(n):
    if a[i] <= w:
        ans_list.append(a[i])
# 2こ
for i in range(n):
    w1 = a[i]
    for j in range(i + 1, n):
        w2 = a[j]
        if w1 + w2 <= w:
            ans_list.append(w1 + w2)
# 3こ
for i in range(n):
    w1 = a[i]
    for j in range(i + 1, n):
        w2 = a[j]
        for k in range(j + 1, n):
            w3 = a[k]
            if w1 + w2 + w3 <= w:
                ans_list.append(w1 + w2 + w3)
print(len(list(set(ans_list))))

最初は ans_listにappendするときに、すでに同値が存在するかどうかを in で調べて、同値がないときだけappendしていました。その場合、TLEになりました。

配列のinも計算量がO(n)かかるので、全体の計算量はn=300

O(N**2) + O(N**3) + O(N**4)

となるので、計算量は10**8 * 3以上となり、AtCorder目安の 10**8 * 2を越えてしまうということかと思います。

あれこれ悩んで、配列の重複削除でググったら、setに変換する方法に行き着いて、何とか突破できました😅

回答を見ると、lengthがW+1の配列を用意して、インデックスに相当する数値が使われたかどうかをbooleanで管理して、最後に使われたやつだけcountすれば良かったんですね。

こういう発想ができるようになりたい・・・

C Poem Online Judge

これも苦戦しました。TLEやWAの嵐で、何回も提出しました。

最終的に提出したコードはこちら

n = int(input())
st = [input() for i in range(n)]
def solution():
    org = {}  # key:s, value: org t
    for i in reversed(range(n)):
        s = st[i].split(' ')[0]
        t = int(st[i].split(' '))
        org[s] = t
    org_sort = sorted(org.items())
    max_t = 0
    max_s = ""
    for i in range(len(org_sort)):
        s = org_sort[i][0]
        t = int(org_sort[i])
        if t > max_t:
            max_t = t
            max_s = s
    # print(f"{max_s} {max_t}")
    print(st.index(f"{max_s} {max_t}") + 1)
solution()