更新弱化中とその原因そしてその解決策

さて，今月のブログエントリ数が約1年振りに1桁となりましたが，その原因は一体何かと言いますと，即ち卒業研究なわけです．

高専では，最高学年である5年において，丸々1年間を使い指導教員の下卒業研究に取り組みます(多分)．昨年は，色々と手を出し過ぎた事に加え，長期間に渡り体調を崩してしまったため，随分と遅れを取ってしまった事を記憶しています．現在は，どうにか最終発表を無事に終え，あとは卒業論文と学会発表が控えているというわけです．卒業論文と学会の要旨原稿の締切がこれまた，2/10と非常に迫っており，そのため暫くの間ブログの更新は無理そうです．つまるところ，2/10以降には，少しく時間が出来るというわけです．

ちなみに，私が取り組んでいるテーマをひとことで言うと，「家庭用ロボットの効率的な振舞を強化学習によって獲得する」です．

多くの家庭用ロボットにはヒューリスティクスが組み込まれており，それに従って掃除を行っています(ちなみに，業務用掃除ロボットは，高精度センサ使用可能+室内形状が既知という条件から，経路計画さえ済んでしまえば，その経路をロボットがたどるだけで終わります)．そのため結構効率が悪いです．というわけで，効率向上を目的としてロボットに振舞を学習させるわけです，自動で．実環境への適用は滅茶苦茶難しいので，現時点では，実環境を模擬したシミュレーション上での実験を行っています．ある程度の制約はつきますが，それでもいくらかは効率化可能なようです．

余談ですが，競技プログラミングに関わっていたお陰か，随分とシミューレションの高速化が出来ました．どこが一番時間を食っていてどこをどう変えれば高速化するか，というのが直感的に分かるわけです．最終的には，最初のプログラムに比べ100倍近く高速化出来ました．

2011年の目標

というわけで今年の目標を制定します(途中で変更するかも)．

■プログラミング関係
・ICPC
国内予選10位以内
アジア地区予選10位以内
・Aizu Online Judge
10位以内(Solved)
・TopCoder
YellowCoder(1500以上)
・Project Euler
Level 5
・コンパイラ制作
何か一つ，自分専用言語を作ってみたいですね．

達成出来そうで出来なかった目標達です．

■その他
・体調管理
昨年は，半年近くに渡って体調を崩してしまい，多くの方に迷惑をかけてしまいました．
今年は，限度を超えて無理をすることが無いようにスケジュールを組んでいきたいと思います．
・筋トレ
上の達成に貢献できそうなものとして．
・専門書消化
昨年と同様，まだまだ読み終えていない本が沢山有ります．

あまり多過ぎると手付かずのまま時間だけが過ぎ去ってしまうので，この位に止めておきましょう．

2010の目標の達成状況

さて，2010年もあっという間に終わってしまい，2011年に突入しました．昨年を振り返るため，2010年の目標の達成状況を考察してみます．

http://mainly-coding.blogspot.com/2010/01/blog-post.html
↑これ．

■プログラミング関係
・TopCoderでYellowCoderになる
Maxで1463まで行った(+37pでYellow)のですが駄目でした…．
・Project EulerでLevel4になる
この目標を書いた時点で31問，12月入った時点で100問程度でしたが，怒涛の勢いで問題を解いていき，ぎりぎりLevel 4(150問)に到達しました．
・PKU Judge Online，anarchy golfへの参加
anarchy golfは幾つか参加し，POJは現在88問です．むしろAOJへの参加の方が多いでしょう．
・新しい言語を一つ以上習得する
Prolog(論理プログラミング言語)を始めました．習得は出来ていませんが，今も尚，勉強は続けています．

■その他
・溜まった専門書の消化
何冊か読みましたが，それ以上に買った冊数が多い気がします．
・数学，物理，英語の勉強(編入試験勉強を兼ねて)
数学はそこそこ復習しましたが，他は…．
・趣味の充実
ICPCへの参加により充実度やモチベーションが非常に高くなったと思います．

多くの目標は達成できたとは言えませんが，目標が全く無いよりはモチベーションが高くなりますし，また達成感という物が生まれると思います．

後日，今年の目標を書こうと思います．

Project Euler

■088
長さnの数列(a_k)を作る．
但し，任意のkについて，
2≦a_k<a_k+1
この時，
Σ=Σ_k a_k
Π=Π_k a_k
と置き，
1+…+1+Σ=1*…*1*Π
が成り立つとすれば，1の個数mは
m=Π-Σ
となる．
よって，総和(総積)がΠであり長さがn+mの数列が出来たことになる．
Σ,Πは再帰で生成するが，再帰回数nは12000程度で十分である(と思う，それ以上の長さを生成しても意味が無いから)．
min[len]=条件を満たす長さlenの数列の総和(総積)の最小値
として，minを更新していく．

■098
それぞれの文字列をASCIIでソート．ソートした後の文字列群で等しいものがアナグラム対となる．アナグラム対(s, t)に対して，桁数がsの長さである自乗数を全て生成する．sとある自乗数mを対応させ，アルファベット->数字のマッピングを作る．条件を満たさない(違うアルファベットに同じ数字が割り当てられる等)マッピングになるときはそこで終了する．マッピングを用いてtに対応する数値nを生成．nが自乗数ならすべての条件を満たしたことになる．
これらを満たすもののうち，最大のものを見つければ良い．

■151
[仕事の回数][A1の枚数][A2の枚数][A3の枚数][A4の枚数][A5の枚数]=その組み合わせが起こる確率
でDP．
考えられる組み合わせ全てについて，
dp[k][b1][b2][b3][b4][b5]+=dp[k-1][a1][a2][a3][a4][a5]*ak/(a1+a2+a3+a4+a5)
で更新．akを引いたとし，その後のそれぞれの紙の枚数をb1,b2,b3,b4,b5とする．
例えば，a3を引いたとしたら，
b1=a1
b2=a2
b3=a3-1
b4=a4+1
b5=a5+1
となる．

これで，ついに150問に到達し，Level 4となりました．

Project Euler

■110
x=n+k
と置くと，
y=n²/k+n
となる．kはn²を割り切る必要があるため，重複を含めてn²の約数の数だけ解があることが分かる．
n=2^r₁3^r₂5^r₃…
のように素因数分解出来たとき，n²の約数の数cは，
c=(2r₁+1)(2r₂+1)(2r₃+1)…
となる．
cが8000000(重複しているので2倍)を超えるような最小のnを探索で見つける．

■135
x=a+2d,y=a+d,z=a
と置くと，
(-a+3d)(a+d)=n
となり，
n=pq
とすれば，
d=(p+q)/4
a=(-p+3q)/4
となる．nについて，a,dがそれぞれ自然数となるような(p,q)の個数が解の個数となる．

■136
135を流用．非常に時間がかかった．

■139
a<b<cとすると，小正方形の面積は，
c²-2ab=(a-b)²
なので，小正方形の辺の長さmは，
m=(b-a)
つまり(b-a)|cであるものを数えれば良い．
ピタゴラス数生成行列で探索するだけ．

Project Euler

■086
3辺をx<y<zとすると，
最短距離は
√[(x+y)²+z²]
となる．
a<b<cであるピタゴラス数
a²+b²=c²
と対比させると，
a=x+y, b=z, c=最短距離
または，
a=z, b=x+y, c=最短距離
と書ける．
ピタゴラス数(a, b, c)を適当に生成した時，前者・後者の組み合わせ数をそれぞれ以下のようになる．
・前者
1辺の最長はbで，b≦Mの時，x/2個．
・後者
1辺の最長はaで，a≦Mの時，max{(2x-y+2)/2, 0}個．

■131
実験的解法になってしまったので省略．

Project Euler

■215
可能なレンガの組み合わせをDFSか何かで予め求めbitで表現しておく．
|---|--|--|--|
ならば，000100100100とする(端は含まない)．
[段数][組み合わせの番号]でDP．
i番目の組み合わせとj番目の組み合わせとが伝播亀裂していないならば，
dp[k][j]+=dp[k-1][i]
i番目の組み合わせのbit表現をbits[i]とすると，上の条件式は，
if((bits[i]&bits[j])==0)
と書ける．
intで処理しようとしたため，オーバーフローしていた事に気が付かなかった．

■178
[桁数][0~9のどれが出現したか][一番最下桁]でbitDP．
dp[0][1<<i][i]=1
を初期条件とし，以下の式で更新．
dp[k][j|(1<<(i-1))][i-1]+=dp[k-1][j][i]
dp[k][j|(1<<(i+1))][i+1]+=dp[k-1][j][i]

■190
ラグランジュの未定乗数法を使う．
f=Π_k x_k^k
g=Σ_k x_k-m=0
δ/δx_k (f-λg)=0
δ/δλ (f-λg)=0
結果，
x_k=2k/(m+1)
となる．あとは計算するだけ．

■207
数式を適当に弄ると，
2^t=[1+√(1+4k)]/2
となる．ここで，1+4kは奇数であるため，1+4kが平方数となるならば，
1+4k=(2a+1)²
と書くことができ，これを解くと，
2^t=a+1
k=a²+a
となる(a≧1)．
となる．
a+1が2のベキ乗である時，完全な分割となるため，aを決定したとき，完全な分割であるものの割合は，
log₂(a+1)/a²+a
となる．

■197
恐らく収束するだろうと見込みのもと適当なnまで値を見たところ，周期2の周期解に収束していた．よって，n=10¹²まで計算する必要はなく，適当なところで打ち切れば正確な答えが出る．

■159
dp[i]=iのMDRS
a[i]=iのDR
とすれば，
dp[n]=max{a[i]+dp[n/i]}
となる(iはnの約数)．
但し，
a[1]=0
dp[1]=0
としておく．

Project Euler

■094
疑正三角形は，(a,a,a+1)又は(a,a+1,a+1)となる．
前者の面積は，
S=(a+1)/4√[(a-1)(3a+1)]
後者については，
S=a/4√[(a+2)(3a+2)]
となるので，根号の中身が平方数になるものを逐一数えていけば良い．

■095
真の約数の和を事前に求めておく．ある数aについて約数の和を再帰的に求めていき循環するかどうかを調べる．

■231
20000000までの素数を列挙しておけば，素因数分解(O(√n))を(おそらく)高速化できる．
150000001~20000000までの数の素因数の出現頻度から，1~50000000までの数の素因数の出現頻度を引き，和を計算する．

■235
s(5000)が容易に発散してしまうため，事前に範囲を狭めておいてから二分探索．doubleでも十分計算可能．閉じた式は使う必要無し．

■265
ビット演算を少し使って，DFSするだけ．