空飛ぶロボットのつくりかた

ロボットをつくるために必要な技術をまとめます。ロボットの未来についても考えたりします。

Sim2Real論文まとめ(2) - PixelDomainAdaptation

f:id:robonchu:20190303135127p:plain

やりたいこと

実データを取得するのが大変なので、限られたデータからDomain Adaptationがしたい。

そのために有用そうなUnsupervised Pixel-Level Domain Adaptation with GANを理解する。

論文について

arxiv.org

  • presented at CVPR 2017

  • Google Brainの論文

評価

☆☆☆☆(4/5)

ロス関数の作り方やGANを安定させるための工夫が参考になる。

内容まとめ

Abstract

  • 品質のいいアノテーション付きのデータセットを作るのはとても大変

  • 解決策として、人工的にデータによる自動アノテーションすることが考えられるが、生成モデルが現実世界に適合できないことも多い。

  • 本論文では、画像空間においてあるドメインから対象とするドメインに適応させる教師なしのGANのアプローチを提案する。

Introduction

  • ImageNetなどのアノテーション付き大規模データセットは認識技術の向上に大きく貢献した。

  • 一方でデータの作成がとても大変だという課題がある。

  • ここで、人口的に作成した画像で代替できればよいが、それだけで訓練したモデルでは実画像に対して適用できないことが多い。

  • ひとつの解決策として、教師なしのDomain Adaptationがある。

  • つまり、ラベル付けされたあるDomainからラベル付けされていない対象Domainへ学んだ知識を転移させたい。

  • 本論文では元の特徴量を保持しつつ、あるDomainの画像をまるで対象のDomainであるように見映を変化させるようなモデルを提案する。

  • Pixelレベルでの教師なしのDomain Adaptationであり、PixelDAと呼ぶ。既存技術に対し様々な利点がある。

f:id:robonchu:20190302232505p:plain

上図からわかるように対象Domainに近い見映の画像が生成さえれている。

以下に簡単に提案手法の特徴を述べる。

Decoupling from the Task-Specific Architecture
  • 一般的なDomain AdaptationではDomain Adaptationのプロセスとタスク(Classification or Detection etc ..)特有の構造が絡み合っている。

  • これに対してPixelDAではDomain Adaptationの構成を再学習することなしに、タスク特有の構造を変えることができる。

Generalization Across Label Spaces
  • PixelDAはタスク固有部分とdomain adaptation部を非干渉化できているので、訓練時とテスト時で異なるlabel spaceを扱うことができる
Training Stability
  • GANを利用したDomain Adaptationは初期状態に影響を受けやすい。

  • この対策として、ソース画像と生成画像を用いた損失関数による訓練とピクセル類似度による正則化によって安定性を向上させる。(詳細後述)

Data Augumentation
  • これまでの一般的なDomain Adaptationdeは有限のソースとターゲットデータからの学習に限られる。

  • 提案モデルはソースデータと確率ノイズベクターによる条件付けによって、制限なく仮想的にターゲットDomainから似た画像を生成することができる。

Model

  • PixelDAは汎用的に使用可能だが、説明のため画像の classificationを例に説明を行う。

  • この論文のゴールは、ソースDomainからターゲットDomainに対して汎化的なclassifierを訓練することである。

  • 提案モデルはタスク固有のclassificationからdomain adaptationのプロセスが分離されているので、1度adaptするとdomain adaptationすることなしに他のclassificationタスクへ適用(訓練)することができる。

  • 私たちはDomain間の差異はhigh-level(対象物のタイプや幾何的な変化etc...)というよりlow-level(ノイズや色、彩度etc...)な情報による影響が大きいと考えていることを強調したい。

  • 定式化すると

    f:id:robonchu:20190303135234p:plain

    はソースのデータセットを表現し、 xsはソース画像、ysはソースラベル。

    f:id:robonchu:20190303135259p:plain

    はGenerator functionを表し、θがパラメータでソース画像とnoise vectorであるzからfake imageであるxfを出力する。

    Generator function Gが求まると、以下のようにadaptされた新しいデータセットをつくることができる。

    f:id:robonchu:20190303135334p:plain

Learning
  • GをターゲットDomainに近い画像を生成できるようGANを用いる。

  • ソース画像xsとnoise vector zからadaptされた画像xfを生成するGを訓練する。

  • モデルは、ターゲットDomainからサンプルされた画像かどうかの尤度dを出力するdiscriminator func Dによって補強される。

  • Discriminatorはgeneratorから作られたfake画像かターゲットDomainからとってきたreal画像かを見分けようとする関数である。

  • ここで大事なことが、一般的なGANはnoise vectorのみに制限付けられているのに対して、提案モデルはnoise vectorとソースDomainからの画像の両方に制限付けられている、ということである。

  • なので、ゴールは以下のmin-max gameを最適化することである。

    f:id:robonchu:20190303135357p:plain

    αとβは重みで、LdはターゲットDomainに近づけるためにloss funcでLtはタスクをこなすためのloss funcである。

  • Ldは以下のようにかける。DとGのmin-max game。

    f:id:robonchu:20190303135413p:plain

  • Ltは以下のようにかける。classificationの場合の典型的なsoftmax cross-entropy lossを用いている。

    f:id:robonchu:20190303135437p:plain

    ここで、Gで生成した画像とソース画像の両方を用いてTを訓練しているのは訓練を安定させるため。これによって、初期値依存性が減り安定性が大きく向上した

    f:id:robonchu:20190303123809p:plain

    実装したモデルは上図参照。min-max gameでの最適化時は2つのステップに分かれている。

    1. generatorのθGを固定した状態で、discriminator とタスク特徴のパラメータθDとθTを更新する。

    2. パラメータθDとθTを固定した状態で、θGを更新する。

Content-similarity loss
  • low-levelの画像のadaptationについて、前景と後景に対して処理をするのが良いという知見がある。

  • そこでラベル付けされた情報の類似性を保つために前景と後景を切り分けるz-buffer maskを用いて工夫を行う。

  • その工夫とは前景のpixelのみソース画像とgenerate画像の間の大きな差異にペナルティを与えるlossを新たに追加するというものである。

  • これによって、min-max gameの最適化がより安定する。

  • まとめると以下のようにloss関数を表現できる。

    f:id:robonchu:20190303135508p:plain

    αとβとγは重みで、Lcは類似度を一定に保つようなcontent-similarity lossである。

  • このloss func Lcinputとoutputの全体の差ではなく、pixelごとの差に対してpenaltyを与えるmasked pairwise mean squared error(masked-PMSE)を用いる。以下のように表現でき、generateされた前景画像とソース前景画像に対して、計算される。

    f:id:robonchu:20190303135532p:plain

    mはbinary maskでkはkはinput xのpixle数でL2ノルㇺをとっている。

  • これによって対象物の全体の形状など再現するための情報を保つことができる。

Evaluation

ここからは画像ベースでPixelDAを使った例を貼り付けます。

MNISTの例

f:id:robonchu:20190303135554p:plain

Linemodeの例

f:id:robonchu:20190303135619p:plain

ラベリング情報は保ちつつlow-levelな情報が様々変化している画像が生成されていることがわかる。

所感

loss関数をうまく設計することで変化させたい情報とさせたくない情報を切り分けれるのは面白い。

Domain Adaptationにおいてlow-levelの情報に着目しているのは納得。

GANを安定化させるための共有要素/普遍的な方法を検討していきたい。

C++のお勉強(3) - ポインタ/スマートポインタ

f:id:robonchu:20190303150234p:plain:w100

やりたいこと

ポインタの考え方(特にC++11)を理解し、使いこなせるようにする

ブラウザでのコード実行方法

C++ Shell がおススメ

ポインタ

型* 変数名 = オブジェクトのアドレス

  • &は変数のアドレスの取得

  • *は指定したアドレスのデータにアクセス

例1 : アドレスを利用した値の書き換え

#include <iostream>
#include <string>
using namespace std;

int main (){

  string name = "doraemon";
  string *name_address;
  name_address = &name;
  *name_address  = "dramichan";
  cout << name << endl;  // dramichan
  cout << *name_address << endl;  // dramichan
  return 0;
}

例2 : ポインタのポインタ

#include <iostream>
using namespace std;

int main(){
  string name = "atom";
  string* name_address = &name;
  string** name_address_adress = &name_address;
  *name_address = "uran";  // uran
  cout << name <<endl;  // uran
  cout << **name_address_adress <<endl;
}

スマートポインタ

スマートポインタで管理されるオブジェクトは明示的にdeleteしなくても、使われなくなったら自動的に破棄される

unique_ptr

あるメモリの所有権を持つ unique_ptrはただ一つのみ

使い方
  • #include で使える。

  • ポインタの保持するメモリにアクセスするには、operator*()や operator->()が使用可能。

  • unique_ptrは、コピーは禁止だが、ムーブは可能。

  • deleterの指定可能。

ポイント

shared_ptr

同一のメモリの所有権を複数で共有できるようにしたスマートポインタが、shared_ptr

使い方
  • #include で使える。

  • ポインタの保持するメモリにアクセスするには、operator*()や operator->()が使用可能。

  • コピーもムーブも可能。

  • deleterの指定可能。

ポイント
  • shared_ptrの初期化にmake_sharedを使うこと

  • unique_pointに比べて遅い

  • 循環参照に気をつけて!以下のような状況を指す。

#include <iostream>
#include <memory>

class Robot
{
public:
    Robot() {}
    ~Robot() {}
    
    std::shared_ptr<Robot> hand_ptr;
};

int main()
{

    std::shared_ptr<Robot> r1 = std::make_shared<Robot>();
    std::shared_ptr<Robot> r2 = std::make_shared<Robot>();

    r1->hand_ptr = r2;
    r2->hand_ptr = r1;

    return 0;
} // pointaが解放されない!
  • 循環参照はstd::weak_ptrで解決できる

weak_ptr

循環参照によって生じる問題を防ぐために導入されたスマートポインタで所有権をもたない

使い方例
#include <iostream>
#include <memory>

class Robot
{
public:
    Robot() {}
    ~Robot() {}
    
    std::weak_ptr<Robot> hand_ptr;
};

int main()
{
    std::shared_ptr<Robot> r1 = std::make_shared<Robot>();
    {
        std::shared_ptr<Robot> r2 = std::make_shared<Robot>();

        r1->hand_ptr = r2;
        r2->hand_ptr = r1;
    }  // ここでr2が解放
    return 0;
} // ここでr1が解放
ポイント
  • ダグリングポインタ(無効なメモリ領域を指すポインタ)に気をつけること!以下に例を示す。
std::shared_ptr<Robot> robot = std::make_shared<Robot>();
std::weak_ptr<Robot> weak_robot = robot;

// この間に、robotの寿命が切れるとweak_robotはダグリングポインタになってしまう
  • ここで監視しているshared_ptrオブジェクトを取得するlock関数を用いることでダグリングポインタの問題に対処できる。例えば以下のようにして不正アクセスを防ぐことができる。
if (auto r = weak_robot.lock()) {
  // こうすることで不正アクセスを防いだうえで*r に対して処理をかける
}

参考 : weak_ptr::lock - cpprefjp C++日本語リファレンス

使い分け

使用頻度としてはunique_ptr > shared_ptr > weak_ptrが理想的

  1. まず unique_ptrの利用を検討する。

  2. 複数で共有する必要のある場合、shared_ptrを利用する。

  3. 循環参照になっていないか確認し、なっている場合weak_ptrを利用する。

所感

次は右辺値・左辺値・ムーブについて理解したい。

全体参考

Sim2Real論文まとめ(1) - SimGAN

f:id:robonchu:20190225163721p:plain

やりたいこと

センサノイズをシミュレータで再現したい。

そのために有用そうなSimGANを理解する。

論文について

arxiv.org

  • CVPR2017でBest Award

  • 珍しいAppleの論文

評価 

☆☆☆☆☆(5/5)

めちゃくちゃコスパ良いアプローチ。素晴らしい。

内容まとめ

Abstract

  • 教師あり学習の難点として、たくさんのラベル付きデータが必要になる。

  • シミュレータでデータを作ることが期待されているが、シミュレータと実世界の乖離が問題で上手く行かないことが多い。

  • 本論文はその溝を埋める手法を提案する。

  • 方法としてはラベル付きのシミュレーションのデータとラベルなしの実データを用いて、Genertive Adversarial Networks(GANs)によりシミュレーションデータを実データに近づける(S+U Learning with SimGAN)

  • 以下の三点がキーポイント。

    1. a "self-regularization" term

    2. a local adversarial loss

    3. updating the discriminator using history of refined images

    これらによってリアリスティックな画像を生成することができる。

Introduction

  • シミュレータをリアルに近づけるアプローチも盛んだが、良いレンダリングアルゴリズムのものを使ったとして、実世界を完全に再現できているわけでなく、これを用いて学習した場合、過学習することもある。

  • この論文の目標はラベリングなしの実データとシミュレータを用いてリアルな画像を生成すること。

  • そのために、refinerというネットワークを考案した。下図参照。

f:id:robonchu:20190225163721p:plain

  • これはシミュレータが作った生成画像をrefineする。

  • 実データに近づけるため、refinerはadversarial lossを用いて訓練する。

  • これはGANsに似たアプローチをとっていて、実データとの区別がつかないように更新するdiscriminative networkを用いている。

  • ここで、生成データのアノテーション情報を保つため、生成データとrefineされたデータの差にペナルティを与えるようなself-regularization lossをadversarial lossに追加している

  • そして、ピクセルレベルでのfully CNNを用いることで、大域的な構造を保つ

  • GANsのアプローチは対立する2つのネットワークを訓練するため、不安定になりがち。これに対して、discriminatorの受容野を画像全体ではなく複数の局所的な領域に制限する

  • さらに安定に訓練を行うため、過去のrefineされた画像を用いてdiscriminatorの更新を行う

Contributions

  1. ラベルなしの実データを用いて合成データをrefineする(S+U learning)

  2. adversarial lossとself-regularization lossを用いてrefiner networkを訓練する

  3. refiner networkを安定して訓練するためのGANsに対するいくつかの大事な修正を行う

  4. 定性的な実験結果とSOTAな結果を示す

S+U Learning with SimGAN

  • ゴールはアノテーション情報を保持しつつ生成画像をリアルに近づけるrefinerを訓練すること。

  • 以下の2つの損失関数によって、関数パラメータθを学習によって最適化する。

f:id:robonchu:20190225170151p:plain

  • 第一項は実データに近づける作用、第二項はアノテーション情報を保つ作用がある。

  • 詳細はこれから説明。

Adversarial Loss with Self-Regularization
  • GANsに似ている提案手法は同様に2つのネットワークのminmax gameであり、refiner networkとdiscriminator nerworkを交互に更新する。
Discriminator
  • discriminator networkは以下の損失関数を最小化することによってΦを更新する。

f:id:robonchu:20190225170433p:plain

  • この式は交差エントロピー誤差で~xiが生成データ、yiが実データである。

  • Dはrefineされた画像である確率を出力する層を最終層に持つConvNetとして実装。つまり、refineであれば1、実データであれば0が理想。

  • 確率的勾配降下法によって更新する。

Refiner

f:id:robonchu:20190225170151p:plain

  • (1)式のlrealは訓練済みのdiscriminatorを用いて以下のようにかける。

f:id:robonchu:20190225171437p:plain

  • このロス関数が小さくできれば、discriminatorをより騙すようなrefinerに近づく。

  • さらに、生成されたリアルな画像はシミュレータで付与されたアノテーション情報も保ってほしい

  • これを実現するため、生成データとrefineされたデータのピクセルレベルでの違いを小さくするようself-regularization lossを用いる。

  • そうすると、(1)の式は以下にような表現になる。こおkでψは恒等関数。||はL1ノルム。

f:id:robonchu:20190225172350p:plain

  • ここでRはピクセルレベルでrefineするためプーリングなどがないfully convolutinal neural netで実装。
更新則
  • 以下の通りでR(θ)を更新する間はΦを固定、D(Φ)を更新する間はθを固定。

  • 交互に繰り返してLr(θ)とLd(Φ)を最小化する。

f:id:robonchu:20190225172824p:plain

Local Adversarial Loss
  • refinerがとても強いdiscriminatorを訓練した時、refinerが過度に特徴を強調する方向へ働くことがある。

  • ここで、局所的な状態もrefinerはリアルに近づけるべきで、同様にdiscriminatorも局所的な情報で判断できるべき。

  • 上記を踏まえ下図のように discriminatorのネットワーク出力をw x hの確率マップにし、refinerのadversarial loss関数を局所パッチのcross entropy lossesで表す

f:id:robonchu:20190225174432p:plain

Updating Discriminator using a History of Refined Images
  • discriminatorが最新のrefined imagesにのみ正しく区別できる傾向に陥ることがある。

  • これは本来すべてのrefined imagesを正しく区別したいため良くない。

  • なので、discriminatorの更新時に過去のrefined imagesも使用することで、安定性を向上させる

  • 下図のようにmini-batchの半分を最新の画像、もう半分をバッファにためていた画像を用いる。

f:id:robonchu:20190225180256p:plain

以上がSimGANのロジックの部分。

Experiments

  • ここからは画像ベースでSimGANを使った向上例をペタペタ貼り付けます。かなり汎用性がありあそう。

  • 視線方向はたもちつつ、リアルな画像へrefine↓

f:id:robonchu:20190225180926p:plain

  • より詳細↓

f:id:robonchu:20190225181104p:plain

  • 手の姿勢推定のためのDepth画像への適応例↓

f:id:robonchu:20190225181213p:plain

  • 過去の画像を使ってdiscriminatorを更新したことの効果↓

f:id:robonchu:20190225181434p:plain

  • Local adversarial loss の効果↓

f:id:robonchu:20190225181617p:plain

所感

実機でデータセットを作るのはホント大変なので、生成データとアノテーションなしの実データでSimlationとRealのGapを埋めれるのは素晴らしい。

特にセンサのノイズは個体によって異なるし、表現しにくいので、このアプローチはほんとに興味深い。

AtCoderチャレンジまとめ(6) - AtCoder Beginner Contest 119

f:id:robonchu:20190127185444p:plain

やりたいこと

C++に慣れつつアルゴリズムの知識を上げたい。

そんなわけでAtCoderにチャレンジ !

チャレンジコンテスト

atcoder.jp

変数名が適当なのはご愛嬌

A問題: Still TBD

文字列 S が入力されます。これは、西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表したものです。(例えば、2019 年 4 月 30日は 2019/04/30 と表されます。)

Sが表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S が表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力せよ。

自分の回答

#include <iostream>
using namespace std;
     
int main() {
  std::string s;
  cin >> s;
        
  char cary[10]; 
  s.copy(cary, 10);
      
  std::string sn("");
  for (int i=0;i<10;i++){
    if (i != 4) {
      if (i != 7){
        sn += cary[i];
      }
    }
  }
      
  int num = atoi(sn.c_str());
  if(num>20190430){
    cout << "TBD" << endl;
  } else {
    cout << "Heisei" << endl;
  }
  return 0;
}

B問題:

高橋くんは N人の親戚からお年玉をもらいました。

N個の値 x1,x2,...,xN と N 個の文字列 u1,u2,...,uN が入力されます。各文字列 ui は JPY または BTC であり、xi と ui が i人目の親戚からのお年玉の内容を表します。

例えば、x1=10000, u1= JPY であれば 1 人目の親戚からのお年玉は 10000 円であり、x2= 0.10000000, u2= BTC であれば 2 人目の親戚からのお年玉は 0.1ビットコインです。

ビットコインを 1.0BTC あたり 380000.0 円として換算すると、高橋くんがもらったお年玉は合計で何円に相当するでしょうか?

入力

入力は以下の形式で標準入力から与えられる。

N

x1 u1

x2 u2

:

xN uN

出力

高橋くんが受け取ったお年玉が合計で Y 円に相当するとき、値 Y(整数とは限らない) を出力せよ。

出力は、ジャッジの出力との絶対誤差または相対誤差が 10−5以下のとき正解と判定される。

自分の回答

#include <iostream>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  
  double x;
  std::string u;
  std::string str="JPY";
  
  double ans;
  
  for (int i; i<n;i++){
    cin >> x >> u;
    if (std::string(u)==str){
      ans += x;
    } else {
      ans += x * 380000.0;
    }
  }
   
  cout << ans << endl;
  return 0;
}

C問題: Synthetic Kadomatsu

あなたは N 本の竹を持っています。これらの長さはそれぞれ l1,l2,...,lNです (単位: センチメートル)。

あなたの目的は、これらの竹のうち何本か (全部でもよい) を使い、長さが A,B,Cであるような 3本の竹を得ることです。そのために、以下の三種類の魔法を任意の順に何度でも使うことができます。

延長魔法: 1

    MP (マジックポイント) を消費し、1 本の竹を選んでその長さを 1増やす。

短縮魔法: 1

    MP を消費し、1 本の長さ 2 以上の竹を選んでその長さを 1減らす。 
合成魔法: 10

    MP を消費し、2 本の竹を選んで接続し 1 本の竹とする。この新たな竹の長さは接続した 2本の竹の長さの合計に等しい。(以後、この竹に対してさらに魔法を使用することもできる。)

目的を達成するには、最小でいくつの MP が必要でしょうか?

入力

入力は以下の形式で標準入力から与えられる。

N A B C

l1

l2

:

lN

出力

目的の達成に必要な MP の最小量を出力せよ。

自分の回答

時間以内に解けなかった...Cが解けないのは辛い。

全探索大事。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
int A,B,C;

long long brute_force_search(int cnt, int a, int b, int c, int L[]) {
  long long INF = std::pow(10, 9.0);
  if (cnt==N) {
    if ((a!=0)&&(b!=0)&&(c!=0)){
      return std::abs(a-A)+std::abs(b-B)+std::abs(c-C)-30;
    } else {
      return INF;
    }
  }
  vector<long long> ansc(4);
  ansc[0] = brute_force_search(cnt+1, a, b, c, L);
  ansc[1] = brute_force_search(cnt+1, a+L[cnt], b, c, L)+10;
  ansc[2] = brute_force_search(cnt+1, a, b+L[cnt], c, L)+10;
  ansc[3] = brute_force_search(cnt+1, a, b, c+L[cnt], L)+10;
  int min = *std::min_element(ansc.begin(), ansc.end());
  return min;
}

int main() {
  cin >> N >> A >> B >> C;
  
  int len[N];
  for (int i; i<N;i++){
    cin >> len[i];
  } 
  
  long long ans;
  ans = brute_force_search(0, 0, 0, 0, len);
  cout << ans << endl;
  return 0;
}

ちょっとだけ解説

a,b,c=0の状態から始まり初期の1本追加するときに10を足しているので、

最後にABC3本分の30を引いているのと、

一本も追加しない場合は成り立たないのでINFとしてる。

D問題: Lazy Faith

東西方向に伸びる道路に沿って A 社の神社と B 軒の寺が建っています。 西から i 社目の神社は道路の西端から si メートルの地点に、西から i 軒目の寺は道路の西端から tiメートルの地点にあります。

以下の Q個の問いに答えてください。

問 i (1≤i≤Q): 道路の西端から xi メートルの地点から出発して道路上を自由に移動するとき、神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか? (必要数を超えた数の寺社を通過してもよい。)

入力

入力は以下の形式で標準入力から与えられる。

A B Q

s1

:

sA

t1

:

tB

x1

:

xQ

出力

Q 行出力せよ。i 行目に問 i への答えを出力すること。

自分の回答

これも時間以内にとけなかった。二分探索がポイント。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int main() {
  int A,B,Q;
  cin >> A >> B >> Q;
  
  vector<long long> jin(A+2);
  vector<long long> tera(B+2);
  
  long long INF = std::pow(10, 18);
  
  jin[0] = -INF;
  jin[A+1] = INF;
    
  tera[0] = -INF;
  tera[B+1] = INF;
  
  for (int i=1; i<A+1;i++){
    cin >> jin[i];
  }
  for (int i=1; i<B+1;i++){
    cin >> tera[i];
  }
  
  long long q;
  for (int i; i<Q;i++){
    cin >> q;
    long long b = upper_bound(jin.begin(), jin.end(), q) - jin.begin();
    long long d = upper_bound(tera.begin(), tera.end(), q) - tera.begin();
    
    long long ans = INF;
    vector<long long> jinv{jin[b-1],jin[b]};
    vector<long long> terav{tera[d-1],tera[d]};
    vector<long long> dv(3);

    for (auto j: jinv) {
      for (auto t: terav){
        dv[0] = std::abs(j-q)+std::abs(t-j);
        dv[1] = std::abs(t-q)+std::abs(j-t);
        dv[2] = ans;
        ans = *std::min_element(dv.begin(), dv.end());
      }
    }
    cout << ans << endl;
  }
return 0;
}

二分探索参考

所感

Cが解けずに時間が経過すると、めっちゃ焦る。。。冷静に解決のための手段を一個ずつ洗い出せるようにしないと。

まずいろんなアルゴリズムの知識を網羅的につけて正しく選択できるところを目指そう。

AtCoderチャレンジまとめ(5) - AtCoder Beginner Contest 118

f:id:robonchu:20190127185505p:plain

やりたいこと

C++に慣れつつアルゴリズムの知識を上げたい。

そんなわけでAtCoderにチャレンジ !

チャレンジコンテスト

atcoder.jp

変数名が適当なのはご愛嬌

A : A - B +/- A

正整数 A,Bが与えられます。

Aが B の約数なら A+B を、そうでなければ B−A を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

A が B の約数なら A+B を、そうでなければ B−A を出力せよ。

自分の回答

#include <iostream>
using namespace std;
    
int main() {
    int a,b;
    cin >> a >> b;
    
    if(b%a==0){
      cout << a+b <<endl;
    } else {
      cout << b-a<< endl;
    }
    return 0;
}

B : Foods Loved by Everyone

カツサンドくんはオムライスが好きです。

他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きで、これらの食べ物は全て、誰もが好きだと信じています。

その仮説を証明するために、N人の人に M種類の食べ物について好きか嫌いかの調査を行いました。

調査の結果、i番目の人は Ai1 番目, Ai2 番目, ..., AiKi番目の食べ物だけ好きだと答えました。

N人全ての人が好きだと答えた食べ物の種類数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N M

K1 A11 A12 ... A1K1

K2 A21 A22 ... A2K2

:

KN AN1 AN2 ... ANKN

出力

N 人全ての人が好きだと答えた食べ物の種類数を出力せよ。

自分の回答

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n,m;
  cin >> n >> m;

  vector<int> v;

  for(int i=0;i<n;i++){
    int a;
    cin >> a;

    for (int j=0;j<a;j++){
      int b;
      cin >> b;
      v.push_back(b);
    }
  }

  int ans=0;
  for(int i=1;i<m+1;i++){
    int n_count = std::count(v.begin(), v.end(), i);
    if (n_count==n){
      ans += 1;
    }
  }

  cout << ans << endl;
  return 0;
}

C : Monsters Battle Royale

N 体のモンスターが居て、それぞれ 1,2,...,Nと番号付けられています。

はじめ、モンスター iの体力は Aiです。

以降、体力が 1以上のモンスターを生きているモンスターと呼びます。

生きているモンスターが 1体になるまで以下を繰り返します。

  • ランダムに 1体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
  • その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。

最後に生き残ったモンスターの最終的な体力の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N

A1 A2 ... AN

出力

最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。

自分の回答

基本的に体力の小さい2つのみに着目して解けることに気づいた。

体力の小さい順にソートして、 2番目に1番小さいもので割り切れれば、最小体力は1番目のままなので、2番目を削除。

割り切れない場合は、2番目 = 2番目-1番目とし、2番目を更新する。そして、2番目が1番目を下回ったら再度sort。

以降これらの繰り返しで最後の一つが残るまで繰り返す。

#include <iostream>
#include <vector>
#include <algorithm>
    
using namespace std;
             
int main() {
    long long n;
    cin >> n;
    
    vector<long long> a(n);
    for(long long i;i<n;i++){
      cin >> a[i];
    }
              
    std::sort(a.begin(),a.end());
    while(true){
      if(a.size()==1){
        break;
      }
      if (a[1]%a[0]==0){
        a.erase(a.begin()+1);
      } else {
        a[1] = a[1] - a[0];
        if(a[1]<a[0]){
        std::sort(a.begin(),a.end());
        }
      }
    }
              
    cout << a[0] << endl;
    return 0;
}

D : Match Matching

ちょうど N本のマッチ棒を使って作れる整数の中で最大のものを求めてください。

ただし、以下の条件を満たさなければなりません。

作る整数の各桁は、1から 9 までの数字のうち A1,A2,...,AM(1≤Ai≤9)のいずれかでなければならない。

数字 1,2,3,4,5,6,7,8,9を 1 つ作るには、それぞれちょうど 2,5,5,4,5,6,3,7,6 本のマッチ棒を使う。

入力

入力は以下の形式で標準入力から与えられる。

N M

A1 A2... AM

出力

問題文の条件下でちょうど N本のマッチ棒を使って作れる整数の最大値を出力せよ。

けんちょんさんの回答の写経

いつもありがとうございます!!! そして、またしてもDが解けない。。。

教科書: AtCoder ABC 118 D - Match Matching (400 点) - けんちょんの競プロ精進記録

以下のかんたんな例を用いて動的計画法の内容を理解。

入力例:

8 2

3 7

3を作るのにマッチ5本、7を作るのにマッチ3本。なので、73が答えだとわかる。

これをけんちょんさんのDP(iはマッチの本数で dpは作れる数字が入る)で考えると

i = 0の時

    dp[5] = 3, dp[3] = 7

i =1,2の時は作れる数字がないのでスキップ

i = 3の時

    dp[3+5] = 73, dp[3+3] = 77

i = 4の時は作れる数字がないのでスキップ

i = 5の時

    dp[5+5] = 33, dp[5+3] = 73

 (*) ここで前のdp[8]に73が入っているので、37と比較して大きい73を入れる

i = 6の時

    dp[6+5] = 773, dp[6+3] = 777

i = 7の時は作れる数字がないのでスキップ

i = 8の時

    dp[8+5] = 733, dp[8+3] = 737

よってdp[8]=73より73が答えだとわかる。8本与えられたときに作れる最大の数。

以下写経コード。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const string MINUS_INF = "-";

void update_char_max(string &a, string b){
    if (a == MINUS_INF){
        a = b;
    } else if (a.size() < b.size()) {
        a = b;  // stringの比較のため、まず桁違いのものは更新
    } else if (a.size() == b.size()) {
        if (a < b) {
          a = b;  // 同じ桁のstringは純粋に値の比較
        }
    }
}

long long match_map[10] = {2,5,5,4,5,6,3,7,6};
string dp[100000];

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(m);
    for (int i=0; i<m; ++i) {
        cin >> a[i];
    }

    // 初期化
    for (int i=0; i<100000; ++i) {
        dp[i] = MINUS_INF;
    }

    // 初期条件
    dp[0] = "";

    // DP ループ
    for (int i = 0; i <= n; ++i) {
        if (dp[i] == MINUS_INF) continue;
        for (auto ae : a) {
            update_char_max(dp[i+match_map[ae-1]], dp[i]+(char)('0'+ae));
        }
    }
    cout << dp[n] << endl;
}

所感

autoが便利だし、どんどん使っていこう。

動的計画法を使いこなせるようになったら、Dの解ける問題が増える気がする。DP頑張る。

あとはちょっとした初期化の書き方だったり、読みやすくて、短いコードを意識して書いていきたい。

AtCoderチャレンジまとめ(4) - みんなのプロコン 2019

https://img.atcoder.jp/yahoo-procon2018-qual/6301a7d889fb01c0794ace9bf70f3693.png

f:id:robonchu:20190210142258p:plain

やりたいこと

C++に慣れつつアルゴリズムの知識を上げたい。

そんなわけでAtCoderにチャレンジ !

チャレンジコンテスト

Yahoo Programming Contest 2019 - AtCoder

変数名が適当なのはご愛嬌

問題A: Anti-Adjacency

1 以上 N 以下の異なる整数を、差が 1 の整数をともに選ばないように K 個選ぶことができるか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

整数を K 個選ぶことができるなら YES を、そうでないなら NO を出力せよ。

自分の回答

#include <iostream>
using namespace std;
 
int main() {
  int n,k;
  cin >> n >> k;
  
  int ans;
  ans = (n+1)/2;
  
  if(ans>=k){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  
  return 0;
}

問題B: Path

4 つの街があり、順に 1,2,3,4 と番号が付いています。 道が 3 本あり、i 本目の道は異なる街 ai,bi を双方向に結んでいます。 同じ街の対の間を結ぶ道が複数あることはありません。

街同士を行き来する手段は、道以外にはありません。 どの2つの街の間も、道を何本か通ることで行き来することができます。

すべての道をちょうど 1回ずつ通ることですべての街を訪れることが可能かどうか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

a1 b1

a2 b2

a3 b3

出力

すべての道をちょうど 1 回ずつ通ることですべての街を訪れることが可能なら YES を、そうでないなら NO を出力せよ。

自分の回答

#include <iostream>
using namespace std;

int main() {
int a1,b1;
cin >> a1 >> b1;
int a2,b2;
cin >> a2 >> b2;
int a3,b3;
cin >> a3 >> b3;

if (a1==a2 || a1==b2) {
  if(a1==a3 || a1 ==b3){
    cout << "NO" << endl;
    return 0;
  }
}

if (b1==a2 || b1==b2) {
  if(b1==a3 || b1 ==b3){
    cout << "NO" << endl;
    return 0;
  }
}

cout << "YES" << endl;
return 0;
}

解説

問題の構成から、異なる街を選ぶこと、同じ道は作らないことから、計3セットのa,bの中で同じ数字が3つない場合にすべて訪れることを発見。

つまり、3セットのすべてに同じ数が含んでいるものを除く。

問題C: When I hit my pocket...

すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K回行います。

・持っているビスケットを叩き、1枚増やす

・ビスケット A枚を 1円に交換する

・1円をビスケット B 枚に交換する

K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

K A B

出力

K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を出力せよ。

自分の回答

#include <iostream>
using namespace std;
 
int main() {
  long long k,a,b;
  cin >> k >> a >> b;

  long long ans1;
  ans1 = (k-a+1) / 2;
  ans1 = (ans1-1) * (b-a);
  ans1 = ans1 + b + (k-a+1)%2;

  long long ans2;
  ans2 = k+1;

  if(ans1 > ans2){
    cout << ans1 << endl;
  } else {
    cout << ans2 << endl;
  }
  return 0;
}

解説

A+2 < Bのときは、お金に交換→ビスケット生成がより増やせる。

そうでないときは、交換せずにビスケットを叩きまくる。

A+2 < Bのときは、基本的に最初の一回交換するまでは叩いて増やす必要があるが、その後は

・ ビスケット A枚を 1円に交換する

・ 1円をビスケット B 枚に交換する

というように2回で(B-A)個を増やすことができる。

D: Ears

数直線上にすぬけ君がいます。すぬけ君は L個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。

・座標 0未満の点や座標が Lより大きい点を通ることはない
・整数座標の点で散歩を開始し、整数座標の点で散歩を終了する
・整数座標の点でのみ、進む方向を変えることができる

すぬけ君は、座標が整数 iを用いて i−0.5 と表される点を通るたびに、i 番目の耳に石を 1個入れます。

すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各 iに対しすぬけ君の i 番目の耳には Ai個の石が入っているようにしたいです。

・すぬけ君の耳をひとつ選び、石を 1個入れる
・石が 1個以上入っているすぬけ君の耳をひとつ選び、石を 1個取り出す

すぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

L

A1

:

AL

出力

必要な操作の回数の最小値を出力せよ。

入力例

4

1

0

2

3

出力例

1

自分の回答

これは時間以内に解けなかったので、解説を見て検討しました。

#include <iostream>
#include <vector>
#include <algorithm>
  
using namespace std;
  
long long cost(long long* A, const long long& index, const long long& area){
  if (area==0 || area==4) {
    return A[index];
  } else if (area==1 || area==3) {
    if (A[index]==0) {
      return 2;
    } else if(A[index]%2==0) {
      return 0;
    } else {
      return 1;
    }
  } else if (area==2){
    if (A[index]%2==0){
      return 1;
    } else {
      return 0;
    }
  }
}
  
int main() {
  long long n;
  cin >> n;
  
  long long A[n];
  for(long long i=0;i<n;i++){
    cin >> A[i];
  }
  
  vector< vector<long long> > dp;
  dp.resize(n);
  for(long long i=0; i<n; i++){
    dp[i].resize(5);
  }
  
  for(int j=0;j<5;j++){
    dp[0][j] = cost(A,0,j);
  }
  
  for(long long i=1;i<n;i++){
    dp[i][0] = dp[i-1][0]+cost(A,i,0);
    for(int j=1;j<5;j++){
      long long mindp = *std::min_element(dp[i-1].begin(), dp[i-1].begin()+j+1);
      dp[i][j] = min(mindp+cost(A,i,j), dp[i][j-1]);
    }
  }
  
  long long ans = *std::min_element(dp[n-1].begin(), dp[n-1].end());
  cout << ans << endl;
  
  return 0;
}

解説

以下の5つにわけて、下図にあるような考え方、動的計画法(DP)で解きました。

まず、すぬけくんのスタート、ゴール位置をS,Tとし、散歩中の最小・最大位置をD,Uとします。

  1. i <= DのときはXi=0なので、この範囲のコストはAiそのまま。りんごさんはAi回操作必要。

  2. D < i <= Sのときは、Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。

  3. S < i < Tのときは、Xiが奇数ならばコスト0。偶数ならばコスト1。

  4. T < i <= Uのときも2.と同様。Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。

  5. U < iのときも1.と同様。この範囲のコストはAiそのまま。

このコストの考え方を用いて、入力例を用いて示すと

f:id:robonchu:20190210140946j:plain

のようなコストマップがかけ、緑☆のように左列と上ブロックの情報を用いてすべてのブロックが計算できる。

最後に最終列の最小値を求めればそれが答え。

問題E: Odd Subrectangles

TBD

問題F: Pass

TBD

所感

すぬけくんがバケモノ過ぎて問題解くときに焦った笑

メモ時の大量の耳がある、すぬけくん↓↓↓

f:id:robonchu:20190210141742p:plain

Eigen事始め

f:id:robonchu:20190202123719p:plain

やりたいこと

C++で行列計算を高速に行いたい!

ので、行列計算ライブラリEigenを学ぶ。

教科書

インストール

Eigen からダウンロードする。

もしくはROSが入っている場合、

/usr/include/eigen3/Eigen

にEigenがインストールされている。

コンパイル方法

g++ -I /path/to/eigen/ my_program.cpp -o my_program

Getting Started

#include <iostream>
#include <Eigen/Dense>

int main() {
  // 2行2列の行列作成
  Eigen::Matrix2d m(2,2);
  m(0,0) = 3;
  m(1,0) = 2.5;
  m(0,1) = -1;
  m(1,1) = m(1,0) + m(0,1);
  std::cout << m << std::endl;

  // 1行2列のベクトル作成
  Eigen::Vector2d v(1,2);
  std::cout << v << std::endl;

  // 上記行列とベクトルの積
  std::cout << "m * v =" << std::endl << m * v << std::endl;
}

出力

  3  -1
2.5 1.5
1
2
m * v =
  1
5.5

Dynamicに生成

以下のように記述することで行列サイズを動的に決めることができる

Eigen::MatrixXd m = MatrixXd::Random(3,3);

コンマで初期化

Matrix3f m;
m << 1, 2, 3,
     4, 5, 6,
     7, 8, 9;
std::cout << m;

便利機能まとめ

配列からEigenに変換

配列からEigenに変換するのに便利なEigen::Map

int array[8];
for(int i = 0; i < 8; ++i) array[i] = i;
cout << "Column-major:\n" << Map<Matrix<int,2,4> >(array) << endl;
cout << "Row-major:\n" << Map<Matrix<int,2,4,RowMajor> >(array) << endl;

出力

Column-major:
0 2 4 6
1 3 5 7
Row-major:
0 1 2 3
4 5 6 7

クオータニオン計算

TBD

参考なるブログ

所感

これは便利 ! 使いやすいし、多機能

背中がITAI...