Study

AtCorder251

AtCorder 251に参加しました。

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

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

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

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

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()

同じ文字列は最初の方が優先されるので、逆順見ていき、文字列をキーとして得点を上書きしていき、有効な文字列と得点の辞書を作成しました。であとは、その辞書から最高の文字列と得点を探し出すという解法になります。

これで通ったのですが、でもこれNGになるケースがありそうな気がします・・・

逆順に辞書に格納していて、それを先頭から評価しているので、最高得点が複数ある場合の最優秀賞が違う気がするのですが、どうなんでしょう・・・?

解説を見たら、値千金の解説がありました。

**既出の文字列の記録には、set型を使います。**この型は、要素の追加・存在確認を O(1)O(1) で行えます。list型を使うと、要素の存在確認が要素数 KK に対して O(K)O(K) と低速なため、TLEになります。

だそうです。

私は最初、まさしく解説のsetをlistにしたものを提出して、TLEになりました。

以下をもっと勉強しておく必要がありそうです。
https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb

D At Most 3 (Contestant ver.)

これも本番中に一応トライしたのですが、問題の意味がわかりませんでした。

おもりの個数1、重さ1ならどんなWでも条件満たすと思うのですが、違うのでしょうか?

と本番中はこのように考えて、試しに

pirnt(1)
print(1)

を提出してみましたが、当然NG😇

私の読解力がおかしいみたいですね。

回答の問題要約を見て、そういうことだったのかと思いました。

問題文を要約するとこうなります。

『 異なるおもりを最大3個まで選び、選んだおもりの重さの和で整数を作ります。 この方法で1以上10**6以下のすべての正整数を作ることができるように、最大300個の重さが正整数のおもりの組を構築してください。 』

で、問題の意味はわかったものの、解法を見てもよくわかりませんでした・・・

色別の正解率をみると、このD問題はE問題より正解率が低いようです。なんかイレギュラー的な感じがするので、今回は、まあ理解できなくてもいいかなということにしました。(自分が理解できないだけ😭)

まとめ

いままでは、A,Bの2完しかできなかったのですが、今回はじめてCまで解くことができました。

今回Cが解けたのはまぐれに近いですが、今後もできればCまでは安定させたいと思います。