ランダムウォーク
TLで見かけたランダムウォークをProcessingで実装しました。
ランダムウォークを見たので描いてみました。これすごく好きです。
— string s="ごつちやん"; (@gotutiyan_kapi) October 3, 2018
実装解説とコードは以下から。https://t.co/drS6Pxb2H5#processing pic.twitter.com/Ss7Bu3VyDo
実装の方針は以下の通りです。
・円を動かす方向を数十フレームごとに更新する。
・円の軌跡を数十フレーム分残して、lineで描画する。
今回は4方向のみのランダムウォークです。自身としては初めて、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]; //向かう方向を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); //軌跡を描画 } } };
2018/9/4 虹色四角の周期性回転
虹色の四角を何重にも描いて、回転をすることで良い感じになりました。
やってることはよくある回転ですが、何回見ても綺麗ですね。
float seed[]=new float[250]; void setup(){ size(500,500); colorMode(HSB,360,255,255); for(int i=0;i<width/2;i++)seed[i]=0; } void draw(){ fill(255); [f:id:gotutiyan:20180904232406p:plain] int x=width/2; translate(width/2,height/2); for(int i=0;x>0;i++){ pushMatrix(); rotate(seed[i]); fill(map(i,0,width/2/4,0,360),255,255,100); rect(-x,-x,2*x,2*x); rotate(radians(i/2.0)); x-=4; seed[i]+=0.001*i; popMatrix(); } }
ABC 108(9/1) A,B,C問題の思考過程
なんか3完で58位を取れたので思考過程を書きます。珍しくA→C→Bで解きました。
A問題
簡単な掛け算で解けそうでしたが、その式を考える時間で愚直ループ解を実装できそうだったのでそっちにしました。偶数の個数と奇数の個数を数えて掛け算します。
int main(){ int k; cin>>k; int even=0,odd=0; rep(i,1,k+1){ if(i%2==0)even++; else odd++; } cout<<even*odd<<endl; }
B問題
正方形の残りの2点の座標を出力する問題です。最初、正方形は辺が方眼紙のせんに沿うような形しか想像していませんでした。ですが斜めに向くパターンもあると気づいてからサンプルをぐっと睨むと、入力のx座標の差分とy座標の差分を利用するだけと気づいたので実装しました。
int main(){ int x,xx,y,yy; cin>>x>>y>>xx>>yy; int a,aa,b,bb; int diffx=xx-x,diffy=yy-y; a=xx-diffy; b=yy+diffx; aa=a-diffx; bb=b-diffy; cout<<a<<" "<<b<<" "<<aa<<" "<<bb<<endl; }
C問題
a,b,cの任意の2つの和がKの倍数になるということで、「和が〜の倍数」という部分に余りの利用を感じました。
まず、a,b,cが全てKの倍数の時、当然任意の2つの和はKの倍数になるなあと思いました。
さらに、2つの数を足すということから、Kの剰余がK/2になる数も答えになると思いました。ここで、Kが偶数の時には成り立ちますが、奇数の時には成り立たない気がしました。試しにK=5を考えた時、5=2+3とすればa=2(mod K)、b=3(mod K) と仮定できますが、cにはaとの対では3、bとの対では2を当てるべきで、これは同時に満たせません。この例で、Kが奇数の時にはKの剰余がK/2になる値は使えないと結論づけました。
一般化(?)すれば、a,b,cをKでの剰余とし、K=a+bと分割した時、残りのcはK=a+c、K=b+cの両方を満たさねばならず、つまりa=b=cにならないといけません。このような時、a,b,cは0(mod K、つまりKの倍数)、またはK/2(mod K、ただしKは偶数)の時だけなのではー、と思ったわけです。
最後に、a,b,cの順番を入れ替えたものも違う組みとして考えることから、個数を数えて単に3乗すれば良いと気づきました。
int main(){ ll n,k; cin>>n>>k; vector<ll> v(k,0); rep(i,1,n+1){ v[i%k]++; } ll ans=0; ans+=(v[0]*v[0]*v[0]); if(k%2==0){ ans+=(v[k/2]*v[k/2]*v[k/2]); } cout<<ans<<endl;
アステロイド曲線
アステロイド曲線で遊びました#openframeworks
— string s="ごつちやん"; (@gotutiyan_kapi) August 9, 2018
コードは以下からhttps://t.co/Lljyp5LFpN pic.twitter.com/XLAQYIpiB6
この前にリサージュ曲線を描きましたが、次はアステロイド曲線です。リサージュ曲線の記事は以下です。
リサージュ曲線 - gotutiyan’s blog
以下のサイトを参考に、リサージュ曲線の式は以下のように表すことができます。圧倒的にわかりやすいですね。
x=a*cos()*cos()*cos(); y=a*sin()*sin()*sin();
もちろん、cosやsinはラジアンの引数を取りますが。
mathtrain.jp
今回はこれを適当に並べてみると、アステロイド曲線を並べているけど円を並べているように見えたので、回転させてみました。面白いですね!
#include "ofApp.h" #include <vector> #include <utility> #include <algorithm> #define rep(i,j,k) for(int i=j;i<k;i++) #define pb push_back class asteroid{ public: int n,size; double r; vector<double> x,y,sita; void init(int nn,int nsize,double nr){ n=nn; size=nsize; x.resize(n); y.resize(n); sita.resize(n); r=nr; } void move(){ rep(i,0,n){ sita[i]+=PI/128*(i+1)/n; x[i]=size*cos(sita[i])*cos(sita[i])*cos(sita[i]); y[i]=size*sin(sita[i])*sin(sita[i])*sin(sita[i]); ofDrawCircle(x[i],y[i],r); } } }; asteroid a[25]; void ofApp::setup(){ ofSetRectMode(OF_RECTMODE_CENTER); ofSetFrameRate(60); ofSetBackgroundColor(0); ofSetColor(255); ofSetCircleResolution(64); //ofNoFill(); rep(i,0,25)a[i].init(50,50,2.0); } void ofApp::update(){ } void ofApp::draw(){ rep(i,0,5)rep(j,0,5){ ofPushMatrix(); ofTranslate(50+100*i,50+100*j); ofRotate(25*ofGetFrameNum()*DEG_TO_RAD); a[i*5+j].move(); ofPopMatrix(); } }
リサージュ曲線
リサージュ曲線を描いてみました。
リサージュ曲線はx,yを媒介変数表示することで表現できます。
以下のサイトのリサージュ曲線の項を参考に、プログラムで表現してみます。係数のsizeは、リサージュ曲線の完成形の、縦横の大きさを表します。
x=size*sin(3*θ) y=size*sin(4*θ)
mathtrain.jp
以下のプログラムでは、θの部分をaddx[ ],addy[ ]としています。
数学の授業で書くようなグラフは、この媒介変数表示において、θを変えることにより計算できる点を無限に打つことで実線として書けています。
プログラムでは無数に点は打てず、processingではまだしもopenframeworksでは点を打つ関数が無いので、200個程度の円を描いて動かすことにします。
これらは結局周期運動になるので、あるタイミングで複数の点が1点に重なることがあり、見ていて楽しいですね。
コードは以下の通りです。
#include "ofApp.h" #include <vector> #include <utility> #include <algorithm> #define rep(i,j,k) for(int i=j;i<k;i++) #define pb push_back int n=200,size=200; vector<double> x(n),y(n),addx(n,0),addy(n,0); void ofApp::setup(){ ofSetRectMode(OF_RECTMODE_CENTER); ofSetFrameRate(60); ofSetBackgroundColor(0); ofSetColor(255); ofSetCircleResolution(64); //ofNoFill(); rep(i,0,n){ x[i]=size*sin(3*addx[i]); y[i]=size*sin(4*addy[i]); } } void ofApp::update(){ } void ofApp::draw(){ ofTranslate(250,250); rep(i,0,n){ ofDrawEllipse(x[i], y[i], 10, 10); addx[i]+=PI/512*(i+1)/n; addy[i]+=PI/512*(i+1)/n; x[i]=size*sin(3*addx[i]); y[i]=size*sin(4*addy[i]); } }
ACM-ICPC 大崎(Osaki)
電車が走行する時間帯が与えられるので、最低電車が何台あれば運行できるかを出力する。
解説
入力の運行時間が少しでも被っていれば、その時間帯は複数の電車が運行しないと矛盾してしまいます。よってすべての運行時間を見て、運行時間が被っている時間帯の個数の最大値を求めれば良いです。
具体的な方法としては、時間帯を秒単位で表す配列を用意して、運行時間帯中の要素を全て+1します。これを全ての入力について行った後、配列の要素の最大値を見れば、答えが求まります。
しかし、この「時間帯の要素全てに+1する」という操作について真面目にfor文を回すと、計算量が心配です。これはimos法を使えば計算量がグッと落ちます。
今回の入力では数字やコロンの間に空白が無いため、cin>>などよりはscanfを使った方が入力を受け取りやすいと思います。
#include <iostream> #include <string> #include <map> #include <vector> #include <utility> #include <set> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <cmath> #define rep(i,j,k) for(int i=(int)j;i<(int)k;i++) #define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++) #define Sort(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define vec vector #define INF (int)1e9 #define INFL 1e18 #define MOD 1000000007 #define pb push_back #define MP make_pair #define PI 3.1415926535 typedef long long int ll; typedef std::pair<int,int> P; int D=1; int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0}; using namespace std; int main(){ int n; int t=24*3600+59*60+59; //あり得る時間(秒)の最大値 while(cin>>n&&n){ vector<int> v(t+1,0); rep(i,0,n){ int hs,ms,ss,he,me,se; scanf("%d:%d:%d",&hs,&ms,&ss); scanf("%d:%d:%d",&he,&me,&se); v[hs*3600+ms*60+ss]++; //区間の左端に+1(imos法) v[he*3600+me*60+se]--; //区間の右端に-1(imos法) } int ans=0; rep(i,0,t){ v[i+1]+=v[i]; //一気に累積和をとる(imos法) ans=max(ans,v[i+1]); //配列の最大値をansに入れる } cout<<ans<<endl; } return 0; }
ACM-ICPC When Can We Meet?
問題
When Can We Meet? | Aizu Online Judge
N人分の空いている日程が与えられるので、M人以上が参加できる日程の中で最も多くの人が参加できる日程を出力します。同じ人数参加できる日が複数存在する場合、一番早い日を出力します。
解説
N人分のデータが与えられますが、「この日程は何番目の人のもの」ということは特に意識する必要はありません。誰のものかは気にせず、単純に与えられた日程を全て数えれば良いです。
数えるための配列をvとおき、0で初期化、v[i]=日程 i+1が空いている人数として扱います。N回ループを回す中で毎回xを受け取り、x回ループを回す中で v[日程]++; とすることで数えられます。
最後に、一番登場回数の多い日付を探して出力すれば良いです。
探すにあたっては、登場回数の最大値を保存するnum、その最大値を持つ添字を保存するansというように、2つ値を持ちながら探す必要があります。
該当する日付がない時0を出力しますが、ansを0で初期化しておけば、結局何も更新がなければ0が出力されて手間が省けます。
#include <iostream> #include <string> #include <map> #include <vector> #include <utility> #include <set> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <cmath> #define rep(i,j,k) for(int i=(int)j;i<(int)k;i++) #define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++) #define Sort(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define vec vector #define INF (int)1e9 #define INFL 1e18 #define MOD 1000000007 #define pb push_back #define MP make_pair #define PI 3.1415926535 typedef long long int ll; typedef std::pair<int,int> P; int D=1; int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0}; using namespace std; int main(){ int n,m; while(cin>>n>>m&&n&&m){ vector<int> v(100,0); //v[i]:=日程i+1が空いている人数 rep(i,0,n){ int x; cin>>x; rep(j,0,x){ //日程を受け取って、登場回数を増やしていく int t; cin>>t; t--; v[t]++; } } int ans=0,num=-1; rep(i,0,100){ //v[i]がm以上で、かつ現在保持している最大値より大きければ更新 if(v[i]>=m && num<v[i]){ num=v[i]; ans=i+1; } } //最終的な日程を出力 cout<<ans<<endl; } return 0; }