日刊競プロ ABC 227 -B - KEYENCE building-

B-Keyence building

問題文
1 から N の番号がついた N 人の人がいます。人 i はキーエンス本社ビルの建築面積を Si平方メートルであると予想しました。キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。
N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。

図は割愛

制約
1≤N≤20
1≤Si≤1000
入力に含まれる値は全て整数である

考えたこと

制約からMaxでも予想した面積は1000なので、a,bの最大は1000になると考えた。つまりa、bを1000まで２回ループさせれば良いと考えた。（10**6なので間に合うのでは？と考えた）

回答

N = int(input())
Slist = list(map(int,input().split()))
count =0
for s in Slist:
 flag = False
 for a in range(1,1001):
   for b in range(1,1001):
     if s-(4*a*b+3*a+3*b)==0:
       flag = True
       continue
 if not flag:
   count+=1
           
print (count)

しかし、Python3ではTLEで間に合わなかった。調べてみたところPyPy3では間に合うとのこと。。。

せっかくなのでPython3とPyPy3の違いを調べてみた。

高速動作するPython「PyPy」とは？概要と速度をチェック

まず、RPythonというCPythonのサブセットがあります。これはつまり制限付きのCPythonで実装されたPython処理系です。そしてそのRPythonを使って実装されたのがPyPyになります。PyPyのプログラムはJust-in-Time（JIT）コンパイルという、実行時にコードのチャンクを実行時に逐一コンパイルするシステムを使って高速化されています。JITコンパイルは何度も使われるコードを最適化するため、Pythonのコードでもかなり早く動かすことができます。

何度も使われるコードを最適化するということで，DPのように何回も計算する処理を改めてメモ化している？

さらに調べたとこと

JVM JITコンパイラの仕組み

ソースコード -> コンパイル -> 中間コード -> 実行（コンパイル）

JVM言語は、コンパイルを走らせた際に（javaではjavac、scalaではsbt compileなど）、対象の全てのソースコードをコンパイルするわけではない。
まず、中間コードを作成する。(java bytecode)。この中間コードを生成するプロセスを挟むことで、JVM環境さえあれば、どのOSでも同じコードを実行できるようになった。（JVMは、それぞれのOSに適した物を入れる必要がある）その後、作成した中間コードを一気にコンパイル（nativeコードに変換）はしない。
インタプリタでソースコードを実行の都度コンパイルしている。（上図で言うと Java interpreter）

都度コンパイルする理由は，１度しか使わない処理が無駄になることと，最適化するため．（最適化するために都度コンパイルする仕様にしているらしい）

おまけ

キーエンス本社ビル（wikipediaより）

なかなか特徴的な形をしている．．．

入社した奴の親戚は新たに入社できないという決まりらしいが本当か・・・？