プログラミング上達したい人が書くブログ

プログラミング上達したい人が書くブログ

主に、アニメやPython、C++、競技プログラミング(初心者)について書きたいです。また、１週間に一つの記事を心掛けています。学生です。備忘録と書かれたものは他人に見せることを考えて書いてないため見にくいです。

競技プログラミング プリム法編 [備忘録]

はじめに

　制限時間内に問題を解く競技プログラミングにおいて、アルゴリズムを調べるために本を読み文字を打ち込むことはとてもめんどくさいと感じたため、ここにMain関数で呼び出して使える形で残しておくことでAtCoderでやるときにコピペで使えるようにしています。

 

　下部ソースコードでは、最少全域木のコストを返している関数です。

 

　また、AOJでacceptももらいました。AOJのURLは以下に貼っておきます。

最小全域木 | グラフ | Aizu Online Judge

 

プリム法特徴

　最少全域木におけるコストの総和を求めている。

　O(V*V)でV=10000程度は対応可能

　プリム法そのものはここがわかりやすい。

 

ソースコード

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

using namespace std;
#define MV 10000
#define INF 1e9

struct edge{int to,cost;};//辺の表現方法の１種
vector <edge> G[MV];
bool used[MV];//各点を一度使ったかどうか
int V,E;//Vは点、Eは辺の個数
int d[MV];//コストを格納している
int prim(){
  
  for(int i = 0;i < V;i++){//初期化
    d[i] = INF;
    used[i] = false;
  }
  d[0] = 0;
  used[0] = true;
  
  for(int i = 0;i < G[0].size();i++)
    d[G[0][i].to] = G[0][i].cost;

  int num = 0;

  for(int j = 0;j < V;j++){
    int m = -1;
    for(int i = 0;i < V;i++){
      if(used[i] == false && (m == -1 || d[m] > d[i]))
	m = i;
    }
    if (m == -1)
      break;
    used[m] = true;
    num += d[m];
    for(int i = 0;i < G[m].size();i++)
      d[G[m][i].to] = min(d[G[m][i].to],G[m][i].cost);
  }
  return num;
}

int main(){
  int first;
  cin >> V >> E;
  for(int i = 0;i < E;i++){
    int f,t;
    edge e;
    cin >> f >> e.to >> e.cost;
    G[f].push_back(e);
    /*
      G[f]にはfからでてる辺が格納されている。
     */
    t = e.to;
    
    e.to = f;
    G[t].push_back(e);
  }

  int fl = prim();
  cout << fl << endl;
  
  
}

 

東京モーターショー 2017に行ってみた件について　Part2　Kwasaki,YAMAHA編　

イベント

はじめに

　写真ばかりで、ブログが長くなったため分けました。

　前回の「Part1 ホンダ編」のURLは以下に貼ります。

printf.hatenablog.com

 

Kawasakiのブース

　Kawasakiのバイクの展示では、Ninjaシリーズを初めて見たのですが、かなりかっこよかったです。

　Ninja ZX-10RRというバイクになります。

f:id:sachishimei:20171101114534j:plain

f:id:sachishimei:20171101115418j:plain

 

　Ninja H2 CARBONです。今回見たバイクのなかだと一番好きなデザインをしています。この黒を基調にして、一部分に緑が入るというところや前部の形がかなり良いです。

f:id:sachishimei:20171101115358j:plain

 

YAMAHAのブース

　YAMAHAのブースで特に気になったものが、前輪が二つ付いていてるバイクとモビリティです。特に、MWC-4(下の車種)なんかは4輪であり車とバイクの中間のような形をしていて、「The未来の移動手段」といった雰囲気を醸し出しています。

f:id:sachishimei:20171102214712j:plain　　f:id:sachishimei:20171102214800j:plain

　　

f:id:sachishimei:20171102214829j:plain

 

終わりに

もう少し続きます。

 

 

東京モーターショー 2017に行ってみた件について　Part1　ホンダ編

イベント

はじめに

　CEATECに先日行ってみて、想像以上に面白く、楽しめたため今度は東京モーターショーに行ってみようと思い実際に行ってきました。ただ、行く前はCEATECの入場料無料に対して、入場料の1600円にちょっと落胆していたのですが行ってみると1600円払う価値は十分にあると感じました。

　また、今回行ってみて思ったのですが、前売り券は絶対に買った方がいいです。でないと、その場で券を買ってまた入場列に並びなおすことになります。また、私が行ったときは生憎の悪天候で雨が降り続いていました。その中で並ぶ時間が長いと、入る前につかれてしまいます。よって、前売り券は買っておいた方がいいです。

　さらに、展示において子供や身障者が優先的に前に行けるスペースがあるため、もし、子持ちであれば一緒に行くことをおすすめします。

 

以下はブースの写真をいくつか貼っていきます。大量の写真があった場合はパートを分けるかもしれません。

＊暇なとき更新

 

Part2のURL

printf.hatenablog.com

 

ホンダのブース

　Monkeyがまた新しくですそうです。ただ、復刻というわけではなくコンセプトそのままに作った形になっているそうです。また、まだ開発中のため発売は来年になるそうです。

 

f:id:sachishimei:20171030105307j:plain　　　f:id:sachishimei:20171030105328j:plain

f:id:sachishimei:20171030105546j:plain


昔ながらのカブシリーズ


www.honda.co.jp

f:id:sachishimei:20171030114533p:plain　　f:id:sachishimei:20171030114551p:plain

 

 

　PCXにハイブリッドと電気モデルが登場しました

f:id:sachishimei:20171030115331p:plain　　f:id:sachishimei:20171030115357p:plain

 

　ホンダのNSX。2300万前後...高い。

f:id:sachishimei:20171101112653j:plain

 

　ホンダのUrban EV Conseptという目玉車種です。前の部分が電子的になっているところは新しいと思いましたし、そこを生かしてメッセージを表示できるところも便利だと思いました。

f:id:sachishimei:20171101113138j:plain

 

終わりに

　写真ばかりで異常に長くなりそうだったため、いくつかのパートに分けることにしました。

RUQ(Range Update Query)問題c++で解いてみた[備忘録]

競技プログラミング C++ 備忘録

問題URL

Range Update Query (RUQ) | Aizu Online Judge

 

RUQとは

　AOJの問題文から引用させてもらうと、

数列 A = {a0,a1 ,...,an−1} に対し、次の２つの操作を行うプログラムを作成せよ。

  • update(s,t,x): as,as+1,...,at をxに変更する。
  • find(i): ai の値を出力する。

ただし、ai (i=0,1,...,n−1)は、231-1で初期化されているものとする。

といった文言が書かれています。この問題では、nの範囲が100000まであり、updateとfindも合わせて最大100000回実行できるプログラムを作らなければなりません。

　これをなにも考えずに作ると、時間制限である1秒を超えてしまいます。実際、私も一度作りましたが、あるテストケースで1.73秒掛かってしまいました。そこで、出てくるのがRUQと呼ばれるデータ構造を使うことです。

 

kujira16.hateblo.jp

 

　上記のURLにあるブログの説明がRUQの図解付きで、非常にわかりやすかったです。

 

RUQを使って通したソースコード

・REP(i,n)で、for(int i = 0;i < n;i++)を省略しています。

・fill(from,to,num)で配列を同じ数字で埋めることが可能です。

・fill_n(from, num1, num2)で、fromからnum1個の数をnum2で埋めることができます。

・上記URLのRUQの説明を読んでください。

 

　下記ソースコードの配列aは、上記問題文にもある数列のことです。配列lazyは、数列aを√n個ずつの数列に分割したときに使われるものです。

　ところどころ現れる、

if(lazy[t/sq] >= 0){ fill_n(a+(t/sq)*sq,sq,lazy[t/sq]); lazy[t/sq] = -1; }

といったコードは、lazyに入っている数字をaに伝播させています。

　REP(i,q)内の2番目のif文であるif(t/sq  == s/sq)という部分は、a[s]とa[t]が同じlazyのグループに存在しているかを判定しています。そして、そのif文内部でも、sからtがグループの端から端まで包括しているかしてないかでも場合分けしています。

　REP(i,q)内の２番目のif文に対応したelse文内では、まず、1つグループすべての値を変更しない部分、つまり端の部分のaを直接変えています。次に、グループ内すべてを変えるものに対応したlazyを変えています。

　つまり、例えばnが11になると、0,1,2,3,4,5,6,7,8,9,10という配列の添え字をもつ物ができます。そして、これは、|0,1,2|3,4,5|6,7,8|9,10|という部分に分けられます。このとき、update(1,9,num)を実行すると、3から8はグループ内すべてを変更するためlazyを変えています。しかし、1と2、9はグループ内すべてを変えるわけではないためaを直接変えています。

 

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  int n,q;
  cin >> n >> q;
  vector  res;
  int a[n];
  int sq = sqrt(n);
  int nsq = n/sq+1;
  int lazy[nsq];
  fill(a,a+n,2147483647);//初期化
  fill(lazy,lazy+nsq,-1);//初期化
  REP(i,q){
    int z;
    cin >> z;
    if(z == 0){
      int s,t,x;
      cin >> s >> t >> x;

      
      if(t/sq == s/sq){//同じグループに属していた時
	if(lazy[t/sq] >= 0){//lazyが0以上ということは値が入っている
          //aの値を変更する前には必ず伝播させる
          //伝播させたらlazyで使った部分を初期化しておく
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	  lazy[t/sq] = -1;
	}
	if(t-s+1 == sq){
	  lazy[t/sq] = x;
	}
	else{
	  fill_n(a+s,t-s+1,x);
	}
      }

      else{
	int f = s,to = t;
	while(to%sq != (sq - 1)){
	  to--;
	}
	while(f%sq != 0){
	  f++;
	}
	if(lazy[t/sq] >= 0){
          //aの値を変える前の伝播
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	}
	if(lazy[s/sq] >= 0){
	  fill_n(a+(s/sq)*sq,sq,lazy[s/sq]);
	}
	fill_n(a+to+1,t-to,x);
	lazy[t/sq] = -1;
	fill_n(a+s,f-s,x);
	lazy[s/sq] = -1;
	f = f/sq;
	to = to/sq;
	if(f <= to){
	  fill_n(lazy+f,to-f+1,x);
	}
	
      }
      
    }
    else{
      int x;
      cin >> x;
      int te = x / sq;
      
      if(lazy[te] < 0){
	//cout << a[x] << endl;
	res.pb(a[x]);
      }
      else{
	fill_n(a+te*sq,sq,lazy[te]);//伝播
	lazy[te] = -1;
	//cout << a[x] << endl;
	res.pb(a[x]);

      }
      
    }
    
  }
  for(int i = 0;i < res.size();i++){
    cout << res[i] << endl;
  }
  return 0;
}

 

CEATEC JAPAN 2017に行って来ました

イベント

公式のURL

www.ceatec.com

 

はじめに

　この度、CEATECに初めて行ってきたので面白かったブースについて書いていこうと思います。外観は以下の画像のような感じでした。やはり、IoTブースに特に人が多かったと思います。

 

f:id:sachishimei:20171006224433j:plain

 

株価の予測

f:id:sachishimei:20171006224713j:plain

　銀行が株価の予測を行っているブースがありました。これは、じぶん銀行の口座があれば、個人的に使うことができるそうです。また、上の画像にも書いてありますが、実際にCEATECの期間中に取引してるそうで、的中率は63.6％、1千万円の元手から約4日間の間で30万円ほど儲けを出しているそうです。

　6割を超えているのはほんとにすごいと思います。具体的なプログラムの考え方とか教えてほしいですね。

 

MEKAMON　BANDAI

f:id:sachishimei:20171006225350j:plain

 

　BANDAIのブースから、新しく売り出そうとしているMEKAMONというロボットがありました。これは、スマホで操作できるロボットであり、なおかつ足などの部分が取り外すことができ、カスタマイズができるそうです。また、対戦にはARを使うことで臨場感のある戦いを演出していたり、四足歩行がで自由に動くことができます。

　ただ、見た感じ改良が必要そうには見えました。見てる間にもひっくり返って従業員さん？に直してもらうところを見ています。ただ、見ただけでもかなり平面的には自由に動けていたと思います。後は上下運動とかもしてほしいですね。後、充電が1時間しか持たないのはちょっとつらいところです。

 

風をセンシングし、シャボン玉をVRで演出

f:id:sachishimei:20171006230347j:plain

 

　ここでは、風センサを使って様々なことをしていました。上記画像はその一例です。画像のところでは、VRを付けた状態で風センサに息を吹きかけるとシャボン玉が発生する映像が見られるようになっています。この風センサは風の強弱も感知できるようで、少しずつ吹くと大きいシャボン玉ができ、一気に吹くと大量の小さいシャボン玉が出てくるようになっています。また、この例のほかにも、吹きかけられる風の強さによって色が変わるライトなどがありましたが、水には弱いようで屋外で使うことは、まだ推奨されていないようです。

　これを使えば空中に浮かんだものの姿勢制御とかできそうだなと思いました。

 

終わりに

　上記に上がっているブース以外にも、おもしろいところはたくさんありました。また、体験できるブースもあり、私も上記のシャボン玉もVRを付けて体験させてもらいました。事前登録すれば無料で入れますし、いろんな人におすすめできるイベントだと思います。平日ですが、学生でも最先端の技術を見て、体験できるため一日休む価値はあると思います。私も、もう来年が楽しみです。

Neural Network Console 使ってリンゴとブドウの分類してみた　Part2

機械学習 ニューラルネットワークコンソール ニューラルネットワーク Python Neural Network

前記事URL

 

前回まででやったこと

　Imagespiderを使って画像を集めて、データセットを作りました。

 

ニューラルネットワークの設計

　データセットは作ったため、とうとう設計していこうと思います。といっても、この問題は２値分類問題となるため、サンプルプロジェクトの一番上のやつをそのまま引用すれば設計できます。そして、設計図は以下のようになります。

f:id:sachishimei:20170913212142p:plain

　ここで気づく人もいると思いますが、Inputの横の数字の部分がデフォルトだと「1,28,28」になっていたはずが、「3,28,28」になっています。これは、今回カラー画像でデータセットを作っているからです。前記事でも、データセットを作るときRGBのところにチェックを入れていました。仮に、「1,28,28」でトレーニングしようとすると、

ValueError: could not broadcast input array from shape (10,3,28,28) into shape (10,1,28,28)

というエラーが出てきます。

 

　Affineはレイヤーリファレンスから引用すると、

全ての入力値から、OutShapeプロパティで指定する全ての出力ニューロンへの結合を持つ全結合層です。

 

o = Wi+b

（iは入力、oは出力、Wは重み、bはバイアス項を示す）

と書かれています。OutShapeプロパティでは出力ニューロン数を指定していますが、今回は1を指定しています。

 

　Sigmoidのリファレンスは、

入力値のSigmoidによる処理結果を出力します。確率など0.0～1.0の出力値を得たい場合に使用します。

 

o=sigmoid(i)

（oは出力、iは入力を示す）

となっています。

 

　BinaryCrossEntropyのリファレンスは、

データセットの変数との相互情報量を最小化するニューラルネットワークの出力層です。2値分類問題（0 or 1）を解く際に使用します。BinaryCrossEntropyの入力値は0.0～1.0（確率値）、データセットの変数は0もしくは1である必要があります。プロパティはSquaredErrorと共通です。

となっています。書いてある通り、2値分類問題における出力層として使われています。

引用部分のURLは以下に貼っておきます。

support.dl.sony.com

 

トレーニング

　私の場合、トレーニング用と評価用のデータの個数が38個ずつしかありませんでした。その状態で、トレーニングすると以下のようなエラーが出ます。

[Error 1] Batch size is larger than dataset "Training".
[Error 2] Batch size is larger than dataset "Validation".
2 errors.

バッチサイズが各データセットより大きいということを言っています。バッチとはなんぞやと思いましたがよくわかりませんでした。とりあえず、ミニバッチサイズというもののことを指しているようで、ミニバッチとは、学習するときにデータを分けることで学習時間の高速化を図る技術のことです。

　変更にはCONFIGタブのGlobal Configの部分にあるBatch Sizeをデータ量以下に変更します。今回でいえば38以下になります。下画面ではデフォルトの数値である64になっています。

f:id:sachishimei:20170913215520p:plain

 

　トレーニング結果は以下の画像の通りとなります。

f:id:sachishimei:20170913215806p:plain

　Epochが進むごとに0に近づいているので、どうやら成功しているようです。

 

評価してみた

　評価したときのConfusion Matrixは以下の画像のようになります。

f:id:sachishimei:20170913220458p:plain

　正確性は約86％となっています。実生活で使ったりするにはちょっと低い数値かなあと思います。ただ、今回はデータ数が少ないことや全く関係なさそうなデータ(2次元の女の子の画像など)が含まれている中では結構いい数値ではないかと思います。

 

終わりに

　今回、2値分類問題について取り組んだわけですが、こういうのって実際のWebサービスやアプリに使えるのかが疑問です。具体的には、GUIで書いたものをPythonコードに直すことができるのかとかですね。そういうことができないと、あんまりこのIDEは使う人が増えないと思います。

　また、これはニューラルネットワーク全体について言えることですが、ビッグデータを手に入れる手段がないため、その分野が個人利用の部分で発展しないのだと思います。私は今回Imagespiderを使っているわけですが、関係のない画像が入ってしまうなどデータセットとしての質が落ちてしまいます。本当は、私も欲をいうならば「男の娘か本物の女性の判定」も行ってみたいし、「ある人物がツインテールかどうか」などもやってみたいです。ですが、そのデータを手に入れる手段がないためできません。

　結局、質の高いビッグデータの共有場所が望まれるということです。

　また、リンゴとブドウの分類ではいろいろ試してみるつもりですが、もし正確性がよくなったら別記事に書いてみようと思います。

Pythonと再帰で解く部分和問題

目的

　こういうことをしようと思った目的は、競技プログラミングにおいてほとんどC++が使われている気がするため、Pythonで書こうとしても資料があまり見つかりません。そこで、簡単な問題くらいは自分で実装するかと思いました。

部分和問題とは

　数字がいくつか与えられていて、その数字をいくつか選んで目的の数を作る問題です。例えば、数字に[1, 2, 3, 4]が与えられているとき、7を作りたい場合は[1, 2, 4]を選ぶか、[3, 4]を選ぶ場合があり、これを求めるということです。

 

解き方

　多くの場合この部分和問題は、動的計画法で解いている人が多いため今回は再帰を利用した深さ優先探索を使いました。というのは嘘です。Pythonでの実装がよくわかりませんでした。とりあえず、ソースコードは以下に示します。これは、数の個数が増えると計算量がすさまじい速度で上がっていくため、大きいサイズでは使うことができません(正確には時間が膨大になる)。また、Pythonの再帰を使う上で、デフォルトの深さの限界が1000のためそれ以上の深さは他に設定を変える必要がある。

　ソースコードの上でのnは数の個数、aは各数字、kは調べたい数字を表しています。また、bはどの数字を使っているかを示すもので、[1, 3, 7, 6]の数字の中で1と6を使ったとき[1, 0, 0, 1]と表すようにしています。

#coding: UTF-8

n = int(input())
a = list(map(int, input().split()))
k = int(input())

def bubunnwa(i,sum,b):
    if(i < n):
        b.append(0)
        bubunnwa(i+1,sum,b)
        del b[i:]
        b.append(1)
        bubunnwa(i+1,sum+a[i],b)
    elif(i == n and sum == k):
        print(b)





bd= []
bubunnwa(0,0,bd)

 

実行結果

　入力は1行目が数字の個数、2行目が使える数字の一覧、3行目が作りたい数字になっています。

　出力は、使ったか使ってないかを1か0で表しています。

・入力1

5
4 9 2 8 7
14

・出力1

[1, 0, 1, 1, 0]

 

・入力2

5
1 2 3 4 5
3

・出力2

[0, 0, 1, 0, 0]
[1, 1, 0, 0, 0]

終わりに

　ちょっとDPもできるように頑張ってみようと思います。