WoTの当たり判定を色付きで表示するMODを作った
動機
最近World of Tanksという戦車ゲームにハマった。嬉しいことにこのゲームはMODを作ることを歓迎している。
戦車の装甲値などを一覧で見たかったので、csvにまとめるツールを作った。
しかし、実際には戦車の装甲値は位置によって異なる。これを文字だけで認識するのには限界がある。そこで戦闘中に3Dモデルとして表示することにした。
先駆者
WoTで当たり判定を表示するのにはいくつかの先人がいる。
Web上で見られるものではtanks.ggが有名。
MODとしては、PROTankiがガレージで表示するものを作成している。他にも幾つかあるようだ。
しかし、確認した範囲ではこれらは戦闘中の表示には対応していないようだった。また、モデルを改竄（以下model hack）しているのではなく、コードを改竄（以下code hack）しているらしい。
それに対して、code hackではなくmodel hackだけで実現しようと考えた。理由は下記。
- code hackではバグにより意図せずチートを入れ込んでしまうかもしれない
- code hackではデバッグが大変そう（ほんまか？）
- 表示のことは表示（model）で担いたい
技術詳細
簡単にやったことを説明する。
各戦車はitem_defs/vehicles以下の定義ファイルによってモデルが定義される。
戦車のモデルとは大きく4つのモデルから成る。車体、砲塔、砲身、履帯である。
また、それぞれのモデルは見えるモデル（以下normal model）とは別に、当たり判定モデル（以下collision model）を持っている。 厳密はクライアントで取得できるcollision modelはcollision_client以下に入っており、サーバーサイドのものとは異なるようである。ただ、大差無いだろうということでクライアントのものを使う（というかそれしかモデルを取得できない）。
アイデアとしてはnormal modelをcollision modelに変えるだけである。
各modelは3つのファイルからなる。.model、.visual_processed、.primitives_processedである。
.model
各戦車の定義ファイルから参照される。Level Of Detailを管理する。
.primitives_processed
モデルの頂点群、ポリゴン、ノードを定義する。
.visual_processed
ポリゴンとテクスチャの結びつけ、シェーダーを管理する。
では、normal modelの.primitives_processedと.visual_processedをcollision modelに差し替えれば動くだろうか。
実際このアイデアだけで車体と砲塔は問題ない。また、装甲値は定義ファイルに入っているので、それによって.visual_processed内のテクスチャの参照を書き換えるだけでいい。
しかし、砲身と履帯はもう少し厄介になる。
車体と砲塔、砲身と履帯の違いは「動く」かどうかである。砲身は撃った後のリコイル処理、履帯は言わずもがなである。
当たり判定は動かないモデルであるから、車体と砲塔のように動かないモデルと差し替えるのは比較的簡単であるのだが、砲身と履帯はもう少し工夫が必要となる。
ここからはスキンメッシュアニメーションの理解を前提とする。
戦車のモデルはコード中で組み立てられる。.visual_processedや定義ファイル、また通信によって得られた情報を元に動的に構成される（そうでなければ砲塔は回らない）。
砲身と履帯にはボーンが定義されていて、コード中でそのノードを参照する。つまり安易にモデルを差し替えてノードを消してしまうと参照エラーでクライアントがクラッシュする。
比較的簡単な砲身から見ていこう。
.visual_processedの中にはrootの下にGunというnodeが存在していて、それが実際に動く箇所らしい。
そこで、collision modelの.visual_processedの中でrootではなくGunを参照するように書き換えれば良い。
次に履帯。これは非常に苦労した。
履帯は車輪、サスペンション、トラック（回っている部分）からなる。また、車輪の数などは定義ファイル中に書いてあり、それによってコード中で構成される。
しかしこの定義を書き換えると.primitives_processedとの対応が取れずにクラッシュする。しかも、コード中で駆動輪が2つ無いとエラーを吐くようになっているので、model hackだけでは差し替えることが出来ない。
そこで、normal modelとcollision modelの.primitives_processedをmergeした上で、.visual_processedを改竄してnormal modelだけ見えないようにすることを考えた。これならnormal modelは存在しているので参照エラーは起きない。
normal modelを透明にするには幾つかの方法がある。
- テクスチャを透明にする
- 元の.primitives_processedを改竄してポリゴン数を0にする
- ボーンの変換行列を0にする
選択したのは3の方法である。最初に1をやろうとしたのだができなかった。後から気がついたのだが、これはシェーダーも弄ってやる必要があったらしい。2も挑戦したのだが、.primitives_processedの仕様を把握できず断念した。
3はスキンメッシュアニメーションの仕組みを調べている時に思いついた。.visual_processedでは親nodeに対する回転行列とオフセットを持っている。この回転行列を0にすることで自身以下のnodeを1点に集めることが出来る。つまり透明になる。
合法性
このMODを公開する前に日本のスタッフに聞いたところでは合法だった。
小話
何故クライアントはcollision modelを持っているか
当たり判定処理と言うのはサーバーサイドで行うべき処理なので、クライアントに入っていることが疑問だった。
多分答えの一つはシンプルで、地面や建物との当たり判定はクライアントに担わせるべきであるからだ（normal modelはポリゴンが複雑なのでそれと当たり判定を行うのは難しい）。
ResMgr
WoT（というよりBigWorld）で使われている仮想ファイルシステム。
この検索は非常に「柔軟」である。どうやらファイルのindexを構築する際に小文字に変換するのか大文字小文字の差無くマッチする（後から気がついたので対応が面倒だった）。それだけならまだしも、ディレクトリのパスが'/‘でも’\‘でもマッチする。何故か両方が混ざっているファイルパスが存在していた。勘弁してくれ。
戦車訓練でPantherの砲身が消える
何故か戦車訓練のPantherのcollision modelには砲身が存在しない（普通のPantherには存在している）。つまり、戦車訓練ではPantherの砲身にダメージを与えることが出来ないはずである。あの世界では敵が撃ってこないので確かめる術はないが……。
空間装甲を半透明にしたい
collision modelのデフォルトのシェーダーはlightonlyというものである。これをlightonly_alphaやlightonly_addにすることでアルファブレンディングを行ってくれる……はずだった。ガレージではちゃんと半透明に表示されたのだが、戦闘に出ると履帯が丸ごと消える。謎。
GCJ 2017 Round 1B
B問題をクッソバグらせて絶望していたがCが瞬殺されてギリギリ964位だった。初Round1突破っっぽいので記念に解説を書く。
A
略解
一番ゴールするのが遅い馬と同時にゴールする。
証明
一番ゴールするのが遅い馬（以下B）に注目する。
Bと自身（以下A）が同時にゴールするようにした時、AはゴールするまでBに追いつかない。 AとBは共に等速であるから、距離は線形に縮まる。最初正の距離が開いており、ゴールする時に0であるからそれまで追いつかない。
BとA以外の馬（以下まとめてCとする）について、Cは必ずBに追いつく。 順番待ちルールがない場合、CはBより先にゴールする為これは明らか。Bに追いついてからは1よりAはCにも追いつかない。
CがBに追いつくまでに、AはCに追いつかない。 順番待ちルールが無いとすると、CはAより先にゴールする。1と同様の議論からAはCに追いつけない。
以上から、Bのみを考えればCは考察する必要が無い事がわかる。
文字で書くと冗長だが、馬の変位軸と時間軸のx-tグラフを描けば直感的に理解できると思う。
#include <bits/stdc++.h> using namespace std; int D, N; vector<double> K, S; void solve(){ double mtime = 0; for(int i=0; i<N; i++){ mtime = max(mtime, (D - K[i]) / S[i]); } cout << D / mtime << endl; } int main(){ cout.precision(16); cout.setf(ios::fixed); int T; cin >> T; for(int i=1; i<=T; i++){ cout << "Case #" << i << ": "; cin >> D >> N; K.resize(N); S.resize(N); for(int i=0; i<N; i++) cin >> K[i] >> S[i]; solve(); } return 0; }
B
略解
- small
最も多い色を並べ、残り2色を左右から一つ飛ばしで挿入していく。
- large
R -= G, Y -= V, B -= Oとしてsmallと同様の問題を解いた後、残った色を挿入。
証明
対称性から、Rを最も数が多い色として一般性を失わない。
R > Y+Bであるなら、IMPOSSIBLEとなる（必要性）。 どのように挿入してもRが隣り合うので自明。
IMPOSSIBLEであるなら、R > Y+Bである（十分性）。 対偶をとって、R <= Y+Bであるなら必ず解を構成できることを示す。 これはRの左右からY, Bをそれぞれ挿入すると良い。
GはR、OはB、VはYとしか隣合えない（題より）。 small解けてlarge解けてない人はこの制約を見逃していそう（僕がそうでした）。
GとRしか存在しない時、G == Rの場合しか解が存在しない（対称性よりO, Vは略）。 GRGR…となるケース以外は明らかに同じ色が隣り合う（鳩ノ巣原理？）
GとR以外にも色が存在する時、R -= Gとして問題を解くことが等価（対称性より(ry）。 Gは（Gを含めて）R以外と隣合えないので、RGR…RGRという風にRで両端をサンドイッチする必要がある。 これは先頭のRGR…RGを取り除いてRのみとして問題を解くのと同じ。
#include <bits/stdc++.h> using namespace std; int N; int R, O, Y, G, B, V; string solve(){ string table = "ROYGBV"; if(R == G && (Y|V|B|O) == 0){ string res = ""; for(int i=0; i<R; i++) res += "RG"; return res; } if(Y == V && (R|G|B|O) == 0){ string res = ""; for(int i=0; i<Y; i++) res += "YV"; return res; } if(B == O && (R|G|Y|V) == 0){ string res = ""; for(int i=0; i<B; i++) res += "BO"; return res; } R -= G; Y -= V; B -= O; if(R < 0 || Y < 0 || B < 0) return "IMPOSSIBLE"; if((R==0 && G!=0) || (Y==0 && V!=0) || (B==0 && O!=0)) return "IMPOSSIBLE"; if(R>Y+B || Y>R+B || B>R+Y) return "IMPOSSIBLE"; bool ymax = Y > B && R < max(Y, B); bool bmax = B > Y && R < max(Y, B); if(ymax){ swap(R, Y); swap(G, V); swap(table[0], table[2]); swap(table[3], table[5]); } if(bmax){ swap(R, B); swap(G, O); swap(table[0], table[4]); swap(table[3], table[1]); } vector<int> vec; for(int i=0; i<R; i++) vec.push_back(0); for(int i=0; i<Y; i++){ if(i < R) vec.insert(vec.begin()+i*2+1, 2); else vec.push_back(2); } reverse(vec.begin(), vec.end()); for(int i=0; i<B; i++){ if(i < R+Y) vec.insert(vec.begin()+i*2, 4); else vec.insert(vec.begin(), 4); } for(int i=0; i<vec.size(); i++){ if(vec[i] == 0){ for(int j=0; j<G; j++){ vec.insert(vec.begin()+i, 3); vec.insert(vec.begin()+i, 0); } break; } } for(int i=0; i<vec.size(); i++){ if(vec[i] == 2){ for(int j=0; j<V; j++){ vec.insert(vec.begin()+i, 5); vec.insert(vec.begin()+i, 2); } break; } } for(int i=0; i<vec.size(); i++){ if(vec[i] == 4){ for(int j=0; j<O; j++){ vec.insert(vec.begin()+i, 1); vec.insert(vec.begin()+i, 4); } break; } } string res = ""; for(auto v: vec) res += table[v]; return res; } int main(){ int T; cin >> T; for(int i=0; i<T; i++){ cout << "Case #" << i+1 << ": "; cin >> N; cin >> R >> O >> Y >> G >> B >> V; cout << solve() << endl; } return 0; }
C
略解
まず1頭の馬だけを使った場合の最小時間を求め、その後任意の馬を使った場合の最小時間を求める。
証明？
正直この問題は証明が殆ど存在しないと思う……
任意の2点間を1頭の馬だけを使って移動する場合の最小時間を求める。 Warshall-Floydで全点対最短経路を求めた後、始点の馬で移動できる場合はその場合に掛かる時間で更新する。
任意の2点間を任意の馬を使って移動する場合の最小時間を求める。 1により任意の2点間を1頭の馬だけを使い移動する場合の最小時間の配列が求まっている。 これを用いて同様にWarshall-Floydをすると任意の馬を使った場合の最小時間が求まる。
#define _LIBCPP_DEBUG 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; int N, Q; vector<double> E, S; vector<vector<ll>> D; void solve(){ for(int k=0; k<N; k++){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++) if(D[i][k] != -1 && D[k][j] != -1){ if(D[i][j] == -1) D[i][j] = D[i][k] + D[k][j]; else D[i][j] = min(D[i][j], D[i][k] + D[k][j]); } } } vector<vector<double>> nD(N, vector<double>(N, 1e100)); for(int i=0; i<N; i++){ for(int j=0; j<N; j++) if(D[i][j] != -1 && D[i][j] <= E[i]){ nD[i][j] = min(nD[i][j], D[i][j]/S[i]); } } for(int k=0; k<N; k++) for(int i=0; i<N; i++) for(int j=0; j<N; j++) nD[i][j] = min(nD[i][j], nD[i][k] + nD[k][j]); for(int i=0; i<Q; i++){ int s, t; cin >> s >> t; s--; t--; cout << " " << nD[s][t]; } cout << endl; } int main(){ cout.precision(16); cout.setf(ios::fixed); int T; cin >> T; for(int i=0; i<T; i++){ cout << "Case #" << i+1 << ":"; cin >> N >> Q; E.resize(N); S.resize(N); for(int i=0; i<N; i++) cin >> E[i] >> S[i]; D.clear(); for(int i=0; i<N; i++){ vector<ll> vec(N); for(int j=0; j<N; j++){ cin >> vec[j]; } D.push_back(vec); } solve(); } return 0; }
Nintendo Challenge解いた
まーす氏が突然問題を送ってきた。
https://www.nerd.nintendo.com/files/HireMe.cpp@aki33524 https://t.co/OdsGbvIZGS 解いて
— まーす (@__math) 2017年4月9日
実は初日で解法分かってたのにプログラムにバグが有って数バイト書き換えたら出来てクッソしょんぼり。
// https://www.nerd.nintendo.com/files/HireMe.cpp #include <string.h> #include <stdio.h> typedef unsigned char u8; typedef unsigned int u32; u8 confusion[512]={ 0xac,0xd1,0x25,0x94,0x1f,0xb3,0x33,0x28,0x7c,0x2b,0x17,0xbc,0xf6,0xb0,0x55,0x5d, 0x8f,0xd2,0x48,0xd4,0xd3,0x78,0x62,0x1a,0x02,0xf2,0x01,0xc9,0xaa,0xf0,0x83,0x71, 0x72,0x4b,0x6a,0xe8,0xe9,0x42,0xc0,0x53,0x63,0x66,0x13,0x4a,0xc1,0x85,0xcf,0x0c, 0x24,0x76,0xa5,0x6e,0xd7,0xa1,0xec,0xc6,0x04,0xc2,0xa2,0x5c,0x81,0x92,0x6c,0xda, 0xc6,0x86,0xba,0x4d,0x39,0xa0,0x0e,0x8c,0x8a,0xd0,0xfe,0x59,0x96,0x49,0xe6,0xea, 0x69,0x30,0x52,0x1c,0xe0,0xb2,0x05,0x9b,0x10,0x03,0xa8,0x64,0x51,0x97,0x02,0x09, 0x8e,0xad,0xf7,0x36,0x47,0xab,0xce,0x7f,0x56,0xca,0x00,0xe3,0xed,0xf1,0x38,0xd8, 0x26,0x1c,0xdc,0x35,0x91,0x43,0x2c,0x74,0xb4,0x61,0x9d,0x5e,0xe9,0x4c,0xbf,0x77, 0x16,0x1e,0x21,0x1d,0x2d,0xa9,0x95,0xb8,0xc3,0x8d,0xf8,0xdb,0x34,0xe1,0x84,0xd6, 0x0b,0x23,0x4e,0xff,0x3c,0x54,0xa7,0x78,0xa4,0x89,0x33,0x6d,0xfb,0x79,0x27,0xc4, 0xf9,0x40,0x41,0xdf,0xc5,0x82,0x93,0xdd,0xa6,0xef,0xcd,0x8d,0xa3,0xae,0x7a,0xb6, 0x2f,0xfd,0xbd,0xe5,0x98,0x66,0xf3,0x4f,0x57,0x88,0x90,0x9c,0x0a,0x50,0xe7,0x15, 0x7b,0x58,0xbc,0x07,0x68,0x3a,0x5f,0xee,0x32,0x9f,0xeb,0xcc,0x18,0x8b,0xe2,0x57, 0xb7,0x49,0x37,0xde,0xf5,0x99,0x67,0x5b,0x3b,0xbb,0x3d,0xb5,0x2d,0x19,0x2e,0x0d, 0x93,0xfc,0x7e,0x06,0x08,0xbe,0x3f,0xd9,0x2a,0x70,0x9a,0xc8,0x7d,0xd8,0x46,0x65, 0x22,0xf4,0xb9,0xa2,0x6f,0x12,0x1b,0x14,0x45,0xc7,0x87,0x31,0x60,0x29,0xf7,0x73, 0x2c,0x97,0x72,0xcd,0x89,0xa6,0x88,0x4c,0xe8,0x83,0xeb,0x59,0xca,0x50,0x3f,0x27, 0x4e,0xae,0x43,0xd5,0x6e,0xd0,0x99,0x7b,0x7c,0x40,0x0c,0x52,0x86,0xc1,0x46,0x12, 0x5a,0x28,0xa8,0xbb,0xcb,0xf0,0x11,0x95,0x26,0x0d,0x34,0x66,0x22,0x18,0x6f,0x51, 0x9b,0x3b,0xda,0xec,0x5e,0x00,0x2a,0xf5,0x8f,0x61,0xba,0x96,0xb3,0xd1,0x30,0xdc, 0x33,0x75,0xe9,0x6d,0xc8,0xa1,0x3a,0x3e,0x5f,0x9d,0xfd,0xa9,0x31,0x9f,0xaa,0x85, 0x2f,0x92,0xaf,0x67,0x78,0xa5,0xab,0x03,0x21,0x4f,0xb9,0xad,0xfe,0xf3,0x42,0xfc, 0x17,0xd7,0xee,0xa3,0xd8,0x80,0x14,0x2e,0xa0,0x47,0x55,0xc4,0xff,0xe5,0x13,0x3f, 0x81,0xb6,0x7a,0x94,0xd0,0xb5,0x54,0xbf,0x91,0xa7,0x37,0xf1,0x6b,0xc9,0x1b,0xb1, 0x3c,0xb6,0xd9,0x32,0x24,0x8d,0xf2,0x82,0xb4,0xf9,0xdb,0x7d,0x44,0xfb,0x1e,0xd4, 0xea,0x5d,0x35,0x69,0x23,0x71,0x57,0x01,0x06,0xe4,0x55,0x9a,0xa4,0x58,0x56,0xc7, 0x4a,0x8c,0x8a,0xd6,0x6a,0x49,0x70,0xc5,0x8e,0x0a,0x62,0xdc,0x29,0x4b,0x42,0x41, 0xcb,0x2b,0xb7,0xce,0x08,0xa1,0x76,0x1d,0x1a,0xb8,0xe3,0xcc,0x7e,0x48,0x20,0xe6, 0xf8,0x45,0x93,0xde,0xc3,0x63,0x0f,0xb0,0xac,0x5c,0xba,0xdf,0x07,0x77,0xe7,0x4e, 0x1f,0x28,0x10,0x6c,0x59,0xd3,0xdd,0x2d,0x65,0x39,0xb2,0x74,0x84,0x3d,0xf4,0xbd, 0xc7,0x79,0x60,0x0b,0x4d,0x33,0x36,0x25,0xbc,0xe0,0x09,0xcf,0x5b,0xe2,0x38,0x9e, 0xc0,0xef,0xd2,0x16,0x05,0xbe,0x53,0xf7,0xc2,0xc6,0xa2,0x24,0x98,0x1c,0xad,0x04}; u32 diffusion[32]={ 0xf26cb481,0x16a5dc92,0x3c5ba924,0x79b65248,0x2fc64b18,0x615acd29,0xc3b59a42,0x976b2584, 0x6cf281b4,0xa51692dc,0x5b3c24a9,0xb6794852,0xc62f184b,0x5a6129cd,0xb5c3429a,0x6b978425, 0xb481f26c,0xdc9216a5,0xa9243c5b,0x524879b6,0x4b182fc6,0xcd29615a,0x9a42c3b5,0x2584976b, 0x81b46cf2,0x92dca516,0x24a95b3c,0x4852b679,0x184bc62f,0x29cd5a61,0x429ab5c3,0x84256b97}; //u8 input[32]={ ////change only this : //0x66,0xd5,0x4e,0x28,0x5f,0xff,0x6b,0x53,0xac,0x3b,0x34,0x14,0xb5,0x3c,0xb2,0xc6, //0xa4,0x85,0x1e,0x0d,0x86,0xc7,0x4f,0xba,0x75,0x5e,0xcb,0xc3,0x6e,0x48,0x79,0x8f //// //}; u8 input[32] = {155, 246, 61, 32, 15, 133, 115, 86, 141, 81, 144, 145, 255, 191, 104, 115, 134, 60, 190, 173, 242, 65, 252, 44, 146, 109, 80, 4, 19, 106, 217, 180}; void Forward(u8 c[32],u8 d[32],u8 s[512],u32 p[32]) { for(u32 i=0;i<256;i++) { for(u8 j=0;j<32;j++) { d[j]=s[c[j]]; c[j]=0; } for(u8 j=0;j<32;j++) for(u8 k=0;k<32;k++) c[j]^=d[k]*((p[j]>>k)&1); } for(u8 i=0;i<16;i++) d[i]=s[c[i*2]]^s[c[i*2+1]+256]; } int main(int argc, char* argv[]) { // u8 target[]="Hire me!!!!!!!!"; u8 target[]="youjodepoyopoyo"; u8 output[32]; Forward(input,output,confusion,diffusion); printf("%s\n", output); return memcmp(output,target,16); // => contact jobs(at)nerd.nintendo.com }
GCJ2017qual AをO(N)で解く
概要
長さNのbit列が与えられる。長さKの連続した列をflipして、全て1になるようにしたい。不可能ならIMPOSSIBLE、可能ならflipする最小数を答える。
略解
左から貪欲に0になっているところからflipする。背理法で証明できる。
largeケースですらなので普通に
で解けてしまう。
高速化
flipを一様加算と見る。BITを使えばは自明。もう少し工夫する。
一様加算といえばBITの他にはimos法がある。今回はこれを使う。 imos法は微分した列を足した後に積分（累積和）するという手法である。一様加算の場合、微分した列は両端のみ足し込めば良く長さに依存しない。
しかし、足し合わせた後に逐一累積和を取れば意味がない。そこで、目標とする列も微分することを考える。 目標とする列は全て1である。これを微分すると、100….000となる。
また、最初に与えられた列も微分する必要があるが、足し合わせた後にmod 2を取ると考えると実は1も-1も等価であるためにとなる点を1とすれば良い。
後は、最初だけ1、他は0となるように（微分した）flipをする。
#include <bits/stdc++.h> using namespace std; string S; int K; vector<bool> vec; int ans; void flip(int x){ vec[x] = vec[x]^1; vec[x+K] = vec[x+K]^1; ans++; } int solve(){ cin >> S >> K; int L = S.size(); ans = 0; vec.resize(L+1, false); vec[0] = S[0] == '+'; for(int i=1; i<L; i++) vec[i] = S[i-1] != S[i]; if(!vec[0]) flip(0); for(int i=1; i<L-K+1; i++) if(vec[i]) flip(i); for(int i=L-K+1; i<L; i++) if(vec[i]) return -1; return ans; } int main(){ int T; cin >> T; for(int t=0; t<T; t++){ cout << "Case #" << t+1 << ": "; int ans = solve(); if(ans < 0) cout << "IMPOSSIBLE" << endl; else cout << ans << endl; } return 0; }
映像研には手を出すな!がヤベエ
映像研には手を出すな!を読んだ。感想を一言で言えば、「ヤベエ漫画が出て来やがったぜ」。 それ町*1のようなハイコンテクストなギャグを挟みながら、それでいてアツい漫画だった。
まだ読んでない？一話だけならタダで読めるぞ！ spi-net.jp
もしまだこの漫画を読まずにこの記事を読もうとしているなら辞めたほうが良い。こんな良い漫画のネタバレを見てしまうなんて勿体無い。早く本屋に走るかkindleで買え！
読んだか？読んだな！
以下つらつら好きなポイントやら気付きやらを羅列する。
浅草みどり
設定を考えるのが好きで、背景（というより世界観？）を描くのが得意。人物を描くのは得意ではない。 それ町の歩鳥っぽいキャラ。普段アホだけど憎めないやつで、ふとした時に冴えた事を言う。 「きっかけやら環境が整わんと何もできない*2」と主張するように、実は案外ビビリ。 作者の分身。作者はどうやら未来少年コナンが好きらしい。
水崎ツバメ
財閥令嬢。初登場シーン*3ではいけ好かない顔をしておる。 みどりとは対称的に人物（やその動き）を描くのが得意。 いけ好かない奴かと思いきや、みどりと同じ位アホ。
金森さやか
アホ2人のまとめ役。お金の話が好きで美脚（キャラ紹介）。 本作で一番好きなキャラ。
みどりがさやかにアニ研に行こうと誘った際、さやかはすげなく拒否している*4。 しかし、みどりが実際に絵を書いたのを見た途端（牛乳を要求はするけども）、行くことに同意する*5。 どうやらさやかはコイツはやる奴だと認めた相手であれば、そいつに投資してみようと思うタイプであるらしい。 ツバメの絵を見せられた際には、「どうです浅草氏。」とみどりの意見を仰いでいる*6。 この点からも、さやかがみどりを高く評価しているのが分かる。加えて、自分の詳しくない分野であるからきちんと専門家であるみどりの意見を聞く姿勢が良い。また、みどりらを職人として捉えて*7、彼女らが快適に過ごせる様に注力している。
アニ研に入れないなら映像研を作ってしまえなんて言い出すあたり、実はさやかは他の2人に比べて行動力がずば抜けている。面白いから投資してやるという気概は、自分が面白いモノを見たいという実は子供じみた動機に思える。 本作では全編を通して、みどりの妄想が現実を侵食する。いわばこれはごっこ遊びで、その世界に入れるのは少年の心を持っている人間である。にも関わらず、さやかもちゃっかり入っているのだ。ツバメやみどりのアホが際立っているけど、実は一番少年の心を持っているのはさやかかもしれない。
彼女は金が好きというよりも、金の大切さを理解している、という風に感じる。ただ単にがめついというよりは何かをやるためには金が必要という基本的な点（とはいえ高校生でそれをきちんと理解しているのはそう居ないと思う）を理解している。
ツバメがどうして手伝ってくれるのかと聞いた時、さやかは「金の為」と答える*8。 でも、これは方便だろう（みどりとアニ研に行く時にも牛乳を言い訳にしている、金は彼女にとって良い方便なのかもしれない）。 どうせ彼女がこの時考えていたのはこうだ。「なんだか知らんが、面白くなってきやがった」*9
まとめると、彼女は職人を尊敬し、彼らが自由に動けるように奔走する人間である。 彼女から受けるパッと見の印象からは印象からは遠いとても誠実で理想的なリーダー像がそこにある。 そういうキャラを好きになるなという方が無理なのだなぁ。
生徒会
さかき・ソワンデというハーフの書記の子が一番デキるっぽいのが面白い。 「細工は流々仕上げをご覧じろ」なんて言葉、日本人でも知らない人多そうなのにとか考えてた。 人は見かけによらないという話を入れたかったのだろうか。 彼女はさやかと似た人格であると思う。 つまり、自分が認めた人間であれば評価するというタイプ。
上映シーン
カッケエ。面白いのは、みどりが作った世界に生徒たちが引きずり込まれているところ*10。 よくある描写だけど、この作品ではもうちょっと違った趣がある。 先に述べたように、みどりの妄想が現実を侵食するが、それはあくまでも少年の心を持つ人間に対してであったはずである。 そういう世界観の中で、みどりらが作った世界の中に人々を取り込めた。そう考えると、ワクワクしますね。
妄想
金森さやかという人格はどうやって作られたのだろう。少し考えてみた。
さやかはツバメと似たような出自の人間だったら面白いなぁと考えていた。 まず、彼女のリーダーシップだ。 みどりやツバメのように、職人が「こういうリーダーが欲しい」という点に辿り着くことはあるだろう。 しかし、さやかはそういう職人ではない。彼女は何かに特化しているわけではないのだ。 そういう人間がどうやってあのリーダーシップを得たのだろう。 彼女が高校生という若さでその始点を得たのは、幼少期からの環境によるのではないかと考えた。 つまり、彼女の家庭は何かを経営していたのではないだろうか。その家庭で受けた教育により彼女は今の人格を得たのでは無いだろうか。 実は彼女が山奥の財閥だったりしたら面白い。
しかし、彼女は別段金持ちという雰囲気を出していない。 それは、彼女が家に反抗している故ではないか。 ツバメがさやかに「足長いね」と言った時に、さやかは軽く受け流している*11。 さやかはスタイルが良いし、多分化粧をすれば中々に美人だろう（ほんまか？）。 自分の容姿のような親から貰ったモノを使わずにやってやるぜという意志からそういう行動をしているとかだったら面白い。
という様なことを考えていたけど、ツバメは金があるはずなのに部のために金を使おうとしてない、なんでだろう。 なんかそれに対する描写あったっけ。
競プロ勢のためのデバッグテクニック
Facebook Hacker Cup Round1の問題をオーバーフローと配列外参照で2問落としてしまい、反省を込めてデバッグテクニックを調べました。
競技勢がやらかすケアレスミスなバグの多くはこの2つだと思うので、この2つのみについて述べていきます。また、僕は普段の実装にMacを使っているので、gccのフリをしたMac仕様Clang（クソ）についても言及します。
オーバーフロー
これは-ftrapvオプションを付けてコンパイルしたファイルを実行すればオーバーフローした瞬間に検知（abort）する事が出来ます。
しかし、どこで死ぬのかがわからずこのままでは使い勝手が悪いので、-g（デバッグ）オプションも付けてコンパイルした後に、gdbで実行すると良いです。
#include <iostream> using namespace std; int main(){ int x = 10000000; int y = 10000000; cout << x * y << endl; }
$ clang++ -ftrapv -g overflow.cpp $ gdb -q ./a.out Reading symbols from ./a.out...done. (gdb) r Starting program: /tmp/a.out Program received signal SIGILL, Illegal instruction. 0x00000000004008cf in main () at overflow.cpp:8 8 cout << x * y << endl;
これはUbuntuでビルドした最新のClang++、Mac版Clang++でも動きます。 Ubuntuにもとから入っていたg++では__GI_raiseでSIGQUITを送出して終了した点で終了しました。（これはよく考えたらg++ではなくてgdbがデフォルトでユーザーのプログラムの中まで戻ってくるかどうかというだけかもしれない？あと、No such file or directory.と出ているのがややこしいですが、これは多分gdbのエラーメッセージ。）
$ g++ -ftrapv -g overflow.cpp $ gdb -q ./a.out Reading symbols from ./a.out...done. (gdb) r Starting program: /tmp/a.out Program received signal SIGABRT, Aborted. 0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54 54 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
一応、backtraceをすればどこで死んだかは分かります。
(gdb) bt #0 0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54 #1 0x00007ffff74ad01a in __GI_abort () at abort.c:89 #2 0x00007ffff7842522 in __mulvsi3 () from /lib/x86_64-linux-gnu/libgcc_s.so.1 #3 0x00000000004008b7 in main () at overflow.cpp:8 (gdb) frame 3 #3 0x00000000004008b7 in main () at memory.cpp:8 8 cout << a * b << endl;
Ubuntuにはgdbがデフォルトで入っているので、ICPCでも使えますね。
配列外参照
これはg++とMac版Clang++で対応が若干変わります。
g++
g++の場合、最初に#define _GLIBCXX_DEBUGを書くことで検出出来ます。
最初に書かないと動かないので注意してください。
これは、vectorファイルの中に
#ifdef _GLIBCXX_DEBUG # include <debug/vector> #endif
というコードがあるためです。つまり、include前であれば良いですが、誤りを避けるために最初に書いておくことをおすすめします。
#define _GLIBCXX_DEBUG #include <vector> using namespace std; int main(){ vector<int> a(10); for(int i=0; i<100; i++) a[i] = 1; return 0; }
例によってgdbを使います。
$ g++ -g memory.cpp
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) r
Starting program: /tmp/a.out
/usr/include/c++/5/debug/vector:409:error: attempt to subscript container
with out-of-bounds index 10, but container only holds 10 elements.
Objects involved in the operation:
sequence "this" @ 0x0x7fffffffdd00 {
type = NSt7__debug6vectorIiSaIiEEE;
}
Program received signal SIGABRT, Aborted.
0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
54 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0 0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
#1 0x00007ffff74ad02a in __GI_abort () at abort.c:89
#2 0x00007ffff7b0af95 in __gnu_debug::_Error_formatter::_M_error() const () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3 0x000000000040110c in std::__debug::vector<int, std::allocator<int> >::operator[] (this=0x7fffffffdd00, __n=10) at /usr/include/c++/5/debug/vector:409
#4 0x0000000000400ba8 in main () at memory.cpp:8
(gdb)
Mac版Clang++
Mac版Clangの場合、_GLIBCXX_DEBUGの代わりに_LIBCPP_DEBUGを用います。
_LIBCPP_DEBUGの設定した値によってデバッグレベルが変わるらしく、0か1をdefineすれば良いのですが、何故か1を指定するとバグりました。
#define _LIBCPP_DEBUG 0 #include <vector> using namespace std; int main(){ vector<int> a(10); for(int i=0; i<100; i++) a[i] = 1; return 0; }
$ g++ memory.cpp $ ./a.out vector[] index out of bouns Abort trap: 6
ここまではICPCで使うことも想定して電子的な準備に該当しない領域でどこまで出来るのか考えました
valgrindを使う方法
Facebook Hacker CupやGoogle Code Jam、または一般のプログラミングに関してはこれが一番やりやすいかもしれません。 -gオプションを付けてコンパイルした後
valgrind ./a.out
とするだけで詳細な結果が出てきます。
$ g++ -g -O0 test.cpp $ valgrind ./a.out ==1120== Memcheck, a memory error detector ==1120== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. ==1120== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info ==1120== Command: ./a.out ==1120== ==1120== Invalid write of size 4 ==1120== at 0x10000156D: main (test.cpp:7) ==1120== Address 0x100a8e068 is 0 bytes after a block of size 40 alloc'd ==1120== at 0x10000A681: malloc (in /usr/local/Cellar/valgrind/3.12.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so) ==1120== by 0x10004F7DD: operator new(unsigned long) (in /usr/lib/libc++.1.dylib) ==1120== by 0x10000179E: std::__1::vector<int, std::__1::allocator<int> >::allocate(unsigned long) (new:156) ==1120== by 0x1000016B1: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1070) ==1120== by 0x1000015CC: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1073) ==1120== by 0x10000152E: main (test.cpp:5) ==1120== ==1120== ==1120== HEAP SUMMARY: ==1120== in use at exit: 22,153 bytes in 191 blocks ==1120== total heap usage: 258 allocs, 67 frees, 27,993 bytes allocated ==1120== ==1120== LEAK SUMMARY: ==1120== definitely lost: 0 bytes in 0 blocks ==1120== indirectly lost: 0 bytes in 0 blocks ==1120== possibly lost: 0 bytes in 0 blocks ==1120== still reachable: 0 bytes in 0 blocks ==1120== suppressed: 22,153 bytes in 191 blocks ==1120== ==1120== For counts of detected and suppressed errors, rerun with: -v ==1120== ERROR SUMMARY: 90 errors from 1 contexts (suppressed: 0 from 0)
追記
オーバーフロー時の挙動がMacとUbuntuで異なっていたのはどうやらftrapvの実装の違いのせいのようです
@aki33524 clangはftrapvの実装にundefinedなオペコードぶち込んで対応してるらしい https://t.co/3Yq4hde8JU
— るくす (@RKX1209) 2017年1月16日
" -ftrapv flag will cause clang to intenionally insert ud2"
tf-idfを使ったDbpediaの型推定
卒論が上手く行かないので逃避していたらまぁまぁ良さそうなので公開しておく。
前提
DbpediaとはWikipediaを元に半自動で変換したLODである。
各リソース（記事）にはclass（人とか政治家とか虫とか）が定義されたりされなかったりする。
全リソースの3割ほどにclassが定義されておらず、これを推定する需要がある。
この前のISWCのデモセッションでDbpediaの型（class）推定をしようとしている研究があったのが心に残っていた（全然手法違うけど）。
卒論でデータを眺めていたらふとtf-idfで上手く行くように見えたので試してみた。
というかこれをもっと筋良くした研究が既にあると思うけどパッと出てこなかった。Dbpediaの自動変換の過程で似たようなことをやっている気がする。詳しい人教えてください。
アイデア
基本的なアイデアとしては
「A is writer of B」
という関係があれば、Aはおそらく作家だろうしBはおそらく本だろうという推定が出来るというところ。
つまり、リソース（Wikipediaの記事1つに該当）間のプロパティ（Wikipedia間のリンクに相当、ただのリンクではなく種類がある）
を特徴量として扱う。
tf-idfについては無限に資料があるので詳しく語らないが
「リソースを文書とする」
「（方向、プロパティ）の組を語彙とする」
というアイデアをtf-idfに適用した。
また、2つの文書間の類似度はcos類似度によって表される。
そこで、あるリソースAと他の任意のリソースBのcos類似度を計算して、Bにclassが定義されていれば類似度をclassの推定値として重畳する。
この時、足し合わせたあとにそもそもそのclassを持つリソースがいくつあるかで除したり、推移的なtype定義を用いたりするとよい。
最終的に、最も推定値の大きなclassが推定結果である。
所感
簡単な割に結構上手く行ってくれる。
例えばバラク・オバマにはclassが定義されていない。これを推定するときちんとpolitician - Wikidataと出てきた。
ただ、当然だがプロパティ関係が殆ど存在していないようなリソースは推定を誤る。恐竜が「虫」に推定されたりしていた。
他には、1735年などの年度シリーズが殆ど「場所」として推定されていた。
これは日本語版Dbpediaのデータが悪いようで、birthPlaceとして人との間に関係が定義されていた（birthTime？的なものにしてくれ……）。
これを発展させるとすればプロパティの種類だけではなく、その先に存在しているリソースのclassなども推定すべきだろう。
「A is writer of <instance of Movie>」であれば、Aは作家は作家でも監督？とかそういった推定が出来るかもしれない。
結局これは辺に種類が付いた有向グラフのクラスタリング問題に帰着できそうで、何か機械学習で上手く出来たりするのかなぁというところ。
コードはこれです。
GitHub - aki33524/typeprediction
