【Python】AtCoder Beginner Contest212 A,B,C問題 解答

この記事は約2分で読めます。

A問題 Alloy

 

B問題 Weak Password

4桁の数字が入力されるので、全て同じ数字の場合と、数字が1234のように1つずつ増えて連続している場合にWeak、それ以外はStrongと表示させる問題です。いくつかのパターンに分けられると思います。

[1]4桁全てが同じ場合

1桁目=2桁目、2桁目=3桁目、3桁目=4桁を全て同時に満たすにWeakと表示させることにしました。

[2]連続した数字の場合

入力される4桁の値が1ずつ増加する連続した数字だった場合です。

2桁目=1桁目+1 、3桁目=2桁目+1、4桁目=3桁目+1を全て同時に満たす場合にWeakと表示させています。

[3]9と0を含む連続した数字の場合

問題文より9の次は0になりますが、9と0を含む連続した数字は以下のパターンに分けられます。

7890, 8901, 9012

これらのパターンは個別に条件を指定してWeakと表示させることにしました。

[4]以上のどれにも当てはまらない場合

Strongと表示させています。

C問題

方針:一方は線形探索、他方は二分探索

数字の並びが2つあり、それぞれリストにして二重ループで全探索したところTLEになってしまいました。

線形探索の中でさらに線形探索を行う二重ループでは計算量はO(N^2)になり、制限時間内に終了することができずTLEとなります。

そこで、リストを小さい方から順にソートした上で一方は初めから順番に、もう一方は二分探索を使って差の最小値を調べます。

2分探索を使うときはリストがソートされている必要がありますが、初めから順に調べる線形探索よりも処理が早く、計算量はO(logN)であり、制限時間内に間に合います。

解答1:bisectを利用

 

解答2:自身で二分探索を実装

 

 

コメント