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

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

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

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

はじめに

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

 

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

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

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

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もできるように頑張ってみようと思います。

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

はじめに

 今まではテストデータを使ってやってきたけれども、自分で画像を集めて1から分類してみました。

データセット作ってみる

 ニューラルネットワークで必ず必要になるのがビッグデータですが、今回は集める方法としてImagespiderというソフトを使いました。ダウンロードはこのサイトでできます。また、画像は一つのフォルダ内にものごとのフォルダに保存する必要があります。例えば、今回は「NNCtestフォルダ」内の「リンゴというフォルダ」と「ブドウというフォルダ」内にそれぞれダウンロードした画像が入っています。

 そこまで終わったら、ニューラルネットワークコンソールのホーム画面からDATASETを選択し、左上にある「Create Dataset」を選択します。下画像でいう真ん中上部の青くなっている部分のことです。

 

f:id:sachishimei:20170913101540p:plain

 

 「Create Dataset」を選択していただくと、以下の画像のような画面が出てくると思います。「Source Dir」は、今回データセットにするジャンル分けされた画像が入っているフォルダを選択します。今回でいえば、前述した「NNCtestフォルダ」を選択します。「Output Dir」は、作ったDatasetのcsvファイル保存する場所を選択します。ただ、注意点として「Source Dirフォルダ」と一緒のところには保存できません。右下のRatio(%)は、訓練用データとテストに用いるデータの比率を設定することができます。以下の画面を例にすると、すべての画像データの内98%を訓練に、2%をテストデータとして使っています。

*すいません。2%だとあまりにもテストデータが少なすぎたためこれ以降50%ずつでやっています。

 

その他の細かいリファレンスは以下に掲載してあります。

support.dl.sony.com

 

 

f:id:sachishimei:20170913101355p:plain

 

 すべて設定し終わった後にApplyを押すと、Datasetが作成されます。作成後は以下のような画面が出現してデータセットの画像が確認できます。ただ、今回の場合ImagespiderがGoogle画像検索で出た画像をまとめてダウンロードするという性質上、関係なさそうな画像が含まれています。そこは、Datasetを増やすか自分の目で判定するかして、制度を上げる必要があります。ただ、後者の場合ニューラルネットワークの訓練データが10000くらいに増えたら到底不可能のため、現実的ではありません。

 

f:id:sachishimei:20170913103410p:plain

 

 また、同じようなことをしてもらうとわかるのですが、すべての画像をテストデータにできていないのです。つまり、いくつかは失敗しているということです。そして、そのままニューラルネットワークの設計をして実行すると、

FileNotFoundError: [Errno 2] No such file or directory: '失敗した画像のURL'

というエラーが出現します。そのため、同じようなエラーが出たときは、その対策として、上部の入力で行ったOutShape Dirに書いたフォルダ内に成功している画像の一覧があるため、それを用いてもう一度Datasetを作り直すとうまくいきます。

 

さらに、画像の名前が%2...のようにちょっとおかしい、文字化けしているような状態になっている場合はその画像を直した方がいいです。でないと、

UnicodeDecodeError: 'utf-8' codec can't decode byte 0x83 in position 2: invalid start byte

というエラーがでます。

 

中間休憩

 長くなったため次回まで続きます。また、やっていく過程でエラーが結構頻発しているためどこかでまとめた記事でも出そうと思っています。

 

 

 

 

競技プログラミング ベルマンフォード編 [備忘録]

はじめに

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

ベルマンフォード法特徴

O(V*E)

プログラム上、入力が有向グラフ形式になっている。

無向グラフを表すには逆向きのものも辺として入力させればよい。

d[a]で終点をaとした最短経路のコストを入れている。

負の閉路があるときはNEGATIVE CYCLEと表示される。

 

ソースコード

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

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

struct edge{int to,cost; };
vector <edge> G[MV];

int V,E;
int 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 >> first;
  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);
  }

  
  flag = bellmanford(first);
  if(flag == true)
    cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0;i < V;i++){
      if(d[i] == INF){
	cout << "INF" << endl;
      }
      else{
	cout << d[i] << endl;
      }
    }
  }
  
}