考えすぎると頭がかゆくなる

上記の広告は１ヶ月以上更新のないブログに表示されています。新しい記事を書く事で広告が消せます。

O記法の他にθ記法がある。
θ記法は上からも下からも挟める時に使う。（上界と下界がある）
O記法は上界のみを示す時にも使える。
例えばf(n) = a*n + bについて、O(n^2)であるがθ(n^2)ではない。θ(n)。
曰く、

以前にO記法を見たことのある読者の中には、たとえば、n=O(n^2)という表現を見て奇妙に感じた人がいるだろう。文献では、O記法は略式には漸近的にタイトな限界、すなわちθ記法を用いて定義したものを記述するのに用いられることもある。しかしながら、本書でf(n)=O(g(n))と書くときには、単にg(n)のある定数倍がf(n)の漸近的上界であることを主張しているだけであって、上界がどれほど近いかは主張していない。漸近的上界を漸近的にタイトな限度と区別する事は、アルゴリズムの分野では今や標準的になってきている。

cout << __builtin_popcount(3) << endl; // -> 2
cout << __builtin_popcountll(979087009788987098LL) << endl; // -> 31

かなり歯応えのある問題。

あなたは誘拐され、目隠しされた状態で自宅の庭に放置された。
庭にはバラが植わっている。バラの配置図は記憶しているが、目隠しされているので、自分がどの方角を向いているのかはわからない。ただし自分が庭の中心にいるという事はわかってる。
この状態で、最悪のケースで踏んでしまうバラの数ができるだけ少なくなるようなルートで庭から逃げたい。
そのようなルートで逃げたときに踏んでしまうバラの数の上限を答えよ。
マップは大きさN(奇数)の正方形で、上下左右にのみ動く事ができる。

例）
マップの大きさ:3
マップ(.:土、R:バラ、P:自分がいる場所:

...
RP.
...

この場合の回答は1となる。

変数の条件)
1<=N<=21

回答）
メモ化探索問題ですね。

ぼけーっと中央線で座っていたら代々木あたりで乗り込んで来た女の子二人組に両脇を固められ、俺越しに会話のキャッチボールを始められてしまった。おろおろおろ。

x軸が経過分数、y軸が得られるポイント。
式はここの「12 Determining Score」から。
Competing in a Rated Algorithm Competition

500ptは20pt間隔、1000ptは50pt間隔位が丁度良いです。
pt
pt間隔(刻み幅)

y = 250 * (0.3 + (0.7 * 75 * 75) / (10 * x * x + 75 * 75))