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

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

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

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

はじめに

 制限時間内に問題を解く競技プログラミングにおいて、アルゴリズムを調べるために本を読み文字を打ち込むことはとてもめんどくさいと感じたため、ここに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;};//辺の表現方法の1種
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

 

終わりに

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

競技プログラミング 備忘録 ダイクストラ編

はじめに

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

 今回は、有向グラフについて書いてあるが、無向グラフのときは入力のfromとtoのところには逆向きの分もコストを入れている。

 

 最後の表示は、始点firstからそれぞれの最短距離を表示させるコードである。

ダイクストラ法特徴

重みが非負で、閉路が存在しないときに使える。あった場合はベルマンフォード法。

以下の1,2の条の下で進めていく。

1. まだ使われていない頂点の中で d [i] が最小の頂点を探す
2. その頂点に隣接する頂点をさきほどの式を適用して更新する。
ここでつかった頂点はもう使わない。

https://www.npca.jp/works/magazine/2014_1/より引用

O(E*logV)

基本ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MV 100000
#define INF 1e9

struct edge{int to,cost; };
vector <edge> G[MV];
bool used[MV];
int d[MV+1];

int V,E;

void dijkstra(int first){
  fill(d,d+MV,INF);
  fill(used,used+MV,false);
  d[first] = 0;

  for(int i = 0;i < V;i++){
    int now = MV;

    for(int j = 0;j < V;j++){
      if(used[j] == false && d[now] > d[j]){
	now = j;
      }
    }
    // cout << now << endl; デバッグ用、条件1が正しく動作しているかを確かめられる
    used[now] = true;
    for(int j = 0;j < G[now].size();j++){
      edge e = G[now][j];
      d[e.to] = min(d[e.to] , d[now]+e.cost);
    }
    /*for(int j = 0;j < V;j++)
      cout << d[j] << "   ";
      cout << endl; 
デバッグ用で、各点の更新後の最短経路が見れる
*/ } } int main(){ d[MV] = INF+10; int first; cin >> V >> E >> first; for(int i = 0;i < E;i++){ int f,t; edge e; cin >> f >> e.to >> e.cost; G[f].push_back(e); t = e.to; /*e.to = f; G[t].push_back(e);*/ } dijkstra(first); for(int i = 0;i < V;i++){ if(d[i] == INF){ cout << "INF" << endl; } else{ cout << d[i] << endl; } } }

 

各頂点間の最短のコストと求めるソースコード

 すべての頂点間についての最短経路のコストについて求めている。ソースコードは以下のようになる。

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
#define MV 200
#define INF 1e10
 
struct edge{int to,cost; };
vector <edge> G[MV];
 
int V,E;
long long d[MV+1];
 
bool bellmanford(int s){
  fill(d,d+MV,INF);
  d[s] = 0;
  int c = 0;
  bool upd = false;
  while(true){
    upd = false;
    for(int i = 0;i < V;i++){
      for(int j = 0;j < G[i].size();j++){
    edge e = G[i][j];
    if(d[i] != INF && d[e.to] > d[i] + e.cost){
      d[e.to] = d[i] + e.cost;
      upd = true;
    }
      }
    }
    if(!upd)
      break;
    if(c == V-1)
      return true;
    c++;
  }
  return false;
}
 
int main(){
  d[MV] = INF+10;
  int first;
  bool flag;
  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);
   
    t = e.to;
    /*
    e.to = f;
    G[t].push_back(e);
    */
  }
  long long vec[V][V];
   
  for(int i = 0;i<V;i++){
    flag = bellmanford(i);
    for(int j = 0;j < V;j++){
      vec[i][j] = d[j];
    }
    if(flag == true)
      break;
  }
  if(flag == true)
    cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0;i < V;i++){
      for(int j = 0;j < V;j++){
    if(vec[i][j] == INF){
      if(j != V-1)
        cout << "INF" << " ";
      else
        cout << "INF";
    }
    else{
      if(j != V-1)
        cout << vec[i][j] << " ";
      else
        cout << vec[i][j];
    }
      }
      cout << endl;
    }
   
  }
   
}


 

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

問題URL

Range Update Query (RUQ) | Aizu Online Judge

 

RUQとは

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

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

  • 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)内の2番目の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

前記事URL

 

前回まででやったこ

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

 

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

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

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を使っているわけですが、関係のない画像が入ってしまうなどデータセットとしての質が落ちてしまいます。本当は、私も欲をいうならば「男の娘か本物の女性の判定」も行ってみたいし、「ある人物がツインテールかどうか」などもやってみたいです。ですが、そのデータを手に入れる手段がないためできません。

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

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