そろそろ頭がいる
41. mod 3で上限を評価したあと、順列吐かせて素数判定。こんなので頭を使ってはいけない。
42. 虚無。題意を読み間違えてまくったので、ぼくは虚無未満の人間です。
43. 脊髄反射順列生成マン
44. いまいち釈然としない。差が小さいけど和はとんでもなく大きい、みたいなケースを消しきれず、しかたなく小さいケースで調べて投げたら通ってしまった。ちゃんと証明するなら式をいじるしかないのだろうか。うーむ。
45. 問題44でもそうだが、五角数とか六角数とかの判定は、n になりそうな数を計算してから一致するか確かめると O(1) でできる。いままで判定リストを作ってバケツっぽく調べていたが、これだといろいろ不都合なく調べられそう。あとは三角数をしたから列挙すればOK.
ところでこういう数って無限にあるんですかね。2 種類だとペル的に無限にありそうだけど、3 種類だと不明すぎる。一般のほげ角数への理解が足りない...
46. 意外と小さかった。過去の人々、探索力足りてなくな〜い?(言いがかり)
47. けっこう探索時間がかかった。Pythonで 1 分だと 10^9 くらいの計算時間が目安かなぁ。
48. なんでこの問題だけ解かれてるんや、みんなこんな問題好きなんやね〜
... と思って考えたら、ただ簡単なだけだったというオチ。mod 1e10 です。最初ビック数DPメソッドしようとしててアホだった。O(N logN) でできるけど、頭がついてなかったので O(N^2) です。
49. 4 桁の素数は 1000 個くらい。その二乗くらいの計算量。だんだんこういう計算量を意識する必要が出てきた。
50. 累積和って知ってますか?知ってたとしても、現実的な計算量にするために少し工夫した方がよさそう。
これで Level 2 になりました。いぇい。
虚無ゾーンを抜けたっぽい。こっからが本番。