なんちゃって解説 第1回 - ABC251 A~C問題

はじめに

こんにちは、ひろとです。この記事は題名の通りABCをなんちゃって解説していきます。今から書いてある内容は競プロを1年弱やっている高校生なりの見解です。玄人の方々からしたら「違うそうじゃない」となることが多いかもしれませんが、その際はコメントの方でご教示いただけると幸いです。

記事の対象

このシリーズは最低限のPythonの知識を持っていて、AtCoderを始めたての方々を対象としています。もしPythonの知識に不安があったり読んでいる途中でわからないことが出てきたらQiitaで検索してみたり、Google大先生で調べてみることをおすすめします。Googleなどで調べる際はPython (知りたい内容)のように調べると比較的出てきやすいんじゃないかなと思います。(ex. Python set 使い方)

Pythonのバージョンについて

基本的にはAtCoderのジャッジシステムで使われているバージョン(記事執筆時点では3.8.2)を使います。

ABC251

本題に入っていきます。今回のコンテストのABC問題は比較的易しかったと思います。ただ、C問題はsetの存在やメリットがわかっていないとTLEで弾かれてしまうものでした。

A問題 - Six Characters

問題リンク: A - Six Characters

制約

• Sは英小文字からなる長さ1以上3以下の文字列

入力

S

出力

答えとなる長さ6の文字列

考察

Sを何回か繰り返して6文字の文字列ができればいいので、Sを6回繰り返して出来上がった文字列の先頭6文字を出力すればOK。Sの長さが1~3なので、最低6回繰り返せば確実に長さが6になるため6回にしています。10回でも100回でも問題はないです。

回答コード

クリックして展開

s = input()
ans = (s * 6)[:6]
print(ans)

B問題 - At Most 3 (Judge ver.)

問題リンク: B - At Most 3 (Judge ver.)

制約

• 1 <= N <= 300
• 1 <= W <= 10⁶
• 1 <= A_i <= 10⁶

入力

N W
A_1 A_2 ... A_N

出力

答えを出力

考察

重りの組み合わせは1~3つの場合が存在しています。そのため、それぞれの場合に対してforループで計算していけばOKです。ここで、「重りの個数が3つのときにforの3重ループが発生してTLEしてしまうのでは？」と考えた方がいると思いますが、この問題の制約にN <= 300とあります。Nは重りの個数を表しています。そのため、for3重ループで全列挙したとしても計算量はO(N^3)で最悪の場合でも2.7*10^7なのでギリギリ回し切ることができます。もしN <= 10^9などの場合はO(N^2)になった時点でTLE確定です。制約を読んでいれば気づけることも多いので制約はちゃんと読みましょう！
下に貼ってあるのは僕が実際に提出したコードですが、itertoolsを使わずにfor3重ループでも計算量は同じです。itertoolsの使い方はこちらのサイト様が参考になると思います。
下のコードでは計算の中で「いい数字」を全てansに追加して、あとからset()で重複を無くしていますが最初からsetを使ったほうがコードももうちょっと綺麗になったんじゃないかなーと思ってます。

回答コード

クリックして展開

import itertools


n, w = map(int, input().split())
a = list(map(int, input().split()))

ans = []

l2 = itertools.combinations(a, 2)
l3 = itertools.combinations(a, 3)

for i in a:
    if (i <= w):
        ans.append(i)

for j in l2:
    s = sum(j)
    if (s <= w):
        ans.append(s)

for k in l3:
    s = sum(k)
    if (s <= w):
        ans.append(s)

print(len(set(ans)))

C問題 - Poem Online Judge

問題リンク: C - Poem Online Judge

制約

• 1 <= N <= 10^5
• Siは英小文字からなる文字列
• Siの長さは1以上10以下
• 0 <= T_i <= 10^9
• N, T_iは整数

入力

N
S_1 T_1
S_2 T_2
...
S_N T_N

出力

答えを出力

考察

この問題はsetを知らないと確実にTLEしてしまう問題でした。もし普通の配列(list)を使って毎回in演算子で存在確認をしてしまうと計算量が爆発します。x in listの計算量はO(配列の長さ)で、x in setの計算量はO(1)です。もしlistを使うと、ループを重ねるごとに配列の長さが伸びていき、最終的には存在確認だけでO(N)かかってしまいます。これがわかればあとは特に難しい実装は無いのではないのかなと思っています。

回答コード

クリックして展開

n = int(input())
d = set()
best = [0, 0]

for i in range(n):
    s, t = input().split()
    t = int(t)
    if (s not in d and best[1] < t):
        best = [i, t]
    d.add(s)

print(best[0] + 1)

あとがき

先に謝らせて下さい。数式読みにくいですよね…。これを書いている最中にMathJaxの存在を知ったのですが、使い方を全く知らなかったため今回はこのような形で書かせていただきました。次回以降はなるべくMathJaxで綺麗な読みやすい記事を目標に書いていきます。今後の記事でも自分がコンテスト中に解くことができた問題を解説していこうと思っています。Ex問題まで解説できるレベルになるべく頑張りますので、今後もよろしくお願いいたします。