【ABC329】A〜D問題を解いてみた(解けなかったものあります。)

こんにちは、海月(うみつき)です。
Sky 株式会社 プログラミングコンテスト2023(ABC329)にトライしたので、その話をしようと思います。
(C問題とD問題はTLEで無理でした。。。)

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329） - AtCoder

A問題(Spread)

英大文字からなる文字列 S が与えられます。S の各文字を空白で区切り、その順で 1 文字ずつ出力してください。

• Sは長さ 2 以上 100 以下の英大文字からなる文字列

入力

S

出力

S の各文字を空白で区切り、1 文字ずつ出力せよ。

考えたこと

リストに入力された文字を1つずつ出力していき、最後の文字はfor ループから外して出力しました。空白文字を最後に出力しないようにするため。

コード

s = input()

for i in range(len(s)-1):
    print("{} ".format(s[i]),end=" ")
print(s[-1])

B問題(Next)

N 個の整数 $${A_1}$$​, $${A_2}$$​,…,$${A_N}$$​ が与えられます。 このうち最大でない整数の中で最大である整数を求めてください。
ただし、この問題の制約下で答えは必ず存在します。

• 2≤N≤100

• 1≤$${A_i}$$≤100

• $${A_1}$$​,$${A_2}$$​,…,$${A_N}$$​ がすべて等しいということはない

• 入力値はすべて整数

入力

N
$${A_1}$$ $${A_2}$$  … $${A_N}$$ 

出力

答えを出力せよ。

考えたこと

2番目の最大値を求めれば良いので、まず、リストを昇順/降順に並べ、最大値を求めました。その後、その最大値をリストから削除し、もう一度リストの最大値を求めても良いのですが、違った方法を用いました。
リストは降順に並んでいるので、前から順番に確認し、最大値ではないものが2番目に大きいものとなります。リストを前から確認するというループ(O(n))がありますが、その中の処理が軽くなるかなと考えたためです。

コード

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

#最大値
max = max(a)

#昇順に並び替え
a_sorted = sorted(a, reverse=True)

for i in range(len(a_sorted)):
    if a_sorted[i] != max:
        print(a_sorted[i])
        exit()

2番目に大きな値を出力したらexit() により終了しています。

C問題( Count xxx)

ここからは点数は貰えなかったものになります。。。
Sampleは全て動きました。

英小文字からなる長さ N の文字列 S が与えられます。
S の空でない部分文字列であって、1 種類の文字のみからなるものの数を求めてください。 ただし、文字列として等しい部分文字列同士は、取り出し方が異なっても区別しません。
なお、S の空でない部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のうち、長さが 1 以上であるもののことをいいます。 例えば、ab や abc は abc の空でない部分文字列ですが、ac や空文字列は abc の空でない部分文字列ではありません。

• 1≤N≤2×$${10^5}$$

• S は英小文字からなる長さ N の文字列

入力

N
S

出力

S の空でない部分文字列であって、1 種類の文字のみからなるものの数を出力せよ。

考えたこと

まず、与えられた文字列S から抜き出す文字列を考えました。そうすると、コードの二重ループ部分になりますが
・1文字目から2文字目
・1文字目から3文字目
…
・2文字目から3文字目
・2文字目から4文字目

のようなものが考えられます。
この中から、被りなしに、1種類の文字のみからなるものを求めれば良いです。まずは、被りがあるなしの判定として、条件にマッチしたものをリストに格納しました。そのリストに含まれていれば被りあり、そのリストに含まれていなければ被りなし(新規)として考えました。
これで、被りなしに文字列を得ることができます。

問題はここからで文字列が1つの文字で構成されているかどうかを判定します。
最初の文字と、文字列全体が同じ文字列だと良いので、最初の文字をfirst_charとして、保存しました。その後、"元の文字列"と、"first_charの元の文字列の長さ分"を比較しました。元の文字列の長さ分とすることで、同じ文字で構成されているかを確認できると思ったからです。

が、TLE(実行時間制限超過)となりました。
原因としては、2重ループをしていることに加え、その中の処理のPython の関数に計算量が多いものが含まれていると考えられます。リストに含まれているかを判定している"not in list"など。

コード

n = int(input())
s = input()

ans_list = []
for i in range(n):
    for j in range(i, n):
        #i文字目からj文字目までの文字列を確認
        if (s[i:j+1] not in ans_list):
            extract_str = s[i:j+1]
            first_char = extract_str[0]
            #first_char のみでextract_char が構成されているか
            if extract_str == (first_char * len(extract_str)):
                ans_list.append(extract_str)

#print(ans_list)
print(len(ans_list))
#print(ans_list)

D問題(Election Quick Report)

1,2,…,N の番号のついた N 人の候補者から当選者を 1 人選ぶ選挙において、M 票の投票がありました。
各票ではそれぞれちょうど 1 人が投票先として選ばれており、i 票目の投票先は候補者 $${A_i​}$$ です。
これから 1 票目から順に開票を行い、 1 票ごとにその時点で開票が終了した場合の当選者を更新して表示します。
開票された票において最も得票数が多かった候補者が当選となります。ただし、最も得票数が多かった候補者が複数いる場合は、その中で最も番号の小さい候補者が当選となります。
各 i=1,2,…,M について、1,2,…,i 票目のみを開票した場合の当選者を求めてください。

• 1≤N,M≤200000

• 1≤$${A_i}$$≤N

• 入力される数値はすべて整数

入力

N M
$${A_1}$$  $${A_2}$$  … $${A_M}$$

出力

M 行出力せよ。
i 行目には 1,2,…,i 票目のみを開票した場合の当選者の番号を出力せよ。

考えたこと

投票数が増えていくイメージですが開票されたときの投票された数を格納するリストを作成し、その中での最大値(のインデックス)を出力すれば良いのでは？と考えました。

入力リストAに対応するように投票数保存用リストを作成し、どの人(インデックス)かを出力すれば良いはずでした。

(実はこのように、リストで管理する必要性がなかったみたいです。)

コード

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

winner = [0] * n

#投票回数 a
for i in a:
    winner[i-1] += 1
    max_value_winner = max(winner)
    max_index_winner = winner.index(max_value_winner)
    print(max_index_winner + 1)

このコードも、Sampleは動きました。

最後に

全体的にコードを綺麗に書けたのでは？と思ってます。
C問題解けないの悔しい

TLEからの脱却を目指せ。

海月でした
それでは、また〜