gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

2018/9/4 虹色四角の周期性回転

虹色の四角を何重にも描いて、回転をすることで良い感じになりました。
やってることはよくある回転ですが、何回見ても綺麗ですね。
f:id:gotutiyan:20180904232406p:plain

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;

アステロイド曲線


この前にリサージュ曲線を描きましたが、次はアステロイド曲線です。リサージュ曲線の記事は以下です。
リサージュ曲線 - 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) 

問題
Osaki | Aizu Online Judge

電車が走行する時間帯が与えられるので、最低電車が何台あれば運行できるかを出力する。

解説
入力の運行時間が少しでも被っていれば、その時間帯は複数の電車が運行しないと矛盾してしまいます。よってすべての運行時間を見て、運行時間が被っている時間帯の個数の最大値を求めれば良いです。

具体的な方法としては、時間帯を秒単位で表す配列を用意して、運行時間帯中の要素を全て+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;
}

ACM-ICPC 「月曜土曜素因数」

2008のB問題です。

問題
Monday-Saturday Prime Factors | Aizu Online Judge
素数とは、「1と自分以外に約数を持たないもの」です。普段はこれを「すべての自然数」について考えていますが、これを「7で割ると1または6余る数の集合」に絞って考えるとどうなるかという問題です。

解説
この問題は以下のステップを踏みます。
1 「7で割ると1または6余る数の集合」を作る(月曜土曜数の配列 ms
2 作った集合を元に、月曜土曜素数の集合をさらに作る (月曜土曜素数の配列 msprime

3 各入力に対して月曜土曜素数で割っていき、素因数になるかどうか調べる(月曜土曜素因数)

ステップ1
今回、与えられるq個のデータの上限は高々300000未満であることに注意です。
7で割ると1または6余る集合は、
・( i % 7==1 || i % 7==6) となるような i を集める
・iを増やしながら、7 * i + 1 と 7 * i + 6 を集める
で作ることができます。僕は後者で行い、msという配列に格納しました。

ステップ2
素数判定をするにあたり、
・Nの素数が存在する時、ルートN 以下しかの値しか存在しない
ということは必須です。

よって、すべての月曜土曜数 ms[i] について、sqrt(ms[i]) 以下のms[j]で割っていき、一度も割りきれなければそれは月曜土曜素数です。これをmsprime[] に格納します。

スッテプ3
入力に対して、msprime[i] で割ってみて、割り切れたらその都度出力します。

#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_MAX
#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(){
 //msが月曜土曜数、msprimeが月曜土曜素数
    vector<int> ms,msprime;
 
        //ステップ1
        for(int i=0;;i++){
            if(i==0)ms.pb(7*i+6); //1は月曜土曜数にはならない
            else {
                if(7*i+1>=300000)break;
                ms.pb(7*i+1);
                ms.pb(7*i+6);
            }
        }
         
        //ラムダ式を使って、月曜土曜素数の判定関数を作る
        auto isPrime=[&](int x){
            for(int i=0;(ms[i]<=sqrt(x)+1);i++){
                if(x%ms[i]==0){
                    return false;
                }
            }
            return true;
        };
        
  //msprimeに素数を格納する
        rep(i,0,ms.size()){
            if(isPrime(ms[i])) msprime.pb(ms[i]);
        }
 
 
    int n;
    while(cin>>n && n!=1){
        cout<<n<<":";
 
        rep(i,0,msprime.size()){
            if(n%msprime[i]==0){  msprime[i]で割れたらその都度出力
                cout<<" "<<msprime[i];
            }
        }
        cout<<endl;
 
    }
 
    return 0;
}