picojson valijson
gist964c105f11c61b9792e381beac94b3b1
int64関連のリンクエラーがでたらマクロつければおｋ
visualstudioはデフォルトでdll付けようとするからプロジェクトのプロパティでちゃんと設定してね。
64bitなのはx64だからboostのビルドは気を付けてね。プロジェクトのアーキテクチャとライブラリのアドレスモデルを合わせような
Boost_資料
メモ
○コンパイル Visual Studio 2017 RC
project-config.jam
import option ;
using msvc : 14.0 : "C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.10.24911\bin\HostX64\x64\cl.exe" ;
option.set keep-going : false ;
Configuration
公式では
using msvc : : "Z:/Programs/Microsoft Visual Studio/vc98/bin/cl" ;
という風にversionを空白で書いてあるけど、だめです
これで3時間費やした。
開発者プロンプトで
b2 toolset=msvc-14.0 threading=multi variant=debug,release link=shared runtime-link=static address-model=64 --stagedir=stage/x64 -j 8 --with-regex
-
- with-name
で特定のライブラリだけコンパイルできる。
〇構文解析系
c++ - boost::spirit access position iterator from semantic actions - Stack Overflow
spiritで文法単位を読むごとに位置情報を保存する
https://github.com/yutopp/rill/blob/304d385d6c0d22a083fe7c35d1d6a23edf29bf30/rill/syntax_analysis/code_grammar.hpp
コンマ演算子と関数の区切りをどうわけてるか。argument_listの内側にはcomma_expressionよりも結合の強いassign_expressionがあることに注意。
AtCoder 射撃王 考察と証明っぽいもの
abc023.contest.atcoder.jp
AtCoder Beginner Contest 023 解説
ABC23回のD問題とその解説より引用
問題文
高橋君は最近、射撃にハマっている。高橋君は N 個の風船すべてを射撃で割り、得られる得点をできるだけ小さくする競技に参加している。
風船には 1 から N までの番号が付けられていて、風船 i(1≦i≦N) は競技開始時に高度 Hi のところにあり、1 秒経過するにつれて高度が Si だけ増加する。
高橋君は競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。どの順番で風船を割るのかは高橋君が自由に決定できる。
どの風船についても、その風船を割ることによるペナルティが発生する。ペナルティはその風船が割られたときの高度と等しい整数値となる。高橋君が最終的に得る得点は N 個の風船のペナルティのうちの最大値となる。
高橋君が得ることのできる得点として考えられる最小値を求めよ。
Opt > X ならばどうやっても達成できない
Opt <= X ならば貪欲法で達成できる
本当にそうか？
なにが疑問か、というと、
貪欲法で得たペナルティの最小値が、本当に全ケースの最小値なの？<=>（同値） ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
ようするに
この問題の解法は、↓を前提にしてるんですよ
でも↓のようになってた場合、この解法じゃ正しい解にならなくね？ってこと
というわけで、一枚目の画像のようになっていることの説明を必死こいて考えました
定義:
風船の集合 B (要素数はnとする)
その打った順番 τB
k番目に打った風船 (τB)k*1
k番目に打つはずの風船を打たずにt-1秒立った時の高さ h( (τB)k,t)*2
補題1:
風船集合Bの全ケースを考慮したペナルティ最小値を取るような、ある打ち方τを考える。このk番目に割った風船が、他のどの風船よりも高いとこで割られてペナルティとなったとする。このとき
j < k番目の風船はk-1秒目の時点でk番目に割られた風船より高くなければならない。すなわち
j< k => h((τB)j,k) >= h((τB)k,k)
背理法で証明する
j
わった順番は前提より
(τB)1,(τB)2,(τB)3,...,(τB)j,...,(τB)k,...,(τB)n
その高さは
h((τB)1,1),h((τB)2,2),h((τB)3,3),...,h((τB)j,j),...,h((τB)k,k),...,h((τB)n,n)
前提よりh(k,k)が最も高いので,
h((τB)x,x) < h((τB)k,k) {x ≠ k} ... ①
ここで,割るのをjとkを入れ替えてみると
(τB)1,(τB)2,(τB)3,...,(τB)k,...,(τB)j,...,(τB)n
その高さは
h((τB)1,1),h((τB)2,2),h((τB)3,3),...,h((τB)k,j),...,h((τB)j,k),...,h((τB)n,n)
hの性質より
h((τB)k,j) < h((τB)k,k) {k< k}//より時間がたてばより高くなる// ... ②
また背理法の仮定より
h((τB)j,k) < h((τB)k,k) ... ③
①②③より、jとk入れ替えた打ち方をすると、どの風船も割られた高さがh((τB)k,k)をこえないため、ペナルティがh((τB)k,k)よりも小さくなってしまう。これはh((τB)k,k)が全ケースのペナルティ最小値ということに矛盾する。よって
j< k => h((τB)j,k) >= h((τB)k,k)
補題2:
補題１と同じ前提で
j > k番目の風船はk-1秒目の時点でk番目に割られた風船より低くなければならない。すなわち
j > k => h((τB)j,k) < h((τB)k,k)
当たり前。τは全ケース最小値となる打ち方の一つである。もし
j > k => h( (τB)j,k) >= h( (τB)k,k)
であるならば、k番目の風船を打った時の位置関係が
〇 h( (τB)j,k)//j番目にうつ予定
----〇--------------------------- h( (τB)k,k)//k番目にうった
となってしまう。前提よりτBのなかではh( (τB)k,k)が最大なのだからありえない。
本題
ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
新たな定義
T(τ,(τB)j) 風船の集合Bをτの順番で打つとき、ｊ番目の風船が、打ち方τの時のペナルティとなる高さを超えるまでの時間*3
P(τB) 風船集合Bをτの順番でうった時のペナルティ
Pmin(B) 風船集合Bの全ケースの中の最少のペナルティ
前提(補題と同じ)
風船集合Bの全ケースを考慮したペナルティ最小値を取るような、ある打ち方τを考える。このk番目に割った風船が、他のどの風船よりも高いところで割られてペナルティ = Pmin(B)となったとする。
このとき
(τB)1 から (τB)k-1 までの風船集合とその並びをτ1B1
(τB)k+1 から (τB)n までの風船集合とその並びをτ2B2
とする
k番目に割った風船がペナルティなので
h( (τB)x,x) < h( (τB)k,k) {1 <= x <= k-1}
h( (τB)x,x) < h( (τB)k,k) {k+1 <= x <= n}
よって,τ1B1のなかだけで競技をしたと仮定してペナルティを考えたとき,そのペナルティはh( (τB)k,k) = Pmin(B)を超えない。
すなわち P(τ1B1) < h( (τB)k,k) = Pmin(B)
またPmin,Pの定義より
Pmin(B1) < P(τ1B1)
ゆえにB1の風船集合の全ケースを考えたときの最小ペナルティ = Pmin(B1) < P(τ1B1) < h( (τB)k,k) = Pmin(B) をみたす
同様に Pmin(B2) < P(τ2B2) < h( (τB)k,k) = Pmin(B)
どういうことかというと、
風船の並びを
τB = τ1B1 + (τB)k + τ2B2
って分解したとして、τ1、τ2をそれぞれB1,B2を最少のペナルティで打つ打ち方τ1',τ2'にして
τ'B = τ1'B1 + (τB)k + τ2'B2
っておきかえても、τ'Bもまた全ケース最少のペナルティをとるやり方である
だってそうでしょ？
まずB1を、最もペナルティの少ないやり方で打つ。そのペナルティはh( (τB)k,k)をこえない
つぎに(τB)kをうつ。このペナルティはh( (τB)k,k)
そしてB2を最もペナルティの少ないやり方で打つ。そのペナルティはh( (τB)k,k)をこえない
よってこの打ち方のペナルティの最大値はh( (τB)k,k) = Pmin(B)
時間関係Tもみていく
j < k なら T(τ, (τB)j) < T(τ, (τB)k)
なぜなら補題１より
j< k => h( (τB)j,k) >= h( (τB)k,k) = ペナルティの高さ
j番目に割る風船は、（打たなければ）k番目の風船より先にペナルティの高さを超えるからである。つまりj番目の風船はk番目の風船よりも、ペナルティを超えるまで時間が短い
また
k < j なら T(τ, (τB)k) < T(τ,(τB)j)
なぜなら補題2より
j< k => h( (τB)j,k) <= h( (τB)k,k) = ペナルティの高さ
k-1秒時点でk番目に割る風船(τのペナルティとなる風船)、はj番目の風船より先にペナルティの到達しているはずである。補題２の図をみればわかる
この時間の関係式,jに関する部分をB1とB2に置き換えてやる
1 < j < k-1 => T(τ, (τ1B1)j) < T(τ, (τB)k)
1 < j < n-k => T(τ (τB)k) < T( (τ,(τ2B2)j)
そしてこれで証明は完了してしまったのだ！！！！！！
今までの証明を振り返ろう
たとえば、Bのある打ち方が、全ケース最小のペナルティをとるやり方τだとする。
τBについて考えてみよう、
ｋの前に割った風船の集合をB1,
kの後に割った風船の集合をB2とする
Pmin(B) = P(τB) = h( (τB)k,k)
B1,B2の中だけで最少のペナルティとなるようなうち方τ1',τ2'にいれかえる
(Pmin(B1) = P(τ1'B1),Pmin(B2) = P(τ2'B2))
τ'B = τ1'B1 + (τB)k + τ2'B2
このとき、いつまでに割るかという制限時間は短い順に
B1,(τ'B)k,B2
また、
τ' は依然として全ケース最小のペナルティをとる打ち方です
τ1'B1について考えてみよう
そのτ1'のペナルティとなるk'番目に割った風船について、
k'の前に割った風船の集合をB11,
k'の後に割った風船の集合をB22とする
Pmin(B1) = P(τ1'B1) = h( (τ1'B1)k',k')
B11,B21の中だけで最少のペナルティとなるようなうち方τ1'1',τ2'2'にいれかえる(Pmin(B11) = P(τ1'1'B11),Pmin(B22) = P(τ2'2'B22))
τ1''B1 = τ1'1'B11 + (τ1'B1)k' + τ2'2'B22
このとき、いつまでに割るかという制限時間は短い順に
B11,(τ1''B1)k',B22
いままでのとあわせて
いつまでに割るかという制限時間は短い順に
B11,(τ1''B1)k',B22,(τB)k,B2
またτ'Bの右辺のτ1'B1を置き換えて
τ''B = (τ1'1'B11 + (τ1'B1)k' + τ2'2'B22) + (τB)k + τ2'B2
τ'' は依然として全ケース最小のペナルティをとる打ち方です
τ1'1'B11について考えてみよう
...
千年後
おおっと、B1,k,B2がどんどん分割されて
いつまでに割るかという制限時間は短い順に
b1,b1,b3,...,bn
(bk は風船一個を表す)
みたいにあらわせたぞ
つまりこの並びをτfとすると
τfは制限時間の短い順の貪欲法でとった並び
で、上の再帰をみると、τ',τ'',....,そしてやはりτfも
τf は依然として全ケース最小のペナルティをとる打ち方です
がなりたつ。
よって、
ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
します。τfがまさにそれです。
やったぜ。
風船集合Bが空の時とか厳密じゃないけどまあいいでしょ。
Haskell & Vim 導入 Windows
わけわかんなくてもとりあえずうごけばいい人向け
Haskell やってみたくなった。
C++しか触ったことなくて、今までVisualStudioで事足りてたけど、Haskellの環境はこれを機会にVimでやってみようとおもいました。
いろいろ探して導入に一日使ったのでメモ。
Windowsはめんどくさいらしい（Linuxつかえよ）
※自分は以下に書いている作業をほとんど理解してません。ネットにあるものをのせてるだけです
目標
VimでHaskellのコードを書く。（コード補完機能付き）
1.Haskell ダウンロード
ググったらStackとか使うのもあるらしいけど,めんどいから公式のHaskell PlatForm入れましょwww.haskell.org
cabal update
した後
cabal install ghc-mod
2.Vimダウンロードylgbk.hatenablog.com
↑の通りに。
途中gitのダウンロード中インスコトーラで３回ほど選択が出るけど頑張って英語読んで。
3.プラグイン
2でNeoBundleをインストールしてるはず
あとは必要なプラグインを入れる
vimprocってプラグインはめんどくさいwww.jonki.net
これの下のほう,
2012/12/13版からvimprocのdllがgVimに同梱されています。よくWin環境でのセットアップ記事見ると自分で作っている記事が引っかかりますが、この配布前の記事のようです。結構ハマりどころだったので助かりました。
gVimのzipファイルの中にwin64のvimprocのDLLがあるのでneobundleのvimproc.vim/autoloat/以下にコピーしましょう。これで動くようになるはず。
gVim\plugins\vimproc\autoload\vimproc_win64.dll // 同梱されているDLL
＄HOME\.vim\bundle\vimproc.vim\autoload // ここにコピーする
HOMEっておそらくユーザーの名前のディレクトリ。
あとは普通にプラグイン入れる。
めんどくさいからググって
最終的に_vimrcファイルはこうなった
" vim起動時のみruntimepathにneobundle.vimを追加
if has('vim_starting')
set nocompatible
set runtimepath+=~/.vim/bundle/neobundle.vim
endif" neobundle.vimの初期化
" NeoBundleを更新するための設定
call neobundle#begin(expand('~/.vim/bundle'))
NeoBundleFetch 'Shougo/neobundle.vim'
" 読み込むプラグインを記載
NeoBundle 'Shougo/vimproc.vim', {
\ 'build' : {
\ 'windows' : 'tools\\update-dll-mingw',
\ 'cygwin' : 'make -f make_cygwin.mak',
\ 'mac' : 'make -f make_mac.mak',
\ 'linux' : 'make',
\ 'unix' : 'gmake',
\ },
\ }
NeoBundle 'Shougo/unite.vim'
NeoBundle 'itchyny/lightline.vim'
NeoBundle 'kana/vim-filetype-haskell'
NeoBundle 'dag/vim2hs'
NeoBundle 'thinca/vim-quickrun'
let g:quickrun_config={'_': {'split': ''}}
NeoBundle 'Shougo/neocomplcache'
let g:neocomplcache_enable_at_startup = 1
NeoBundle 'ujihisa/neco-ghc'
call neobundle#end()" 読み込んだプラグインも含め、ファイルタイプの検出、ファイルタイプ別プラグイン/インデントを有効化する
filetype plugin indent on" インストールのチェック
NeoBundleCheck
↓コード補完
↓クイック実行
やったぜ
参考url
Windowsでgvimを使う(neobundleのインストール) - .logbook
【Vim】gVimでneobundle環境を整える - The jonki
VimでHaskellを書く時に入れておきたいプラグイン5つ - Qiita
Installing "ghc-mod"
N分ヒープの要素Xの左の子がN(X-1)+2になる
N分ヒープを1から始まる配列の番号にわりあてたとき、
番号x の左の子は 番号 N(x-1)+2
ってのを示すメモ
根から深度を1,2,...ｄて数えるとする
深度dの右端の番号は,深度dには N^(d-1)個 の要素があるので、等比の和で
R(d) = (N^d-1)/(N-1)
深度dの左端の番号は,深度d-1の右端の番号+1 なので
L(d) = R(d-1)+1
= (N^(d-1)-1)/(N-1) + 1
要素xが深度dにあるとする
要素xの左にある深度dのノードは、x - L(d) 個 ある
要素xのもつ一番左の子の左側には,深度d+1のノードが N*(x - L(d)) 個 ある （N分だから。）
よってxのもつ一番左の子の番号は
(深度d+1の一番左端の要素の番号) + (xのもつ一番左の子の左側にあるノードの数)
ℓ(x) = L(d+1) + N*(x-L(d))
= (N^d - 1)/(N-1) +1 + Nx - N(N^(d-1)-1)/(N-1) - N
= N(x-1)+2
余談: 番号ｘのある深度の求め方
xの深度がdにあるとする
R(d),L(d) は上の方で書いたのとおなじ
(N^(d-1)-1)/(N-1) < x <= (N^d-1)/(N-1)
N^(d-1) < x(N-1) + 1 <= N^d (↑の全辺にN-1をかけてから１をたす)
1/N < (x(N-1)+1)/N^d <= 1 (↑の全辺をN^dでわる)
(x(N-1)+1) <= N^d < N(x(N-1)+1) (↑の全辺の逆数を取ったあと(x(N-1)+1)をかける)
ここで、全辺のをとる
ここで
とすると
符号をかえて
ここで、整数 a と 実数 b において
がなりたつので
番号ｘのある深度は
Siv3dとboost 超覚書
ものすごい詰まったのでメモ
boostのパスの通し方(ver1_58を例にしている)
インクルード boost_1_58_
バイナリ boost_1_58_/stage/lib
エラー対処
LINKエラー: libboost_context-vc120-mt-sgd-1_58.lib が開けない
LINKエラー: libboost_context-vc120-mt-s-1_58.lib が開けない
参考
VisualStudio2010でboostをビルドする - 結果だけでなく過程も見てください
bjam.exe toolset=msvc variant=release link=static runtime-link=static or shared
boostをビルドするとき,うえのコマンドを実行しないといけないときがある。
variant=debug で実行すると, boost_1_58_/stage にlibboost...mt-...gd-1-58とついたものができる
variant=release で実行すると, boost_1_58_/stage にlibboost...mt-...-1-58とついた.libができる
runtime-link=static,shared を変えて実行すると, mt-s- や mt-sgd- とついた.libができる（どっちがsのつくファイルを作るかは忘れた。）
warning LNK4098: defaultlib 'libcmtd.lib' conflicts with use of other libs; use /NODEFAULTLIB:library
warning LNK4098: defaultlib 'LIBCMT' conflicts with use of other libs; use /NODEFAULTLIB:library
siv3dのプロジェクトのプロパティを見る。プロパティ->C/C++->コード生成->ランタイムライブラリ
siv3dはデフォルトでデバッグ,リリースともに /MT
その関係だと思うけど,デバッグでビルドしようとすると上のようなエラーが出た。
プロパティウィンドウ左上の「構成」をデバッグにして
プロパティ->リンカー->依存関係追加(一番上の項目) に
libcmtd.lib
を追加
(同ページ)->無視するデフォルトライブラリ(上から三番目の項目) に
libcmt.lib を追加
とりあえずこれで動いたけど、勝手にいじったからsiv3dで変な挙動をするかもしれないけど、知らん。
シェーダアート_3 物体の複製
wgld.org | GLSL: オブジェクトの複製 repetition |
wgldさんの ＞フラグメントシェーダのコード を見ていく
物体の複製
43,18~20,14~16 行目
前回からの変更点はここしかなく、これが今回重要なところだ。
物体を複製したい。具体的には下のように
球を等間隔に配置しよう。distanceFunc は、（一番近い）物体と光の先端の最短距離を出す。物体が複数ある場合、どの物体との距離が一番近いかを計算しなければならない。
球の配置の仕方を、図のように、「立方体の中心に球」があるとして、その立方体を等間隔に置くようにすると考える。光の先端が、ある立方体の内側にあるとき、光の先端と最も近い球は、その立方体が囲んでいる球だ。これは、立方体と球との位置関係が対照的だから言える。立方体と非対称的な物体（たとえば、三角錐）を考えた場合、もしかしたら光の先端のある立方体の中の物体よりも、隣の立方体の中の物体との距離の方が近いかもしれない。
vec3 trans(vec3 p){
return mod(p, 4.0) - 2.0;
}float distanceFunc(vec3 p){
return length(trans(p)) - sphereSize;
}
distanceFunc は、最も近い物体との最短距離を返す関数。中で trans が 使われている。 これは何をしている関数だろうか。
まず、球の配置の仕方は、 「{4s-2,4t-2,4u-2} (s,t,u は整数) 」 の位置に、中心がくるようにおいている。
光の先端 p = {x,y,z} が与えられたとき、pが属する立方体の位置は、
s = (x - mod(x,4.0))/4.0 + 1.0
t = (y - mod(y,4,0))/4.0 + 1.0
u = (z - mod(z,4,0))/4.0 + 1.0
であり、最も近い球の中心oは、
{
ox = (x - mod(x,4,0)) + 2.0,
oy = (y - mod(y,4,0)) + 2.0,
oz = (z - mod(z,4,0)) + 2.0
}
すなわち
o = (p - mod(p,4.0)) + 2.0
最短距離は,
length(p-o) - SphereSize
＜＝＞ length(mod(p,4.0)-2.0) - SphereSize
＜＝＞ length(trans(p)) - sphereSize （ただし vec3 trans(vec3 p){return mod(p, 4.0) - 2.0;}）
かくして、複製された物体と光の先端との最短距離を計算することができた。あとはすべて前回と同じだ。
