2018-04-18

AOJ 宇宙ヤシガニ(Space Coconut Grab)　解説

AOJ ICPC

問題
Space Coconut Grab | Aizu Online Judge

解説
３つの変数をループで回して全探索すると、O(10^9)となってTLEします。
しかし、x+y*y+z*z*z=eになることから、y,zが分かればxが分かります。

よってy,zを２重ループで回して、残りのxをx = e- y*y - z*z*z と算出できます。
このときの計算量はO(10^6)まで落ちるので間に合います。
またこの過程では、計算により求めたxの値がマイナスになることがあります。これはx+y*y+z*z*z=e において、左辺が大きくなりすぎているということなので、continueすることで除外します。

int main(){
    while(1){
        int e;
        int ans=1e9+7;
        cin>>e;
        if(e==0)break;
         
        rep(y,0,1000){
            rep(z,0,1000){
                int x=e-y*y-z*z*z;
                if(x<0)continue;
                ans=min(ans,x+y+z);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

2018-04-17

集中レーザー

openframeworks

レーザーが集中しているので。（最近良い題名が思いつきませんね）

集中レーザー
良いですね#openframeworks

コードの解説は以下から。https://t.co/VYQcexZGFS pic.twitter.com/53C5pIEIGy
— string s="ごつちやん"; (@gotutiyan_kapi) 2018年4月17日

今回からコードの解説はできるだけ以下のコードの中にコメントとして書くことにしました。その方がわかりやすい気がします（たぶん）。

初めてofMapを使いました。
ofMap(値、元範囲の最小値、元範囲の最大値、目的範囲の最小値、目的範囲の最大値）として使います。

例えば、sin関数は-1~1しか取りませんが、これを0~100の間に範囲を移したいとします。このとき、例えば0なら中間なので50になったり、-0.5なら小さい方から1/4地点ということで25になったりします。

float value = ofMap(sin(ラジアン), -1, 1, 0 ,100);

このように「ある一定の範囲しか取らない値を、別の範囲に対応させる」ときによく使います。今回は0~1しか取らないofNoise()を、-25~25に対応させています。これは便利ですね。

#include "ofApp.h"
#define rep(i,j,k) for(int i=j;i<k;i++)

int deg=0;
void ofApp::setup(){
    ofSetFrameRate(60);
    ofSetBackgroundColor(0);
    ofSetColor(255);
    ofSetCircleResolution(64);
    ofNoFill();
    
}

void ofApp::update(){
}

void ofApp::draw(){
    deg++;
    ofTranslate(ofGetWidth()/2,ofGetHeight()/2); //原点中心に
    vector<float> xx,yy; //各点の座標を保管します
    float radiusx=200*cos(deg*DEG_TO_RAD); //radiusx,yは、色とりどりの線が集中する一点の座標を示します
    float radiusy=200*sin(deg*DEG_TO_RAD);
    rep(i,0,12){  //30度ずつずらして１２個の点を線で繋ぐことを考えます
        int radius,noiseValue=1;
        if(i%2==0)radius=200; //iの偶奇で、出っ張るか凹ますかをradiusの値を変えることで決めます。
        else {
            radius=150;
            noiseValue=ofMap(ofNoise(i*0.05,ofGetFrameNum()*0.01),0.0,1.0,-25.0,25.0);  //凹む点についてはノイズで適当にずらします
        }
        float x=radius*cos(((i*30)+noiseValue)*DEG_TO_RAD);
        float y=radius*sin(((i*30)+noiseValue)*DEG_TO_RAD);
        xx.push_back(x); //各点の座標を配列に格納します
        yy.push_back(y);
        
        ofDrawLine(x,y,0,0); //各点と、画面中心をまず結びます
        if(i)ofDrawLine(x,y,xx[i-1],yy[i-1]); //次に各点同士を結びます。外周の線が完成します
        
        ofColor c; //色とりどりの線の色を決めるためのofColor型変数です
        c.setHsb(255*((20.0*i)/255),255,255);  //iの値によってHSBのHを変えます。
        ofSetColor(c);
        ofDrawLine(x,y,radiusx,radiusy); //色とりどりの線を引きます
        ofSetColor(255);
        
    }
    ofDrawLine(xx[0],yy[0],xx[xx.size()-1],yy[yy.size()-1]); //１番目の点と１２番目の点はこれまででは結んでくれないので、別で書きます
}

2018-04-17

AOJ 0055 Sequence

AOJ

問題
数列の和 | Aizu Online Judge

解説
いくつデータが来るかわからないのでwhile(cin>>)を使って読める分だけ読みます。
最初に解答変数ansに初項nを代入しておきます。これで後は残りの９項を足せば良いので、forを9回回し、ループ変数の偶奇で２で割るか３で割るかを決めます。
最後にansを出力すれば良いです。

int main(){
    double n;
    while(cin>>n){
    double ans=n;
    rep(i,0,9){
        if(i%2==0)n*=2;
        else n/=3;
        ans+=n;
    }
    printf("%.10f\n",ans);
    }
    return 0;
}

2018-04-16

AOJ 0049 Blood Groups

AOJ

問題
血液型の分類 | Aizu Online Judge
各血液型の人数を数える問題です。

解説
入力には生徒の番号と謎のカンマが入っていますが、これらは問題を解く上では関係ありません。
数えるための配列を作って、v[0]~v[3]までをA,B,AB,O型のように、出力する順番で対応させます。
データはいくつ来るか分からないので、while(cin>>)を使って読める分だけ読みます。
実際に使うのはstring s だけで、このsによって配列のどの添字に足すかを分岐させます。

最後に配列の中身を４つ分出力して終了です。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define rrep()
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
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 a;
    char c;
    string s;
    int v[4]={};
     
    while(cin>>a>>c>>s){
        if(s=="A")v[0]++;
        else if(s=="B")v[1]++;
        else if(s=="AB")v[2]++;
        else v[3]++;
    }
    rep(i,0,4)cout<<v[i]<<endl;
     
     
     
    return 0;
}

2018-04-16

くるりんくるりん

openframeworks

円周上を回る円の円周上を回る円の円周上の・・・
完成形をぐっと想像したら、再帰関数をやればできそうな気がしたので書いたらできました。

くるりんくるりん
円周上を回る円の円周上を回る円の・・・。僕はこんなの大好きです#openframeworks

コードと説明は以下から。https://t.co/4b1m1osEZA pic.twitter.com/LfN2IvaZb3
— string s="ごつちやん"; (@gotutiyan_kapi) 2018年4月16日

止まっている円だけ普通にofDrawCircleで書いて、後は再帰関数でうまいことやります。
再帰関数の引数は半径を表すradius、再帰関数が何層まで深いとこまで行くかを持つcount、そして各円を回すために必要な角度情報degです。

今回作成したクラスPICでは、初期化関数init()で円を何個書くか、つまり再帰関数の深さを何層まで許すかを決めて、move()で最初のradiusを渡すことにしています。（特に理由はなくて、気づいたらこんな実装になってた）

また、小さい円ほど早く回らないと「ぐるぐるする　ところを　さらにぐるぐる　する」感じが無いのですが、この実装に意外と苦労してしまいまして。なぜか全ての円が一直線に並んで仲良く回転するようになってしまっていました。
このため「うーん」と唸りながら色々試していたら偶然上手く行ったので、正直仕組みがよく分かってません。

ただ確実に言えるのは、再帰の深さを表すcountは円が小さくなるほど増えるので、これを円の回る速さに使えば良いということです。ここは上手くできたと思います。
総評としては、もう少しスマートな実装がある気がしていますが、見てて楽しいものができたので良しとします。

#include "ofApp.h"
#define rep(i,j,k) for(int i=j;i<k;i++)

int diff=0;
class PIC{
    float x,y;
    int limit;  //limitは再帰の深さの最大値
public:
　//初期化
    void init(int elimit){
        limit=elimit;
    }
    
　
    void move(int radius,int count,float deg){
        if(count==limit)return;
　　//degに足す値にcountを使うことで、小さい円ほど早く回ってくれそう
        deg+=count*0.1+0.1;
        x=radius*cos((deg+count)*DEG_TO_RAD);
        y=radius*sin((deg+count)*DEG_TO_RAD);
        
        ofTranslate(x,y);
        ofDrawCircle(0,0,radius/2);
        
        //再帰を書きます。半径は半分に、countを１増やして、degはそれっぽく書きました。
        move(radius/2,count+1,deg+(count*0.5+1)*diff);
    }
};
PIC p;
float deg=0;
void ofApp::setup(){
    ofSetFrameRate(60);
    ofSetBackgroundColor(0);
    ofSetColor(255);
    ofSetCircleResolution(64);
    ofNoFill();
    
    p.init(5);
}

void ofApp::update(){
    diff++;
}

void ofApp::draw(){
    deg+=0.1;
    ofTranslate(ofGetWidth()/2,ofGetHeight()/2);
    ofDrawCircle(0,0,150);  //止まっている一番大きい円
    p.move(150,0,deg);  //再帰の親です。ここからlimit分再帰します
}

2018-04-14

収縮リング

openframeworks

円周上に配置された四角が収縮します。題名は普通に。

収縮リング
中央で重なるたびに個数が変わるなどします#openframeworks

コードとその解説は以下から。https://t.co/1kFsUch2L5 pic.twitter.com/nLiPZXD3T6
— string s="ごつちやん"; (@gotutiyan_kapi) 2018年4月13日

四角を三角関数を使って円周上に配置しています。この円の大きさは変数radiusで設定されていて、これも三角関数で変化させています。この時sinの値は-1~1ですが、都合上マイナスの値は要らないので、1を足すことで0~2に範囲をずらしています。

また、四角の個数は変数numが持っていて、円が中心で一瞬合わさった時に5~30の範囲でランダムに変化しています。そして変化する度に360度を個数で割ることで、全ての四角が円周上で均等に配置されるように並べ直しています。

座標系の移動は、最初にofTranslate(ofGetWidth()/2,ofGetHeight()/2)で画面中央に移動させた後、各四角を円周上に並べるための円周上の点x,y座標を算出して、そこに追加でofTranslate(x,y)します。
このようにして座標系を移動させれば、原点が四角を描く位置に来るので、ofDrawRectangle(-size/2,-size/2,size,size)で四角の中心が原点に来るように描きます。

ぱっと見簡単な動きをしていますが、いざ実装すると案外やることが多いなあという印象でした。

#include "ofApp.h"
#define rep(i,j,k) for(int i=j;i<k;i++)

int num=12; //numは四角の個数を表す

class PIC{
    float deg,x,y;
    float size,rotate;
    
    
public:
    float radius;
    //初期化関数
    void init(float edeg){
        deg=edeg;
        //sin(deg)^2+cos(deg)^2=1を利用して単位円を構成、それをradius倍して円周を作る
        float x=cos(deg*DEG_TO_RAD)*radius;
        float y=sin(deg*DEG_TO_RAD)*radius;
        rotate=0;
        radius=0;
        size=50;
    }
    
    void move(){
        rotate++;
        //radiusはフレーム数をラジアンとする三角関数で変化
        radius=(1+sin((ofGetFrameNum())*DEG_TO_RAD))*100;
        float x=cos(deg*DEG_TO_RAD)*radius;
        float y=sin(deg*DEG_TO_RAD)*radius;
        
        ofPushMatrix();
        //四角単体で回転させるためのところ
        ofTranslate(x,y);
        ofRotate(rotate);
        ofDrawRectangle(-size/2,-size/2,size,size);
        
        ofPopMatrix();
    }
};
//この配列vに、描かれる四角が格納される
vector<PIC> v(num);
void ofApp::setup(){
    ofSetFrameRate(60);
    ofSetBackgroundColor(0);
    ofSetColor(255);
    ofSetCircleResolution(32);
    ofNoFill();
    
    rep(i,0,num){
        v[i].init((360/num)*i);
    }
}

void ofApp::update(){
    
}

void ofApp::draw(){
    ofTranslate(ofGetWidth()/2,ofGetHeight()/2);
    
    //全ての四角が中心で合わさったという判定は、結局radiusが0になった時と同値
    if(v[0].radius==0){
        num=ofRandom(5,30);
        //配列の数をresizeで変更して、全て初期化
        v.resize(num);
        rep(i,0,num){
            v[i].init((360.0/num)*i);
        }
    }
    //実際に描きます
    rep(i,0,num){
        v[i].move();
    }
}

2018-04-12

２種リング

openframeworks

今まで円の描画はofDrawCircleを使って行っていましたが、この方法では「１つの円の中で複数の色を使う」ことができないので、ほかの方法で円を書いてみることにしました。
色の変わる方向を交互にしたのでこの題名に。

２種リング
クリックしたら色変わりますね#openframeworks

コードとその解説は以下から。（今回は詳しめな仕上がりです）https://t.co/3D8bsuo6Gv pic.twitter.com/yjdi7fSdPI
— ごつちやん (@gotutiyan_kapi) 2018年4月11日

円は、点を打つことでも描くことができます。三角関数で学んだ「単位円」がその代表で、sin^2*cos*2=1を利用して円を描くことができています。この単位円上に点を打っていくことによって、円が完成します。openframeworksは「点を打つ」ことができないので、今回はごく小さな円を描くことで対応しました。クリックすることで色がランダムに変化します。

円１つをクラスで作成し、このインスタンスを２次元に並べています。以下はそのクラスの処理の説明です。

今回は１つの円につき色を２色使っていますが、色の境目がよくわかるように補色にしています。補色は、ある色情報のRGBが（x,y,z）の時、(255-x,255-y,255-z)で表せます。全て255から引くだけです。

また、円をたくさん並べていることから、大きな円を構成するための小さな円があり、もちろんx,y座標の情報を持っています。この小さな円それぞれが持つy座標の値と、大きな円それぞれが持つ色の境目のy座標を示す変数posを比べて、その大小で色を塗り分けます。
三角関数の中身に書いているDEG_TO_RADは、「度数法(degree)からラジアン(radian)に変換する」という意味があるので、for文のループ変数0~359が、0~359度の１周分になっていて、それがラジアンに変換されることで三角関数がうまく働きます。

#include "ofApp.h"
#define rep(i,j,k) for(int i=j;i<k;i++)
float radius=50;

class PIC{
    int r,g,b;
    int x,y;
    int pos,speed;
    
    public :
//初期化関数
    void init(int i,int j){
        x=radius/2+radius*i*2;
        y=radius/2+radius*j*2;
        
        r=ofRandom(255);
        g=ofRandom(255);
        b=ofRandom(255);
        
        if((i+j)%2){  //色の変化の方向を互い違いにするため、iとjの和の偶奇で分ける
            pos=radius;
            speed=-1;
        }else {
            pos=-radius;
            speed=1;
        }
    }
    
    void move(){
        pos+=speed;
        if(pos<-radius || pos>radius) speed*=-1;
        
         rep(i,0,360){
             ofPushMatrix();
             ofTranslate(x+radius/2,y+radius/2);
　　　　//DEG_TO_RADで度数法からラジアンへ
             float x=cos((i)*DEG_TO_RAD)*radius;   
             float y=sin((i)*DEG_TO_RAD)*radius;
         
             if(y<pos)ofSetColor(r,g,b);
             else ofSetColor(255-r,255-g,255-b); //補色を作る
             ofDrawCircle(x,y,2,2);
             ofPopMatrix();
         }
    }
};

vector<vector<PIC>> v;

void ofApp::setup(){
    ofSetFrameRate(60);
    ofSetBackgroundColor(0);
    ofSetColor(255);
    ofSetCircleResolution(32);
    ofFill();
    
    int num=ofGetWidth()/(radius*2);  //numは円を書く個数
    // vectorをリサイズして使うことで、画面幅や半径が変わっても対応できる（はず）
    v.resize(num,vector<PIC>(num));  
    
    rep(i,0,num) rep(j,0,num) v[i][j].init(i,j);  //初期化をします
    
    
    
}

void ofApp::update(){
    
}

void ofApp::draw(){
    int num=ofGetWidth()/(radius*2);
    rep(i,0,num){
        rep(j,0,num){
            v[i][j].move();
        }
    }
}

 //クリックしたらinit()を発動させることで色をランダムに変化させる
void ofApp::mousePressed(int x, int y, int button){ 
    int num=ofGetWidth()/(radius*2);
    rep(i,0,num)rep(j,0,num)v[i][j].init(i,j);
}