01/02 競プロ典型012
ビンゴのような長方形の表において、指定された二点が繋がっているか判定
初期のグラフはどのマスも有効ではなく、入力に応じて以下の２種類の操作をする
(1)t==1のとき、指定されたマス(x,y)を有効にする
(2)t==2のとき、指定された二点が、有効なマスのみを辿って結ぶことが可能か判定
Union-find木という考え方がいいらしい
根（木の最下層）が同じなら到達可能だよねという考え方
3と4が繋がっているかは、根までそれぞれ辿っていき3→2→1(根)、4→1(根)のように根が同じなら到達可能
UnionFindは四つの操作
init、初期化
配列parをサイズH*W、初期値-1に初期化
この配列は、各マスの根を保存する
root、根の更新と探索
根を更新しながら根を返す
ちょっとよくわからない
unite、根を統合
与えられた二点の根を同じにする
この問題では、(1)で与えられた一点とそれに隣接する四点を統合する
same、根が同じか判定
その通り
(1)の処理をquery1で、(2)の処理をquery2の関数で行っている
むずいけど段々理解
クラスの書き方
class UnionFind{
public:
func()
};
クラスの変数
UnionFind UF;
12/30 十字架のカルテ 知念実希人
面白かった
医療系の話、特に精神疾患についてこんなにリアルに触れつつミステリーとしてまとめられるのはこの作者の強みだなと感じる。
医療ミステリーと聞くと堅いイメージがあるが、主人公の凜は頭いいながらかわいさもあってそこがこの小説で一番魅力的だった
けどそういった登場人物のバラエティ感が雰囲気を崩してもいるのかなとも思ってしまった、、シリアスなパートで人格描写があまりに素人の想像通りすぎるので笑えてしまう
精神疾患の鑑定、数値で測定できない分論理や証拠で診断を裏付けなければならないという点で、医者というより刑事や弁護士に似たものがある
現実の精神科医もこんな感じなのかな、影山くらい真摯に向き合うのは簡単でないはず、、
支離滅裂で時に凶暴になる、理解の範疇を超える人間の心理に触れるのは並大抵の精神力では務まらないだろうなぁ
精神疾患と診断された人間が犯した罪の十字架を誰が背負うのか、この作品のテーマではあるが、現在の社会では答えが出せないという結論
いくら病気で責任能力がなかったとしても、被害者からしたら被害にあった事実は変わらない
影山も精神病患者に対する社会の在り方に対して理想を持ってはいるが、そこを考えるのは鑑定医の越権だとあきらめている
影山が理想とするシステムはいつかの未来で生まれるのだろうか、、とても生まれるとは思えない、、、
序盤の話は想像を超えないストーリーで少し退屈だったが、最後のエピソードはとてもわくわくしながら読めた
事件の真相が気になるのはもちろん、凜の成長を感じながら読めたのが大きい
凜のキャラがよかったねほんとに
少しきれいに進みすぎ？とも思うが、それを含めても面白かった
4/5
12/29 競プロ典型010
ある配列の部分列の和を計算
シンプルにfor分で回そうとするとTLE
↓
あらかじめ各indexまでの累積和を計算しておいて
累積和[end]-累積和[start-1]
で計算出来る
目から衣
Connecting the dots,CVPR,2019
概要
初の学習ベースの単眼active深度推定
イントロ
キネクトとかの消費者向けdepthカメラは良い感じに活用されているよね
でも、計算コスト、メモリコストの制限を受けるよ
キネクト･･･シンプルな相関ベースのブロックマッチング
この２手法は精度の面で全然遅れている、学習ベースの方が精度良い
今回は学習ベースのアクティブステレオを紹介するよ
カメラ一個で良いし、end-to-endだよ
一般的にactive stereoのデータセットをたくさん用意するのは難しい
なので、自己教師かweakly supervised fashion(?)でやる
related work
Active Depth Sensing
まず、active stereoはtemporal(時間方向)とspatial(空間方向)に分けられる
temporalは、複数のパターン画像を連続で投影し、ピクセルごとに一意の符号付けをする
→複数回の撮影が必要
spatialは、ある程度広い領域で見れば一意なパターン分布になるようにしてマッチングを取る
キネクトV1
→シンプルなタスクに見えるが、photoconsistencyとpatch内で視差が一定になる問題がある
Fanello[10](HyperDepth)
ランダムフォレストでマッチングをする、擬似真値にPatchMatch Stereo、早くて並列出来て良い
（よくわからないので今度読む）
→我々は教師なしで良いので強い
インテルリアルセンス
基本はステレオ、テクスチャレス領域のカバーに構造化光
Fanello(まさかの２回目)
マッチングの効率良いアルゴリズムをやったらしい
Zhang
アクティブステレオの学習ベース、でもステレオ画像がいるっぽい？
Stereo Matching
テクスチャレスむずいよね
Single Image Depth Prediction
最近になって解決されはじめている
→一視点からdepthを特定するのは基本的にill-posed
手法
DOE(Diffractive Optical Element)･･･回折光学素子、光の回折を利用していろんな方向にレーザー光を分散
投影光と輝度値の関係
基本的には、パターン光とアンビエント光の和
パターン光は、投影強度×反射率×シェーディング
それにノイズを足す
基本的には、光源は距離に対して二乗の減衰になるのは点光源のみだけど、レーザー光の発散があるので同じと仮定している
画像をアンビエントとパターン光に分けている
アンビエントは滑らかさ、パターン光はdepthの絶対値がわかる（ステレオ条件を活かせるので）
weak supervision
教師データのラベル付けもある程度ネットワークにやってもらう、そのデータで学習する
12/24 競プロ典型008
配列から条件を満たす部分列を取り出す問題
dpが使えそうっていうのは想像できたが、どう実装するかがわからなかった
解説見ても理解に時間がかかる、、、要復習
選ぶ･･･右下に移動
選ばない･･･右に移動
それだけなのに、わからない、
long long dp[100010][8]
12/24 競プロ典型007
ある値に対して、別の配列の中から一番差が小さい値を探す
二分探索だなぁとはすぐ思いついた
今回は配列がソートされていないので、自分でソートする必要あり
lower_boundで値が入るインデックスを探し、左と右の値それぞれと差を計算して、小さい方が差の最小値
左端と右端の場合は、差が片方しか計算出来ないので、場合分けする必要あり
なんか二分探索で引っかかってしまってプログラムが組めなかった
あとINFの値が小さすぎた
簡単な方の問題なはず
sort(A.begin(),A.end());Aの配列を昇順でソート
pos1=lower_bound(A.begin(),A.end(),B);配列Aの中に値Bを挿入する場合に昇順を壊さないような位置（インデックス）のイテレータを返す
先頭からの距離にしたい場合は、pos1-A.begin()にする必要あり（よくわからない）
12/21 競プロ典型004
行列の要素(i, j)に対して、i行目の和＋j列目の和を計算する
(i, j)の値を二回計算してしまうので一回分引く
めちゃくちゃ簡単だった
先に各行、各列の和を計算してメモしておく
それを用いて答えを計算
for文で1要素ずつ計算するとTLEになるのかな？
" "や改行を出力するタイミングを注意
