2015-06-20

D進ゲームにおける戦略

イントロダクション

D進ゲームとは、 Thisnor氏による D進，それは苦しいという博士課程シミュレーションゲームのことである。このゲームは4つのコマンドをベースに博士学生を育て、D論提出を目標にするゲームである。
本記事では6/19終わり時点における、とりあえずクリアするためにとるべき戦略と、クリア後に他プレイヤー（博士）と戦うことができる「学会発表」でよい成績をとるための戦略を紹介する。
また、その成果として現在のプレイヤーのレベルを紹介し、最後にまとめと感想を述べる。

したがって、この記事にはある種のネタバレを含むので注意されたい。

2015-06-11

Fekete's lemma

一つ前の記事と似てるような似てないような、なので書いておく

$x$ を数列とする。任意の $k,l \geq 1$ に対して
$x_{k+l} \geq x_k + x_l$ (優加法性) を満たすならば、
$\lim_{k \to \infty} x_k / k = \sup_{k} x_k / k$ を満たす

直感的には、とりあえず $x_k / k$ が(どこかから)非減少列であることを示せてしまえればよさそうに見える。
しかし、この方針では厳しい。たとえば、
$x = (1,2,11,12,21,22,...)$ のように $x_{2a+1} = 10a+1, x_{2a+2} = 10a+2$ ととれば優加法性を満たし、かつ
$a$ を大きくとることによって $x_{2a+1}/(2a+1)>x_{2a+2}/(2a+2)$ となる。

ということで、別の方針で示す必要がある。証明はCombinatorial Optimization (Schrijver)の2章の証明に説明を少し追加したものである。

$i,j,k \geq 1$ とする
優加法性から $x_{jk+i} \geq j x_k + x_i$
$i,k$ を固定して
$\liminf_{j \to \infty} x_{jk+i}/(jk+i) \geq \liminf_{j \to \infty} \frac{jx_k + x_i}{jk+i}$
$= \liminf_{j \to \infty} \frac{x_k}{k} \frac{jk}{jk+i} + \frac{x_i}{jk+i}$
$= \frac{x_k}{k}$
最後の式はlimを飛ばして(無限大にもなりうるが)収束するのでliminfでも大丈夫。
また、この変形の最後で $i$ を含まなかったので次のようにできる
$\liminf_{n \to \infty} \frac{x_n}{n} = \inf_i \liminf_{j \to \infty} \frac{x_{jk+i}}{jk+i} \geq \frac{x_k}{k}$
よって、
$\liminf_{n \to \infty} \frac{x_n}{n} \geq \sup_k \frac{x_k}{k}$ とできる。

liminfとlimsupの定義から、
$\liminf_{n \to \infty} \frac{x_n}{n} \leq \limsup_{n \to \infty} \frac{x_n}{n} \leq \sup_n \frac{x_n}{n}$ なので、先ほどの式とあわせることで、これらには等式が成り立つことがわかる。

結局、liminfとlimsupが一致したので、limが存在することがわかり、 $\lim_{n \to \infty} \frac{x_n}{n} = \sup_n \frac{x_n}{n}$

2015-03-30

1:2:1

1:2:1といえば ->

(x+1)^2の係数
パスカルの三角形3段目
競プロでは ... Air Pollution | Aizu Online Judge

という感じですが次の性質が成り立つんですね

$A_0 = 0,\\ 2 A_i \geq A_{i-1} + A_{i+1} (i \geq 1)$
ならば $i\geq 1$ に対して $\frac{A_i}{i}$ は非増加列である．
言い換えると $i\geq 1$ に対して $\frac{A_i}{i} \geq \frac{A_{i+1}}{i+1}$ が成立する．

証)
数学的帰納法による．
要素数が2以下の場合，つまり $\frac{A_1}{1}, \frac{A_2}{2}$ のみの時は $2A_1 \geq A_0 + A_2$ より非増加列．
$\frac{A_1}{1} ,\dots, \frac{A_n}{n}$ の数列が非増加だったとする．
このとき $2A_n \geq A_{n-1} + A_{n+1} \geq \frac{n-1}{n} A_{n} + A_{n+1}$ より
$\frac{A_n}{n} \geq \frac{A_{n+1}}{n+1}$ を得るため証明終わり．

この性質が何だという話ですが、これは劣モジュラ性について扱っている本を眺めていて副次的に出てきたものです。

劣モジュラ性とは，（素人なので嘘書いてる可能性がありますが）
要素数 $n$ の有限集合 $S$ の冪集合 $2^S$ 上の分配束（集合の和積で閉じている）であるような部分集合 $\mathcal{D}$ をとる．
この $\mathcal{D}$ から実数への写像 $f$ が劣モジュラであるとは $\forall A, B \in \mathcal{D}$ に対して $f(A)+f(B) \geq f(A \cap B) + f(A \cup B)$ を満たすことである．また通常 $f(\phi) = 0$ としておく．

さらに劣モジュラ多面体というものを考えます。

まず， $x \in \mathbb{R}^S$ とする．この $x$ を拡張して $\forall A \in \mathcal{D}, y(A) = \sum_{a \in A} x(a)$ とする．
この時， $\mathcal{D},$ 劣モジュラ $f$ による劣モジュラ多面体とは $\forall A, \in \mathcal{D}, y(A) \leq f(A)$ となるような $x$ の集合のことである．

定理: 劣モジュラ多面体では $y(S)= f(S)$ を満たす $x$ が必ず存在する（証明略）．

(ここからは $\mathcal{D}=2^S$ とする．)
先ほどの定理は大雑把な書き方をすると $A \neq S, y(A) \leq f(A)$ なる複数の平面で切った後に $y(S) \leq f(S)$ でまだ切れる余地がある（もしくは接する,かする）ことを意味している。（しかしすぐに証明できる気がしないし本当にそんなうまいこといってるのか？と思うわけなので具体的なことを考えていこうという方向です。）

さて、この定理が成り立つということは、例えば $s_1,\dots,s_n \in S$ として $y({s_1}) \leq f({s_1}), y({s_2}) \leq f({s_2}), \dots y({s_n}) \leq f({s_n})$ を満たす多面体 $P$ に対して $\max_{x \in P}\sum y({s_i}) \geq f(S)$ が成り立つはずである。
ということは、 $\sum f({s_i}) \geq f(S)$ が成立するはずである。
さらに言えば、 $y({s_i})$ を $y({s_i, \dots , s_{i+j-1}})$ として巡回的な制約を満たす多面体 $P_j$ に関しても同様なことが成り立ち、
$\sum f({s_i, \dots, s_{i+j-1}}) / j \geq f(S)$ が成り立つはずである。(なお、 $m \geq 0, s_{n+m} = s_{m}$ としておく)

ここで数列 $A$ を $A_j = \sum_{i} f({s_{i}, \dots s_{i+j-1}}) , A_0 = 0, A_n = n f(S)$ とすれば劣モジュラ性の式を足しこむことによって冒頭の1:2:1な式が出てくるという話なのでした（背景説明が長い）。

そんで、ここで冒頭の性質が成り立つので、さっき出てきた式を $\sum f({s_i, \dots s_{i+j-1}}) / j = \frac{A_j}{j} \geq \frac{A_n}{n} = f(S)$ という風に示せるのでなるほど確かに定理は納得できる気もしてくるなぁ、と思ったのでした。

2014-09-15

D問題(速報)

・なにこれ ->
D: 夕食 - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder

・解法の一例

自炊定数を $P$ として初期自炊力（自炊のうまさ）をQとしておく。
日数は0-indexedとしておく。
$j$ 日目の食堂幸福度を $C_j$ としておく。
さて、 $K$ 個食堂から選ぶこととする。
このとき自炊幸福度を(足す分だけ)考えると $(N-K)*(N-K-1)/2 + Q(N-K)$ とできる。
$a_i$ 日目( $0 \leq i \leq K-1$ )に食堂にいったとして
$a_i$ 日目の幸福度は,
先ほどの自炊幸福度で差し引かなかった食堂に行ったことから来る幸福度の損失を含めて考えることで、
$a_i$ 日目の時にできる幸福度は $(N-K-(a_i-i))*(-1)*P + C_{a_i}$ と解釈できる。
(それまでに $a_i-i$ 回自炊をした。つまり、これ以降で自炊は $N-K-(a_i-i)$ 回行うので,先程足した分から引く必要がある。

この評価で計算してみると
$PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} + \sum_{i=0}^{K-1} -P(N-K-a_i+i)+C_{a_i}$

Sumの外に出せるものを出すと
$PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} - P\frac{K(K-1)}{2} -PK(N-K) + \sum_{i=0}^{K-1} P a_i +C_{a_i}$

$= PQ(N-K) + P(N-K)(N-K-1) - P\frac{N(N-1)}{2} + \sum_{i=0}^{K-1} P a_i + C_{a_i}$

(最後の変形は別解から考えると出てくる式なのでイコールで結んでおいた。以後の議論では必要ない変形)となる。
足し算の中身が $a_i$ のみに依存している形になるので、これの最大値は
$b_i = Pi + C_i$ を定義してこれの大きい方から $K$ 個選択すれば良い。
しかも $K$ にも依存しないので $b_i$ を始めに定義しておいて、 $K$ の値を0から順番に試していき最大値を出せば良い。　
したがってネックはソートのみ。時間計算量 $O(N log N)$ でできる

2014-05-10

2048をやるときに考えること

マス目の番号は
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
とする。

安置場所
- 自分の場合は上になるほど大きく、右上の隅に一番大きいセルを置く
- つまり4の場所に2048をおいたりしている
基本戦略
- 隅に寄せる
  - いろんな所で言われてること
- 大きな数字を下に作り残さないようにする
  - すぐにマージしないテクニックでその後を優位に進める
    - 例えば5の場所に16,9の場所に16, 10の場所に32,11の場所に16, 12の場所に8,13の場所に2があったとする
    - このときすぐに上を押したくなるけど, そうすると9の場所に2が入ってしまってその後そこに32をつくらないといけなくてこの場合だとかなり死にそう
    - そこで一旦右に動かして2をどかして(新しく入るのを考えると確率2/3ですが死ぬよりはまし)から上を押してほぼ連続で16, 32をマージする
  - 個人的な印象だけど最下段の8はできるだけ取り除くように注意する
    - 8が最下段真ん中で浮くと非常に辛くなる
大事な数字を固定する
- 大事な数字が隅から動いてしまったときに隅に新しい数字が生成されると一気につらくなる
- これを阻止するため、固定状態を保つ
- そのテクニック
  - 最上段へのマージの際にはできた後にすべての数字が異なるようにするのがベスト
  - 例えば32 64 128 512 ができていたら2段目以下で128を作るなど
- 固定されていないとき
  - 大きな数字を作った直後はやはり非固定の状態になりやすい
  - 運頼みではあるができる限り粘る
    - 余裕手があればそれを保つ
    - 単に右マージする前に上をできる限り打つとか

一方向しか動かせない事態の阻止
- 割とよく発生する事象
  - 1/5の確率で入って綺麗に完成、という感じ
  - これで詰むパターンが多い
- 避けるために
  - 一手読みで対処
  - プレイ中は気持ちのいい同時マージの時の罠に気をつけるようにする
  - 下二段でごにょごにょするときに最下段にできるだけ一つは数字マスがあるように気をつけている

2013-01-23

なにかのもんだい

（略解ですが省きまくってる（というか雑）ので頑張って補完するかリプ飛ばしてください）

方針としては、一点を(x,y)に固定して、そのとき、もう一点をどこに置くかを考えます。
もう一点おける候補の場所の面積は1で、条件を満たす置き方の領域ををf(x,y)とします。
結局f(x,y)が平均どのくらいとれてるかをみればよいので、x,yで重積分してやれば良いという事になります。
ただ、f(x,y)をひとつの式で表すのが難しいので多少の工夫を加えます。
1つ目の工夫は最初に一点固定する領域を限定すること
2つ目は縦方向に交わるような点集合と横方向に交わる点集合を別々に計算してやること、です

1つ目の工夫ではタテ・ヨコ・ナナメに線を引いて正方形を8つの部分にわけると楽だと思います。

残りは立式をしてwolfram alpha先生に計算させた結果です

(途中で途切れてるけどコピペしてぶちこんでください)

http://www.wolframalpha.com/input/?i=Integral_0^%281%2F2%29+%28+Integral_0^x++++%28y%2F%281-x%29*x+%2By%2Fx*%281-x%29%29%2F2++dy+++%29+dx

www.wolframalpha.com/input/?i=Integral_0^(1%2F2)+(+Integral_(1-x)^1++++(y-1%2B1%2F(2y))++dy+++)+dx

以上の２つを足して8をかければ2/3になってこれが答え。

数値計算しても0.6666...くらいが出てきます

この問題作ったときは充分大丈夫そうな問題だと思っていたけど、
今見ると無限の元から1つの元を取り出す操作が大変怪しく感じますがどうなんでしょう。
まぁロープ切断問題も無限個から複数の点とってるしいいのかなぁ

2012-07-27

■

京大の試験で出たらしい問題
$\lim_{x \to \infty} \int_{t=0}^{\infty} \frac{cos(xt)}{1+t^2}dt =0$ をしめす
あってるか謎い概略

$x=y \pi$
$(0\leq k < \frac{2}{y} )$
$g(k) = \sum_{i=0}^{\infty } \frac{ cos((\frac{2i}{y})+k)y \pi )}{ 1 + ( \frac{2i}{y}+k )^{2} }$
$= cos(ky\pi) \sum_{i=0}^{\infty} \frac{ 1}{ 1 + ( \frac{2i}{y}+k )^{2} }$
$A(k) = \sum_{i=0}^{\infty} \frac{ 1}{ 1 + ( \frac{2i}{y}+k )^{2}$
$\sum_{i=1}^{\infty} \frac{ 1}{1+(\frac{2i}{y})^{2}} \leq A(k) \leq \sum_{i=0}^{\infty} \frac{ 1}{1+( \frac{2i}{y})^{2}}$
$-1 \leq A(k)-A(k+\frac{1}{y}) \leq 1$