競プロ典型90問 ★2問題コード解説[3]

はじめに

本日も競プロ典型90問から2問解説していきますよ～。 何気に今日でブログの更新も１週間目、珍しく３日坊主から脱却しています。素晴らしい！！

以下が本日のメニューです。

競プロ典型90問

atcoder.jp

027 - Sign Up Requests

027 - Sign Up Requests

低橋くんが運営しているサイトのユーザ登録に関する問題です。ユーザネームがすでに存在する場合のみ登録を受理するという、ネトゲとかによくある仕様ですね。
そういえばAtcoderの開発者の名前って…

この問題の解法としては、 1. 名簿となるリストを用意する。 2. 名前が入力されたとき、名簿にその名前がなければ名簿に追加する。 3. 最終的に名簿を出力します。

以上を正直にコードに起こすと以下のようになります。

n= int(input())
user_list = [input() for i in range(n)]
meibo = []
 
for i in range(n):
    if user_list[i] not in meibo:
        meibo.append(user_list[i])
        print(i+1)

こちらのコードは一見正しそうに見えます。しかしこれだとTLE（時間切れ）してしまいます。 理由はリストにあり、リストの中にある要素があるかどうか調べるin演算子は計算量がO(N)かかります。not in演算子でも同様だと思います。
そこで、リストの代わりに集合を扱うset型で名簿を用意します。
set型はin演算子をO(1)~O(N)で扱うことが出来ます。

以下がAC（正解）したコードになります。

n= int(input())
user_list = [input() for i in range(n)]
meibo = set()
 
for i in range(n):
    if user_list[i] not in meibo:
        meibo.add(user_list[i])
        print(i+1)

033 - Not Too Bright（★2）

033 - Not Too Bright（★2）

イルミネーションが明るすぎないように、間をあけてLEDを配置するといった問題です。２×２の領域内にLEDが１つだけになるようなイルミネーションでLEDの個数が最大の場合を考えます。
また、２×２を満たさない場合、つまり１×NやN×１の場合は、N個のLEDを照らすことが出来ます。

この問題のカギは、縦横の最大点灯数を考えることです。
もしも縦の長さが3~4ならば、縦に配置できるLEDの最大の個数は2個です。横が5~6ならLEDの最大数は3個です。この場合、配置できるLEDの最大数は２×３の６個となります。
以下がコードになります。

h, w = map(int, input().split(" "))
 
if h == 1 or w == 1:
    print(max(h, w))
else:
    tate = (h+1)//2
    yoko = (w+1)//2
    print(tate*yoko)

おわりに

ここまでお読みいただきありがとうございました。
競プロ典型90問の★2問題も残り4問となってきました。
そのあとはどうするか現在考え中です。★3問題を解説するのもアリですが、かなり解説に文字を割く必要があるため、１日２問はきついかな～、なんて。
ABCの過去問のA~C問題とかやりましょうかね。