【AtCoder】PythonでABC238のA問題を丁寧に読み解く

実際の問題はこちらからご覧ください。

この問題のポイント

不等式が成立する範囲を考えて、実行時間を短くできる工夫ができるかどうか。

不等式「2^n > n^2」が成立するかどうかの閾値を考えてみると以下のようになる。

n	2 ^ n	n ^ 2	2^n > n^2
1	2	1	Yes
2	4	4	No
3	8	9	No
4	16	16	No
5	32	25	Yes
6	64	36	Yes
7	128	49	Yes
8	256	64	Yes
9	512	81	Yes
10	1024	100	Yes
…	…	…	…

①n = 1：nが1のときは2>1になり、不等式は成立する。

②2 <= n <= 4：この範囲の時だけ不等式が成立しない。

③5 <= n：nが5以上の時は不等式が成立する。

１. 入力の取得：n = int(input())によって整数nが入力される。

２. nの制限：n = min(n,5)により、nの値を5以下に制限する。これは、不等式2^n > n^2が成立するかどうかを検証する際に、特定の範囲のnに焦点を当てるため。この範囲内にすることで、2^nの計算に要する時間を短くできる。

３. 結果の出力：if pow(2,n) > n*nにより、問題文に指定された不等式の検証をした結果を出力します。

まず最初のコードは、AtCoderで提出したところ　”TLE(Time Limit Exceeded)”　という問題で指定された実行時間以内にプログラムが終了できず不正解になってしまいました。

このアルゴリズムの計算量は理論的には、O(1)であると考えられるが、nの値が大きい場合に2^nの計算に要する時間が膨大にかかってしまう。

n = int(input())
if 2**n > n**2:
  print('Yes')
else:
  print('No')

次のアルゴリズムの計算量もO(1)ですが、nの値を１〜５で制限しているため計算に要する時間を削減しています。

n = int(input())
n = min(n,5)
if pow(2,n) > n*n:
  print('Yes')
else:
  print('No')

次のコードは、”この問題のポイント”に載せた表を忠実に再現したものです。最初のif()文で不等式が成立する範囲を指定しています。こうすることで、演算をすることもなくnの値だけで結果を出力することが可能です。

n = int(input())
if n == 1 or n >= 5:
  print('Yes')
else:
  print('No')