BETA

初心者日記(4)『AtCoder (Distinct or Not)を解く』

投稿日:2020-06-12
最終更新:2020-06-24

AtCoderの過去問ACが250問を越えていた。やったぁ。

300点の問題も少し解けるものが出てきた。成長を感じる。

ここら辺になると、『全探索してたら時間かかりすぎてTLEでアウト』現象が起こる。
ABC154のC問題『Distinct or Not』で初めてTLEになってしまった。問題は整数列が全部異なる数字か調べるもの。

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

for p in range(n):  
    for i in range(n):  
        if p == i:  
            pass  
        elif a[p] == a[i]:  
            y = False  
        else:  
            pass  

if y:  
    print('YES')  
else:  
    print('NO')  

まず、for で p と i が一緒かどうか全探索で調べる。これでTLE。ここでは、『1 と 2 3 4』『2 と 1 3 4』というように同じものを2回調べているから駄目だと思い、そこを改善した。

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

for p in range(n):  
    i = p + 1  
    while i < n:  
        if a[p] == a[i]:  
            y = False  
            break  
        i += 1  

if y:  
    print('YES')  
else:  
    print('NO')  

for の中を書き直し、『1 と 2 3 4』『2 と 3 4』というように同じものは比較しないようにしたがTLE。なんでや!

これでだめなら、今の探索の仕方がだめだとしか思えない。ていうか数列最大20万て比較回数最大約200億、そりゃTLEになっちゃうわ。この200億をもっと減らす抜本的なコードを考えないといけない...

よく考えたら、この問題は同じ数字があれば NO を出力する問題。同じ数字を一か所に集められたら比較ももっと楽になるだろうな。

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

for i in range(n - 1):  
    if a[i] == a[i + 1]:  
        y = False  
        break  

if y:  
    print('YES')  
else:  
    print('NO')  

集めれた。ソートして昇順に並べれば、隣同士を調べていくだけで終わる。200億を20万に減らすことができ、無事AC!
このように、探索回数を減らしてACする問題も正解できるようにしていきたい。

追記:コロナじゃないですが頭が痛くて寝込んでました。体調を整えるのも大切ですね。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

tnodino(つのでぃの)のブログ。日頃の内容を記事にしています。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう