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

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

AtCoderチャレンジまとめ(3) - NIKKEI Programming Contest 2019

f:id:robonchu:20190127185505p:plain

やりたいこと

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

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

チェレンジコンテスト

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder

問題A : Subscribers

私たちは、新聞の購読に関する調査を行いました。 具体的には、調査の対象者 N 人に対し、それぞれ次の 2つの質問を行いました。

質問 1 : あなたは新聞 X を購読しているか?

質問 2 : あなたは新聞 Y を購読しているか?

その結果、質問 1 に対して「はい」と回答した人の数は A 人、質問 2 に対して「はい」と回答した人の数は B人でした。

このとき、調査の対象者のうち新聞 X, Y の両方を購読している人の数は最大で何人であり、また最小で何人であると考えられるでしょうか?

この問いに答えるプログラムを書いてください。

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

N

A

B

自分の回答

    #include<iostream>
    using namespace std;
     
    int main(){
      int a,b,c;
      cin >> a >> b >> c;
      int amax;
      int amin;
      
      if(a >= b+c){
        amin = 0;
      }else{
        amin = b+c - a;
      }
      amax = min(b,c);
      cout << amax << " " << amin << endl;

      return 0;
    }

問題B : Touitsu

三つの文字列 A,B,C が与えられます。これらはそれぞれ、英小文字からなる長さ Nの文字列です。

私たちの目標は、これら三つの文字列をすべて等しくすることです。そのために、あなたは次の操作を繰り返し行うことができます。

操作: 文字列 A,B,Cのうち一つを選び、さらに 1 以上 N 以下の整数 i を指定する。そして、選んだ文字列の先頭から i文字目を別の何らかの英小文字に変更する。

目標を達成するためには最小で何回の操作が必要でしょうか?

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

N

A

B

C

自分の回答

    #include<iostream>
    #include <set>
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      
      string s1,s2,s3;
      cin >> s1 >> s2 >> s3;
      
      int ans=0;
      for(int i=0;i<n;i++){
        set<int> values;
        values.insert(s1[i]);
        values.insert(s2[i]);
        values.insert(s3[i]);
        ans += values.size() - 1;
      }
      cout << ans << endl;

      return 0;
    }

問題C : Different Strokes

高橋くんと青木さんの前に N 皿の料理が置かれています。 便宜上、これらの料理を料理 1、料理 2、…、料理 Nと呼びます。

高橋くんが料理 iを食べると彼は Ai ポイントの 幸福度 を得ます。 また、青木さんが料理 i を食べると彼女は Biポイントの幸福度を得ます。

彼らは、高橋くんから始めて交互に、料理を 1皿ずつ選んで食べることを料理が尽きるまで続けます。 ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか?

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

N

A1

B1

:

AN

BN

自分の回答

    #include <iostream>
    #include <vector>
    #include <algorithm> 
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      
      int a[n],b[n];
      for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
      }
      
      std::vector<int> vec(n);
      long sumao=0;
      for (int i = 0; i < n; ++i) {
        vec[i] = a[i] + b[i];
        sumao += b[i];
      }
      
      std::sort(vec.begin(),vec.end(),std::greater<int>()); //降順ソート
      
      long sumta=0;
      for(int i=0;i<n;i++){
        if(i % 2 == 0){
          sumta += vec[i];
        }
      }
      cout << sumta - sumao << endl;

      return 0; 
    }

longで足りないこともあるから、競プロの人はlong longを使っている人が多い。

問題D : Restore the Tree

N 頂点の根付き木 (注記を参照) があり、その頂点には 1 から N までの番号が振られています。 根以外の各頂点には、その親から一本の有向辺が伸びています。 なお、根は頂点 1とは限りません。

高橋くんは、このグラフに M本の新たな有向辺を書き加えました。 書き足された各辺 u→v は、ある頂点 u からその子孫であるような頂点 vに向かって伸びています。

高橋くんが辺を書き加えたあとの N頂点 N−1+M 辺の有向グラフが与えられます。 より具体的には、N−1+M 組の整数のペア (A1,B1),...,(AN−1+M,BN−1+M) が与えられ、これらは i 番目の辺が頂点 Ai から頂点 Biに向かって伸びていることを表します。

元の根付き木を復元してください。

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

N

M

A1

B1

:

AN−1+M

BN−1+M

自分の回答

TDB
時間ができたら追記します。

参考: 有向非巡回グラフ(DAG)の意味とトポロジカルソート - 具体例で学ぶ数学

所感

やっぱりD問題が難しい。今回はトポロジカルソートを知らないと結構キツい。。。

D問題を解けるように頑張る!

AtCoderチャレンジまとめ(2) - AtCoder Beginner Contest 116

f:id:robonchu:20190127185505p:plain

やりたいこと

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

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

チェレンジコンテスト

AtCoder Beginner Contest 116 - AtCoder

変数名適当でごめんなさい。。。初めてのAtCoder

問題A : Right Triangle

直角三角形 ABC があります。∠ABC=90°

です。

三角形 ABC の三辺の長さである |AB|,|BC|,|CA| が与えられるので、直角三角形 ABC

の面積を求めて下さい。

ただし、三角形 ABC の面積は整数となることが保証されています。

自分の回答

    #include<iostream>
    using namespace std;
     
    int main(){
      int a,b,c;
      cin>>a>>b>>c;
      int ans;
      ans = a*b/2;
      cout << ans << endl;
      
      return 0;
    }

問題B : Collatz Problem

数列 a={a1,a2,a3,......}

は、以下のようにして定まります。

初項 s

は入力で与えられる。

関数 f(n) を以下のように定める: n が偶数なら f(n)=n/2、n が奇数なら f(n)=3n+1。

i=1のとき ai=s、i>1 のとき ai=f(ai−1)である。

このとき、次の条件を満たす最小の整数 m

を求めてください。

am=an(m>n)

を満たす整数 n が存在する。

自分の回答

        #include<iostream>
        #include <set>
         
        using namespace std;
         
        int main(){
          int a;
          cin>>a;
          
          set<int> values;
          int ans = a;
          
          for(int i=0; i < 100000000; ++i){
            values.insert(ans);
            if(ans%2==0){
              ans = ans / 2;
            }else{
              ans = 3 * ans + 1;
            }
            if (values.size()!=i+1){
              break;
            }
          }
          cout << values.size() + 1 << endl;
          return 0;
        }

先生の回答

            #include<iostream>
            #include <set>
             
            using namespace std;
             
            int main(){
              int a;
              cin>>a;
              
              set<int> values;
              int ans = a;
              
              while(values.count(ans) == 0){
                values.insert(ans);
                if(ans%2==0){
                  ans = ans / 2;
                }else{
                  ans = 3 * ans + 1;
                }
              }
              cout << values.size() + 1 << endl;
              return 0;
            }
  • setのcountを使って重複があるかどうかを調べている(values.count(ans) == 0)。こっちのほうがイイね!

問題C : Grand Garden

花壇に N 本の花が咲いており、それぞれ 1,2,......,N と番号が振られています。最初、全ての花の高さは 0 です。 数列 h={h1,h2,h3,......} が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k(1≦k≦N) に対して花 k の高さを hk

にしたいです。

整数 l,r

を指定する。l≦x≦r を満たすすべての x に対して、花 x の高さを 1 高くする。

条件を満たすための最小の「水やり」操作の回数を求めてください。

先生の回答

            #include<iostream>
            using namespace std;
             
            int main(){
              int n;
              cin>>n;
              
              int a[n];
              for(int i=0; i < n; i++){
                cin>>a[i];
              }
              
              int ans = 0;
              int active = 0;
              for(int i;i<n;i++){
                if(active>=a[i]){
                  active = a[i];
                }else{
                  ans += a[i]-active;
                  active = a[i];
                }
              }
              cout << ans << endl;
              return 0;
            }

とてもシンプル!素晴らしい。

問題D : Various Sushi

N 個の寿司があり、それぞれの寿司には「ネタ」ti と「おいしさ」di のパラメータが設定されています。 あなたはこの N 個の寿司の中から K

個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。

    「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
    「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
    「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x

としたとき、x∗x

    である。

あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。

回答

TBD
時間あるとき追記します〜

所感

D問題解けるようになりたい。

AtCoderチャレンジまとめ(1)

f:id:robonchu:20190127185444p:plain

やりたいこと

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

そんなわけでAtCoderにチャレンジ ! の前の準備笑

教科書

けんちょんさんわかりやすい記事ありがとうございます!

計算オーダー

  • 名言 : 標準ライブラリがあっても、中身の計算量を意識しよう! ex: list (Python) からの検索処理は遅い

  • 計算回数の目安: 1秒間で処理できる for 文ループの回数は、100,000,000 回程度(10の8乗)

  • 計算時間の比較: logn < n < nlogn < n2 < n3 < 2n < n!

    • 実用的なレベルとして、n3あたりが限界

全探索

  • 幅優先探索 : グラフ を始点から近い順に1つずつ調べていく探索法

    • 深い階層まで一本道で探索する場合は幅優先探索が有用。 ex: 迷路でスタートからゴールにたどり着きたいケース
  • 深さ優先探索 : ある状態から始めて、遷移できなくなるまで状態遷移を続け、遷移できなくなったら一つ前の状態に戻って・・・を繰り返すことで、 グラフ の全頂点を漏れなく調べる探索法

    • 1つの階層に大量のノードが存在する場合は深さ優先探索が有用。 ex: 辞書順で最初の解を求めるケース

があり、どちらを選択するかは問題に依る。

ソート

  • 既存のライブラリの性能が高い。 ex: C++ の std::sort() はクイックソートをベースとしながらも最悪時の計算量も O(nlogn)O(nlog⁡n) になっている

    • C++の場合、STL をインクルードし、std::sort() でOK
  • 安定ソート : 同等なデータのソート前の順序が、ソート後も保存されるもの

  • ソート種類

    • 挿入ソート : 基本的にはそんなに速くない安定ソート。
    • マージソート : 高速な安定ソート。
    • クイックソート : 安定ソートでないが高速。C++ の std::sort() もクイックソートがベース。
    • ヒープソート : 最小値や最大値を常に取り出せるようなアルゴリズムで、安定ソートではない。

参考: ソートを極める! 〜 なぜソートを学ぶのか 〜 - Qiita

bit演算

  • 45をbitで表すと? : 0b00101101(0bは二進数を表す)

  • AND : int a,b; cout << a&b << endl;

  • OR : int a,b; cout << a|b << endl;

 &   ビットごとの AND
 |  ビットごとの OR
 ^  ビットごとの XOR
 ~  ビットごとの反転(1 の補数)
 <<   左シフト
 >>   右シフト
  • bitsetsで出力 : int a,b; cout << bitset<8>(a&b) << endl; // 00001001のように表示される

  • a ,b ,c 番目のフラグが立っている状態 : (1<<a) | (1<<b) | (1<<c)

  • マスク演算 : bit & mask ; // mask で表された部分の情報のみを取り出したもの

所感

次は練習問題をいろいろ解いてみよう。 D問題普通に難しい。。。

今後の勉強予定

k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita

AtCoderチャレンジまとめ(0)

https://secure-dcdn.cdn.nimg.jp/nicochannel/material/design/2504203/logo2.png

やりたいこと

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

そんなわけでAtCoderにチャレンジ ! の前の準備笑

教科書

けんちょんさんわかりやすい記事ありがとうございますm( )m

A問題の学び

  • 問題分をよく読んで出力形式には注意すること。ex: cout << a << " " << b << endl;の" "を書き忘れる etc ...。

  • (プロコンの場合)変数名はシンプル。タイピング速度重視。

  • 一行でかけるときはまとめる。 ex: if (c % 2 == 0) cout << "Even" << endl;

  • stringを受けて文字にアクセスするときはこう↓

string s;
cin >> s;
int counter = 0;
if (s[0] == '1') ++counter;

・ ++i の作用は式の値として、i + 1 の値を返す事、副作用は i に i + 1 の結果が代入される。

・ i++ の作用は式の値として、i の値を返す事、副作用はその後 i に i + 1 の結果が代入される。

B問題の学び

#include <algorithm>
int N; 
int a[100];

// a[0:N] を大きい順にソート
sort(a, a + N, greater<int>());
    #include <set>
    ...
    set<int> values; // insert するときに重複を取り除いてくれます
    for (int i = 0; i < N; ++i) {
        values.insert(d[i]); // 挿入します
    }
  • 最大最小もよく使う。
const int lower = max(A,C);
const int upper = min(B,D);
  • 計算の工夫として、N!のSで割った余りを求めたい時は、オーバーフローを防ぐため、N! % Sより、(N%S) * ((N-1)%S)* ・・・としたりする。

  • a以上b以下の整数のうち条件を満たすものの個数を求める問題ではf(n) := 0以上n以下の整数のうち条件を満たすものの個数のように関数定義するとf(b)-f(a-1)で求めることができる。

C問題の学び

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

感想

めっちゃ楽しい :D

今後の勉強予定

温湿度・気圧センサモジュールを動かしてみる

http://akizukidenshi.com/img/goods/C/K-09421.jpg

やりたいこと

BOSCH BME280センサを動かしてみる

購入先

教科書

準備

  1. ブレッドボード

  2. ジャンパピン

  3. プルアップ用抵抗(10kΩ)x 2

  4. Arduino Nano (Uno)

  5. BME280

配線の仕方

  • VCC(3.3Vへ)
  • GND(GNDへ)
  • SCL(SCK) <- プルアップ抵抗10kΩをはさむ
  • SDA(SDI) <- プルアップ抵抗10kΩをはさむ
  • CSB(3.3Vへ)
  • SDO(GNDへ)

http://trac.switch-science.com/raw-attachment/wiki/BME280/s-BME280_12.jpg

f:id:robonchu:20181210210434p:plain

https://i.stack.imgur.com/GB2hw.jpg

書き込むコード

BME280 – スイッチサイエンスに記載のコードBME280_I2C.inoをそのまま使用

結果

f:id:robonchu:20181210211113p:plain

所感

だいたいあってる。安いし、そこそこの値をとるにはバッチリだと思う。

さすがBOSCH :)

参考

ブログ

ライブラリ

サーモカメラOWLIFTを動かしてみる

http://www.infinitegra.co.jp/owlift/product2.jpg

http://www.infinitegra.co.jp/owlift/sample_photo1.jpg

やりたいこと

サーモカメラOWLIFT Type-AをLinuxで動かす

事前の環境設定

python3

python3のライブラリのみなので、python3環境を用意しておく

既存環境を汚したくない場合、例えばvirtualenvを利用する

$ sudo apt-get install virtualenv
$ virtualenv -p python3 "my_env"
$ source my_env/bin/activate

抜けたいときは

$ deactivate

参考: venv: Python 仮想環境管理 - Qiita

opencv

$ pip install opencv-python

OWLIFTライブラリのインストール

python library

以下からwhlファイルをダウンロード

以下コマンドでインストール

$ pip3 install owlift-xxx.whl

その他

参考: インフィニテグラ株式会社 | 小型サーマルカメラ OWLIFT

APIドキュメント

サンプルコード

以下からダウンロード

実行結果

USBでカメラをPCを繋いで以下を実行

$ python preview_basic.py

暖房を入れた時のエアコンの吹き出し口が熱を持っていることがわかる↓

f:id:robonchu:20181208143230p:plain

蛍光灯に向けるとこんな感じ↓

f:id:robonchu:20181208143706p:plain

所感

バイスやセンサごとに特性があって面白い♪

WideResNetのお勉強

https://image.slidesharecdn.com/presentationslideshare-170919153832/95/deep-learningchainer-83-638.jpg?cb=1507530330

やりたいこと

Wideなネットワークについて理解を深めたい

内容理解

教科書: Residual Network(ResNet)の理解とチューニングのベストプラクティス - DeepAge

スキップコネクションでDeepなネットワークの学習が可能に。

https://deepage.net/img/resnet/bottleneck_architecture.jpg

BatchNormは下図の左を用いるとよい。

https://deepage.net/img/resnet/bn_pos.jpg

activationの位置に関して下図の右の方が良い結果に。

https://deepage.net/img/resnet/post_vs_pre.jpg

WideResNetはこのResNetのフィルタ数を増やすことで、GPUを活用し、浅いネットワークで同等の表現力を持つように改良したもの。kが広さの係数。

https://deepage.net/img/resnet/wide_param.jpg

Dropoutの入れ方。

https://deepage.net/img/resnet/wide_resnet.jpg

実装参考

わかりやすいブログや資料

https://image.slidesharecdn.com/resnetvariant-170221133435/95/convnetresnet-11-638.jpg?cb=1487684306

https://image.slidesharecdn.com/presentationslideshare-170919153832/95/deep-learningchainer-83-638.jpg?cb=1507530330

Global Average Pooling (GAP)

教科書: Global Average Pooling(GAP)を理解してみる - Qiita

通常の全結合

https://camo.qiitausercontent.com/c41fe18f1d26e1a864cb047d3b3c5f4896c3c996/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f3133303737312f66343965666537352d306139662d313433642d383633342d3962376330663561343061332e706e67

GAP

https://camo.qiitausercontent.com/f1b0f5ebf5e574f6eecd31a9e8066bb81b1d35d8/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f3133303737312f38386431313561332d663463342d663032312d653062342d6632633737616135326266662e706e67

実装参考

参考ブログ

所感

計算資源や学習対象によって適切なネットワークを選択できるようになりたい!