コーディングの問題
string A, Bについて、AがBを部分列として持つかを判定するコードを書け。A, Bの長さは100以下． (SRM 597 Div.2 Med)
DPの問題
bool配列Sについて、部分列S[a..b]に含まれる部分列の中で連続した1の最長の長さmaxlen(a, b)を考える。maxlenに関する漸化式を構成せよ。 (SRM 595 Div.1 Med)
DPの問題
bool配列Sについて、以下を満たす部分列S[a..b]の場合の数を求めよ。条件: 最後にi回以上Trueが連続する、もしくはm回以上連続したTrueが存在する。 (SRM 595 Div.1 Med)
http://topcoder.g.hatena.ne.jp/evima/20131025
Div.2に落ちました。大いに反省します。
Easy LittleElephantAndIntervalsDiv1
Div.1 Easyにしてはかなり簡単だったはず。塗りつぶす時に何故か逆の順番で塗って死亡。
答え: 2^最終結果に残っている操作の種類数
以下、コーディングの勉強。
2^numの仕方。
1LL << num // (long long)2^num;
種類の数え方。
set<int> s; set.insert(1): set.insert(1): set.insert(2): set.insert(2): cout << set.size() << endl;
Medium
手も足も出なかった感じ。まぁDiv.1 Medはいつもこんな感じ。
問題自体について
「S[a..b] + S[ c..d] にGがm回連続で現れる」とは、次のうちどれか1つ以上が成り立つこと
条件A: S[a..b]にGがm回連続で現れる
条件B: S[ c..d]にGがm回連続で現れる
条件C: S[a..b]の終わりの部分と、S[ c..d]の始めの部分をつなげるとGがm回連続で現れる」
「#(AorBorC) = #(A)+#(B)+#(C)-#(AandB)-#(BandC)-#(CandA)+#(AandBandC)」
ということを整理した上で、a, bを固定して、c, dの場合の数をO(1)で求める方法を考える。
戦略的な問題
・問題は部分分解すべき。条件AorBを満たす場合の数、などはべん図が利用可能。
・AorBに応じてCをする、みたいな計算は、本当は4つ実装しなければならないが、効果が一致するならば場合分けをまとめてよい。しかし、思考過程では場合分けしていなければならない。
・欲しいもの駆動でトップダウンに考えるべき。
・欲しいものがあったら全て置いてしまう。そこで初めて漸化式が書けるようになる。
・漸化式を書くために描く模式図は、既知前提部分をボックスにするとよい。ボックスの性質がかける程度に大きめに。
アルゴリズムの問題
いわゆる「前処理を頑張る」という奴。
O(N^2)の処理の中でO(N^2)の処理をするとO(N^4)になるが
二回目のO(N^2)をO(1)で参照可能なテーブルを作るための、O(N^2)が存在すれば、全体もO(N^2)となる。
漸化式で扱われているものは、そのループは漸化的な方向に回す。
逐次的なDPについて。
DPは必ずしも全部メモリに取っておかなければならない訳ではなく、むしろ計算に最小限のバッファとしてメモリを利用することが望まれる。
一方で、本当はO(1)でいいDPを後の計算の事情でO(M)にしたりすることができる。
漸化的な変数と漸化的でない変数が含まれるとき、これのループの順番をうまくコーディングすれば、
・外で回している方のメモリサイズNに対してM(N)を利用できる。
・外側のループのスコープで、DPの計算結果をO(1)で利用できる。その後の計算に何が必要なのかとの兼ね合い。
これは、以下のような考え方から導かれる。
図で考える。-|が回ったループ、cが計算された値、*が未計算の値だとする。
漸化的変数を先に持ってくると、
c****
c****
c****
↓
cc***
cc***
cc***
↓
ccccc
ccccc
ccccc
逆に、漸化的でない変数を後に持ってくると、
c****
c****
c****
↓
ccccc
c****
c****
↓
ccccc
ccccc
ccccc
以下はforの順番を逆にしても計算量に影響を出さずに、メモリオーダを調整可能であることを例示するコード。
#include <iostream>
#include <vector>
#define NUM 5
using namespace std;
void print_vec(vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
}
int f(int a)
{
return a * 2 + 1;
}
void dp_ji(void)
{
cout << "#ji" << endl;
vector<int> tj = {1, 2, 3, 4};
print_vec(tj);
for (int j = 0; j < NUM-1; j++) {
for (int i = 0; i < tj.size(); i++)
tj[i] = f(tj[i]);
print_vec(tj);
}
}
void dp_ij(void)
{
cout << "#ij" << endl;
vector<int> tj = {1, 2, 3, 4};
vector<int> ti(NUM);
for (int i = 0; i < tj.size(); i++) {
ti[0] = tj[i];
for (int j = 0; j < NUM; j++)
ti[j+1] = f(ti[j]);
print_vec(ti);
}
}
int main(void)
{
dp_ji();
dp_ij();
return 0;
}
・メイク前のスキンケア
( ステップ 1 )フェースタオルを温水でぬらす
( ステップ 2 )温めたフェースタオルを顔全体に乗せて、1 分待つ
( ステップ 3 )洗顔フォームを顔全体に塗る
( ステップ 4 )洗顔フォームを残したまま、1 分ほど 待つ
( ステップ 5 )温水で洗顔料を落とす
( ステップ 6 )化粧水を開いた毛穴に押し込む様に顔全体につける
( ステップ 7 )冷たい水に浸したフェースタオルを顔全体に乗せ、毛穴をふさぐ
( ステップ 8 )乳液を顔全体につける
( ステップ 9 )温かいフェースタオルで 1 分待つ
( ステップ 10 )およそ 1 分から 3 分待つ
・手を洗う
(ポイント 1 )メイク前、薬用ハンドソープを使って、手を洗う
(ポイント 2 )メイク中に手が汚れたら、こまめに手を洗う
・部屋の明るさが大切。
外出したときの正確な見え具合が分からないのです。自然の光も混ぜるようにしましょう。
・メイクの順番。
( ステップ 0 )手を洗ってスキンケア
( ステップ 1 )化粧下地
( ステップ 2 )ファンデーション
( ステップ 3 )アイメイク
( ステップ 4 )眉
( ステップ 5 )チーク
( ステップ 6 )リップ
・脇をきゅっと締めるだけで、手先は、器用になる。
・ベースメイクの基本的な順番。
(1) 日焼け止め
(2) 化粧下地
(3) コント ロールカラー
(4) リキッド タイプのファンデーション
(5) コンシーラー
(6) パウダータイプのファンデーション
(7) フェースパウダー
・顔色に悩んだときは、コントロールカラー
• 顔色が悪いときには、赤のコントロールカラー
• 赤ら顔には、緑のコントロールカラー
赤と緑は補色関係にあり、混ざると黄色になります。
• くすんだ顔には、黄色のコントロールカラー
顔がくすんで、透明感や光沢が失われているときは、黄色のコントロールカラーです。
・ファンデーションは、均一に塗らない
「ファンデーションは、骨格の高いところは厚く塗り、低いところは薄く塗る」
たとえば 、頬骨や鼻など 骨格の高い部分には厚く塗ることで、より高く見えてきます。
一方、フェースラインや目のくぼみなど 、骨格の低い部分には薄く塗ることで、より低く見えてきます。
ファンデーションを外に向けて、伸ばす。
額、鼻、顎先の 3 点にファンデーションをつけて、指先を使い、外側に向けて伸ばします。
自然なグラデーションに仕上がるよう、ゆっくり丁寧に伸ばしていきましょう。
(1) 両頬
リキッド タイプのファンデーションの場合、顔の広い部分から塗り始めます。
一番たくさんつけるべき頬は 、中指の先から第 3 関節までファンデーションを取ります。
内側から外側に向けて伸ばしていきましょう。
(2) 額
ファンデーションを手に取る量は、中指の先から第 2 関節までです。
(3) 目元・鼻・口元の細かい部分
ファンデーションと手に取る量は、中指の先から第 1 関節までです。
目元・鼻・口元の細かさに応じて、人さし指や小指などを使い分け、上手に仕上げていきましょう。
・パウダータイプのファンデーション
( ステップ 1 )スポンジの先を使って、鼻や目から塗り始める
まず、鼻と目から始めましょう。最初は、スポンジのかどだけを使います。
スポンジを 2 つ折りにすると、鼻の谷間や目の細かな部分に食い込ませることができ、塗りやすくなります。
( ステップ 2 )スポンジ 4 分の 1 を使って、額に塗る
次に、額です。
ファンデーションをつける範囲を、スポンジの 4 分の 1 まで広げて、額に伸ばしていきましょう。
( ステップ 3 )頬の目安は、片頬でスポンジ 2 分の 1
最後に、頬とフェースライン全般です。
ファンデーションをつける範囲を、スポンジの 2 分の 1 まで広げて、正面の頬から脇に向けて滑らせていきます。
顎も含めたフェースラインにも、スポンジを滑らせていきましょう。
塗り方が均一にならないよう正面から奥に向けて、厚みに変化を持たせると、自然な立体感が出てきます。
・肌の欠点は、ファンデーションで隠そうとせず、
コンシーラーを使う 。
にきび、にきび跡、しみ、目の下のくま、けがの跡。肌の欠点を隠すとき、ファンデーションではメイクの仕上がりが不自然になります。
コンシーラーは、品質より、色を重視する。
・アイメイクを仕上げる、理想的な順番。
「ビューラー→アイライン→マスカラ→アイシャドー」
・ビューラー
( ステップ 1 )手鏡を、机に置く
( ステップ 2 )まつげの付け根から、ビューラーをしっかり当てる
( ステップ 3 )ビューラーを動かすのではなく、顎を引く
( ステップ 4 )ビューラーで挟んだ状態を、5 秒間、キープする。納得のいくカールが整うまで、繰り返します。
( ステップ 5 )付け根、中間、毛先の順でカールさせる
( ステップ 6 )中間より先は、ホットビューラーを使う
ホットビューラーをまつげの毛先にそって、半回転するように使えば 、カールをうまく固定させることができます。
・センスのあるマスカラの上手な塗り方。
( ステップ 1 )上まつげから塗り始める。まつげの付け根から毛先に向けて、つけていきます。
単に真上に向けて上げるのではなく、花びらのように、まつげが放射状になるように仕上げるようにしましょう。
( ステップ 2 )縦にしたマスカラを、目尻から目頭に向けて滑らせ、毛先だけつけていきます。
( ステップ 3 )マスカラを横にした状態で、付け根から下に伸ばします。
・アイシャド ーに慣れないうちは、ブラウン系で練習しよう。
・きれいに仕上がりやすい上手な眉の描き方。
( ステップ 1 )眉山から眉尻にかけて、描く
( ステップ 2 )眉山から眉頭にかけて、描く
眉山から眉頭にかけて描くと、眉のイメージの変化を確認しながら描くことができるため、失敗しにくくなるのです。
( ステップ 3 )眉頭を丁寧に仕上げる
眉頭は、最終的な眉のイメージを確認しながら、時間をかけて描きましょう。
ぼかしながら仕上げると、自然に見えます。
・眉マスカラの発色と持ちがよくなる、上手な塗り方。
( ステップ 1 )眉尻から眉頭に向けて、マスカラを塗る
まずティッシュの上で、軽くマスカラを落としてから塗り始めます。
( ステップ 2 )眉頭は、上から下に向けて塗る
眉の生え方に逆らって眉尻から眉頭に塗り終えれば 、次は眉頭です。
( ステップ 3 )眉頭から眉尻に向けて、マスカラを塗る
マラソンで往復するかのように、眉頭から眉尻に向かって塗ります。
マスカラを塗りつつ、眉の毛並みも整えましょう。
( ステップ 4 )仕上げは綿棒で整える
最後の仕上げは、綿棒です。
眉の輪郭に余分なマスカラがついていれば 、綿棒の先を使って取り除きま
しょう。
・口をE（いー）にして、口紅を塗る
・口紅のきれいな塗り方。
( ステップ 1 )上品さを意識しながら、上唇中央の輪郭から、塗る
( ステップ 2 )左右の口角から上唇中央に向けて、塗る
( ステップ 3 )ボリューム感を意識しながら、下唇の中央を塗る
( ステップ 4 )左右の口角から、下唇中央に向けて、塗る
( ステップ 5 )必要に応じて、グロスで仕上げる
Temporal Causality for the Analysis of Visual Event
画像の時系列HoG, HoFをクラスタリングして、それが発生する回数に関するポアソン点過程の共起行列を因果性解析して、因果的に独立なクラスタをパーティション分けする。
(1) space-time visual words based on their temporal cooccurrences
(2) temporal causal analysis
http://tanichu.com/wp-content/themes/tanichu/data/pdf/ssi10_hamahata.pdf
模倣学習のまとめ、ノンパラメトリックベイズ法を用いた階層ディクリレHMM、sticky HDP-HMMで。
とても良くまとまっていて読みたい。
http://www.jaist.ac.jp/ks/skl/papers/sig-skl-20080916-3.pdf
k-meansによる運動分節化
諏訪正樹: 身体知獲得のツールとしてのメタ認知的言語化,人工知能学会誌, Vol.20,No.5,pp.525-532(2005)
変数の発見とそれらの関係性が能力向上に重要。
T. Taniguchi, N. Iwahashi, K. Sugiura, and T. Sawaragi. Constructive approach to role-reversal imitation through unsegmented interactions. Journal ref: Journal of Robotics and Mechatronics, Vol. 20, No. 4, pp. 567–577, 2008.
SARMという手法による模倣。運動をより細かい列に分解し、それをガウス分布、線形モデルでモデル化する。
高野先生の特徴HMMによる予測可能性と同列に紹介されていた。
http://www2.kokugakuin.ac.jp/~yshibata/bunsetuka/bunsettuka.htm
子供の運動文節化
身体運動の分節化と認識
http://staff.aist.go.jp/toru-nakata/MChopDD/motionchopper.pdf
模倣の哲学
http://www.bewegung.jp/htm/DB/JN/J19/19-02.pdf
a.h
#pragma once
#warning test
a.c
#include “a.h”
#include “a.h”
#include “a.h”
main(){}
うまく動きました。
1. virtual destructor
destructorは継承される可能性があるなら必ずvirtualをつける。
2. compoundするとaccessorが大変なことになる問題。(m_algorithm.getData(i))->at(j)なんてやってられない。
(a) 参照一時変数に取っておいて、名前をわかりやすくして参照する。
(b) at(i, j)みたいなものを定義してやる。
のどちらかで解決する。
3. 副作用がインスタンスを生成する場合
(a) 副作用がインスタンスを生成するのを見過ごして、関数とデストラクタで責任を持つ。
(b) 生成するインスタンスを管理するクラスを作って、そのクラスの実体メンバ変数を用意し、副作用を実体への書き込みにする。
(c) 生成するインスタンスを呼び出し元に返してしまい、それをパラメータとして使うようにお願いする。
4. namespaceとstatic member functionについて
namespaceは宣言をファイルで分割出来る。static member functionは継承状態を利用できる。
汎用的なツールはnamespaceに突っ込んで置いた方がよい。(e.g. include OpenGL)
筋肉の働きについてのわかりやすい動画がいっぱい。
http://physitheraresearch.blogspot.jp/2011/05/stretch-reflex.html
筋伸長反射
伸ばされた筋肉を戻す方向の調整的な反射
http://tanichu.com/wp-content/themes/tanichu/data/pdf/ssi10_hamahata.pdf
模倣学習のまとめ、ノンパラメトリックベイズ法を用いた階層ディクリレHMM、sticky HDP-HMMで。
とても良くまとまっていて読みたい。
http://www.jaist.ac.jp/ks/skl/papers/sig-skl-20080916-3.pdf
k-meansによる運動分節化
諏訪正樹: 身体知獲得のツールとしてのメタ認知的言語化,人工知能学会誌, Vol.20,No.5,pp.525-532(2005)
変数の発見とそれらの関係性が能力向上に重要。
T. Taniguchi, N. Iwahashi, K. Sugiura, and T. Sawaragi. Constructive approach to role-reversal imitation through unsegmented interactions. Journal ref: Journal of Robotics and Mechatronics, Vol. 20, No. 4, pp. 567–577, 2008.
SARMという手法による模倣。運動をより細かい列に分解し、それをガウス分布、線形モデルでモデル化する。
高野先生の特徴HMMによる予測可能性と同列に紹介されていた。
http://www2.kokugakuin.ac.jp/~yshibata/bunsetuka/bunsettuka.htm
子供の運動文節化
身体運動の分節化と認識
http://staff.aist.go.jp/toru-nakata/MChopDD/motionchopper.pdf
模倣の哲学
http://www.bewegung.jp/htm/DB/JN/J19/19-02.pdf
生体は60兆個、200種類の細胞と生体マトリクスで出来ている。
構築modeling→成長
再構築remodeling→吸収、形成、萎縮、肥大
環境、病的(外的、内的)変化に対するadaptationの平衡状態としての生体
例: 圧縮応力がかかる骨は太くなり、引っ張り応力がかかる骨は細くなる→O脚などの治療
生物・メディカル情報
Molecular Biology of the Cell, Pubmed http://www.ncbi.nml.gov/sites/entrez最新の研究が全部ここに乗る。
*細胞
細胞膜：リン脂質で疎水性の構造が細胞の外側に局在している。
細胞骨格→アクチン、微小管
核: DNA→RNA＠小胞体
電子回路II
*MOSFET動作原理
http://www.nteku.com/toransistor/mos_toransistor.aspx
**ゲートに関して
ゲートはキャパシタとしてモデリングできる。
t_{ox}: 酸化膜厚
k_s: 比誘電率 (SiO_2で約4)
WL: W, LはChannelの面積
V_g: ゲートがかけた電圧
V_{TH}: しきい値←半導体による制約
V_c: チャネル中の平均的電圧
Q=\epsilon_0 k_s \frac{WL}{t_{ox}} (V_g – V_{th} – V_c)
**ソース、ドレイン間電圧に関して
電圧をかけると電子は速度vで動く。
\mu: 移動度
v = \mu E = \mu \frac{V_{ds}}{L}
\Delta t = L / v: チャネル中の電荷がそっくり入れ替わる時間
Q = I \Delta t
I = \frac{Q}{\Delta t}
**組み合わせると
I = \mu c_{ox} \frac{W}{L} (V_g – V_{TH} – \frac{1}{2} V_{DS})
= \mu (\epsilon_0 k_s / t_{ox}) \frac{W}{L} (V_g – V_{TH} – \frac{1}{2} V_{DS})
故に、ゲート-ソース間電圧に関して放物線の挙動を示す。
最大値はV_{DSMAX} = V_g – V_{TH}で\mu c_0 \frac{W}{L} \frac{V_{DSMAX}}{2}。
デザインするときは普通、W, Lを変更する。
\muはシリコンとかの材料を頑張ると変えられる。
k_sはハフニウムを混ぜると…などプロセスエンジニアが設計する。
**FETから取る電流の調整方法
FETを直列にすると電流は1/2倍
FETを並列にすると電圧は2倍
**設計方法
ダイオードとMOSFETのDs-Diグラフの交点として表される。