yukicoder No.643 Two Operations No.2
問題
No.643 Two Operations No.2 - yukicoder
解説
この解説は多分悪い例として見ていただくのが良いと思います。
考察のできる人は、公式解説通りに考えられるのでしょう。でも僕にはそんな思いつきはありませんでした。ならマシンパワーに頼るしかない、ということで、全探索解でACしました。これも競技プログラミングです。
操作1,2を様々な順番で実行して行って、x==yとなるような最小手順を探してみます。
問題はこの手順をどれくらいの深さまで見るかですが、適当に手元で実行すると、30回では時間がかかりすぎたので、20回にしました。
ans=10000と初期化しておいて、x==yになればctとの最小値を取ります。最終的にans==10000であれば、x==yにならなかったので-1を出力です。
今回は偶然答えが3以下になるような問題だったので、全探索が通って嬉しいですね。
#include <iostream> using namespace std; int ans=100000; void dfs(int x,int y,int ct){ //cout<<x<<y<<endl; if(ct>20){ //20回操作を試して見たら終了 return; } if(x==y){ ans=min(ans,ct); return ; } dfs(y,x,ct+1); //操作１ dfs(x+y,x-y,ct+1); //操作２ return; } int main (){ int x,y; cin>>x>>y; dfs(x,y,0); if(ans!=100000)cout<<ans<<endl; else cout<<-1<<endl; return 0; }
yukicoder No.739 大事なことなので2度言います
解説
文字列を半分に切って、同じかどうか判定します。
文字列を抽出するsubstr(開始index, そこから何文字か)を利用すると簡単にかけます。
substr()の使用例は以下のような感じです。
string s="abcde"; cout<<s.substr(1,3)<<endl; //"bcd"が出力。s[1]から3文字分取る。
よって、この問題の解答は以下のようになります。
#include <iostream> #include <string> using namespace std; int main (){ string s; cin>>s; if(s.substr(0,s.size()/2)==s.substr(s.size()/2,s.size()/2))cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }
他には、単純に１文字ずつ見ていく方法があります。
int main(){ string s;cin>>s; //文字列長が奇数ならそもそもNO if(s.size()%2==1){ cout<<"NO"<<endl; return 0; } //文字列を添字が0から、s.size()/2からの2つをスタート地点として、順番に比べる。1つでもダメならその時点でNO。 rep(i,0,s.size()/2){ if(s[i]!=s[i+s.size()/2]){ cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; return 0;
processingでエクスポートすると画像が出ない話
processingは、「アプリケーションとしてエクスポート」すると、.exe(Windows)や.app(Mac) などの形式で出力できます。
しかし画像ファイルを扱っていた時、単に出力しただけでは起動ファイルを実行しても画像が表示されません。
解決策
出力前にコーディングしていた時には、画像を.pdeと同じ階層に置くことで、loadImage()で読み込むことができていました。
出力の際にも同じことをします。出力されたファイルには画像ファイルの情報は含まれないので、自分で置く必要があります。
具体例(一応)
念のため、具体例を示します。
以下のコードtest.pde の中身が以下のようになってしているとします。
size(500,500); PImage p=loadImage("1.png"); image(p,0,0);
この時、編集中のフォルダ[test]は以下のようになります。
.pdeと同じフォルダに画像を置いています。
次に、これを出力すれば以下のような中身のフォルダができます。（画像はmac）
これらの起動ファイルを実行しても画像は表示されないので、自分で置きます。（画像はmac）
これで起動すると画像が表示されるようになりました。
windowsでも同様に画像を配置すれば良いです。
ノイズ木構造
ノイズ木構造
— string s="ごつちやん"; (@gotutiyan_kapi) October 8, 2018
再帰とノイズでえっさほいさとhttps://t.co/L4cClmSyyP#processing #creativecoding pic.twitter.com/4InhLRMLSg
再帰関数で二分木をどわーっと書いて、点をノイズで揺らしてみました。僕の好きなノイズと再帰でごり押しした感じの作品ですが、動的に生成される木構造が良いですね。本当はノードが増えたり減ったりしたときに、辺をニョキッと滑らかに生やしたかったんですが、やり方がよく分かりませんでした。。
コードは以下の通りです。最初の一回だけ、nowDeepが０なので、map(i,0,0,0,360)となってこれはinfinityを返すぞ！と怒られますが、気にしない気にしない。
PIC10 p10=new PIC10(); void setup(){ size(1200,600,P2D); smooth(); } void draw(){ background(0); p10.move(width/2,10,0); } class PIC10 { int nowDeep=0; //現状の最大の再帰の深さ PIC10() { } void move(float x, float y, int i) { float noi=200*noise(100*i+frameCount/700.0); //横の節との間隔 float noitate=200*noise(1000*i+frameCount/700.0); //縦の節との間隔 if (y+noitate>=height-20) { //画面に収まる範囲で再帰をする fill(map(i, 0, nowDeep, 0, 360), 100, 100); ellipse(x, y, 10, 10); nowDeep=i; //再帰を打ち切る際にnowDeepを更新 return; } colorMode(HSB, 400, 100, 100); fill(map(i, 0, nowDeep, 0, 360), 100, 100); ellipse(x, y, 10, 10); stroke(0,0,100); line(x, y, x+noi, y+noitate); line(x, y, x-noi, y+noitate); move(x+noi, y+noitate, i+1); move(x-noi, y+noitate, i+1); } }
ランダムウォーク2
先日のランダムウォークを改良しました。
gotutiyan.hatenablog.com
方向ベクトルを斜めにして、軌跡を点線に。さらに円の内部を動く色付きのものと、円の外を動く白色のものに分けてみました。
ランダムウォークをもう少し改良〜
— string s="ごつちやん"; (@gotutiyan_kapi) October 6, 2018
コードと解説は以下からhttps://t.co/kwZ3QfGVEE#processing#creativecoding pic.twitter.com/VCX6Ciwwuz
白いものは画面外に出たとき、もしくは円の中に入ったときに、強制的に引き戻す方向に変えさせます。
色付きのものは、円を出ようとしたときに、強制的に引き戻す方向に変えさせます。
引き戻す方向は案外簡単に設定できて、引き戻す条件に合致した瞬間のx,y座標をX,Yとおけば、「出て行く」動きを引き戻すなら、X,Yそれぞれの反対の符号を持つdir[ ]を、「入りこむ」動きを引き戻すなら、X,Yそれぞれと同じ符号を持つ dir[ ]を足せば良いです。
また、軌跡を表す線を点線にしましたが、これは軌跡を格納している配列において、「5で割った余りが0,1,2となるような添字の時だけline()を引く」ということをしています。
つまり、３ピクセル描いて２ピクセル描かない、をひたすら繰り返します。
コードはprocessingで、以下の通りです。
RandomWalk2 random10_color[]=new RandomWalk2[100]; RandomWalk2 random10_white[]=new RandomWalk2[200]; void setup() { size(600,600,P2D); for (int i=0; i<random10_color.length; i++)random10_color[i]=new RandomWalk2(0); for (int i=0; i<random10_white.length; i++)random10_white[i]=new RandomWalk2(1); } void draw() { background(0); translate(width/2, height/2); noFill(); ellipse(0, 0, 500, 500); for (int i=0; i<random10_color.length; i++)random10_color[i].move(); for (int i=0; i<random10_white.length; i++)random10_white[i].move(); } class RandomWalk2 { PVector now; PVector dir[]=new PVector[4]; PVector diff; ArrayList<PVector> prev=new ArrayList<PVector>(); int changeDir; float c; float radius=250; int mode=0; //0なら円内部の色付き、１なら円外部の白 RandomWalk2(int emode) { mode=emode; if (mode==0)now=new PVector(0, 0); else now=new PVector(random(width)-width/2, random(height)-height/2); dir[0]=new PVector(1, 1); //方向ベクトルたち dir[1]=new PVector(-1, -1); dir[2]=new PVector(1, -1); dir[3]=new PVector(-1, 1); diff=new PVector(1, 1); changeDir=(int)random(30, 50); c=random(360); } void move() { if (mode==0) { if (dist(0, 0, now.x, now.y)>radius) { //色つきのが円の外に出ない if (now.x<0&&now.y<0)diff=dir[0]; if (now.x>0&&now.y>0)diff=dir[1]; if (now.x<0&&now.y>0)diff=dir[2]; if (now.x>0&&now.y<0)diff=dir[3]; } } else { if (dist(0, 0, now.x, now.y)<radius) { //白いのが円の中に入らない if (now.x>0&&now.y>0)diff=dir[0]; if (now.x<0&&now.y<0)diff=dir[1]; if (now.x>0&&now.y<0)diff=dir[2]; if (now.x<0&&now.y>0)diff=dir[3]; } if (now.x<-width/2)diff=dir[0];//白が画面の外に出ない if (now.x>width/2)diff=dir[1]; if (now.y<-height/2)diff=dir[3]; if (now.y>height/2)diff=dir[2]; } if (frameCount%changeDir==0) { //フレームごとでの方向変更 int x=(int)random(0, 4); diff=dir[x]; } prev.add(new PVector(now.x, now.y)); while (prev.size()>100)prev.remove(0); now.add(diff); if (mode==0) { //円の色 colorMode(HSB,360,100,100,100); fill(c, 100, 100,100); } else { colorMode(RGB); fill(255); } noStroke(); ellipse(now.x, now.y, 10, 10); //円の描画 colorMode(HSB); if (mode==0) { //線の色 colorMode(HSB); stroke(c, 100, 100, 100); } else { colorMode(RGB); stroke(255); } for (int i=1; i<prev.size(); i++) { //線を描く if (i%5==0||i%5==1||i%5==2)line(prev.get(i).x, prev.get(i).y, prev.get(i-1).x, prev.get(i-1).y); } } };
processing: ArrayListのadd()で配列の要素が全部同じになった話
ArrayList::add()の様子がおかしい・・？
見事にハマったので感想をば。
ランダムウォーク - gotutiyan’s blog
このランダムウォークを実装しようとしたとき、円の軌跡を残すために前100フレーム分の座標をArrayListに格納して管理しようとしました。
このとき、以下のような実装をしたのです。（少し省略していますが）
ArrayList<PVector> prev = new ArrayList<PVector>(); prev.add(now); /*nowは現在の座標で、毎フレーム更新されます。このnowを毎フレームaddすることで、保存されていくはず。*/
add()は配列の一番後ろに値を挿入します。しかし、この実装ではnowをadd()する度に、配列の要素全てが今addしたばかりのnowになってしまったのです。
こうなる原因は、ArrayListにおけるのメモリ関連にありました。
ArrayListはアドレスを保存している
変数を宣言したからにはそれを保存するためのメモリを消費していて、このメモリの場所のことをアドレスと呼ぶのでした。ArrayListにおけるadd() では、このアドレスを格納していくようです。値を格納しているのではありません。C言語を嗜んだことがある人でしたら、このような違いです。
int x[]; //理想 int *x[]; //現実
つまり、上記の実装では、決して変わることのないnowのアドレスを、何回も追加していたことになります。当然、nowを更新すれば、それを参照している配列の要素すべての値が書き換わります。
これを防ぐためには、新たにメモリを取り直してから格納すれば良いです。
prev.add(new PVector(now.x,now.y));
このように、「new PVector()」を用いることで、アドレスを取り直して追加することができ、配列の要素が書き換わらなくなりました。
ランダムウォーク
TLで見かけたランダムウォークをProcessingで実装しました。
ランダムウォークを見たので描いてみました。これすごく好きです。
— string s="ごつちやん"; (@gotutiyan_kapi) October 3, 2018
実装解説とコードは以下から。https://t.co/drS6Pxb2H5#processing pic.twitter.com/Ss7Bu3VyDo
実装の方針は以下の通りです。
・円を動かす方向を数十フレームごとに更新する。
・円の軌跡を数十フレーム分残して、lineで描画する。
今回は４方向のみのランダムウォークです。自身としては初めて、PVectorとArrayListを使ってみました。どちらも使い慣れると便利でした。
PVectorはfloat型変数x,yを持ったクラスで、以下のようにして扱えます。
PVector p=new PVector(0,50); //pのx座標に50、y座標に100足すとします。add()で足す。 p.add(new PVector(50,100)); ellipse(p.x,p.y,100,100); //ellipse(0+50,50+100,100,100)と同じ
また、ArrayListは動的配列で、C++で言う所のvectorクラスと同じようなものです。以下のようにして扱えます。
ArrayList<PVector> prev=new ArrayList<PVector>(); //値を追加。一番後ろに入ります。 prev.add(new PVector(x座標,y座標)); //値を削除。 prev.remove(消したい要素の添字); //配列の長さを取得。 prev.size(); //配列の要素を参照。 prev.get(添字);
要素の取得にはprev.get(0);とする必要があり、prev[0]のようにCライクでは書けません。
また、今回は要素の追加のadd()でめちゃくちゃハマリました。このことについてはまた別の記事として書きたいと思います。
今回はこのArrayListを「後ろに行くほど新しい軌跡が入った配列」として利用しました。後ろから座標を入れて行って、前から消して行きます。
コードは以下の通り。
int sz=50; //描く数 RandomWalk random9[]=new RandomWalk[sz]; void setup(){ size(500,500,P2D); smooth(); for(int i=0;i<sz;i++)random9[i]=new RandomWalk(); } void draw(){ background(0); for(int i=0;i<sz;i++)random9[i].move(); } class RandomWalk { PVector now; //円の現在の位置 PVector dir[]=new PVector[4]; //向かう方向を４方向分格納 PVector diff; //現在円が向かうべき方向 ArrayList<PVector> prev=new ArrayList<PVector>(); //円の軌跡を格納 int changeDir; //方向を変えるフレーム間隔 RandomWalk() { now=new PVector((int)random(width), (int)random(height)); dir[0]=new PVector(1, 0); dir[1]=new PVector(-1, 0); dir[2]=new PVector(0, 1); dir[3]=new PVector(0, -1); int x=(int)random(4); diff=dir[x]; changeDir=(int)random(30,50); } void move() { if (frameCount%changeDir==0) { //もし画面外にいたなら、引き戻す方向に設定 if (now.x<0)diff=dir[0]; else if (now.x>width)diff=dir[1]; else if (now.y<0)diff=dir[2]; else if (now.y>height)diff=dir[3]; else { //画面内ならランダムに int x=(int)random(0, 4); diff=dir[x]; } } prev.add(new PVector(now.x,now.y)); //prev配列の一番後ろに今の座標を入れる now.add(diff); //今の座標を更新 fill(255); ellipse(now.x, now.y, 10, 10); while (prev.size()>100)prev.remove(0); //前100フレーム分持ちたいので、多すぎる分古いもの(前)から削除 stroke(255); for (int i=1; i<prev.size(); i++) { line(prev.get(i).x, prev.get(i).y,prev.get(i-1).x,prev.get(i-1).y); //軌跡を描画 } } };
