Atcoder ABC99-D GoodGrid

問題

D - Good Grid

色iを色jに塗り替える時に感じる違和感と、色が塗られたマス目の情報が与えられる。この時、(i+j)%3=(x+y)%3となるような(i,j),(x,y)のマス目は全て同じ色に塗らなければならない。感じる違和感の最小値を求める。

解説

全探索をします。
前準備として、v[0,1,2][0,1,2,,c]の配列において、「v[i][j]:=(x+y)%3==i のマス目における色j の出現回数」とすることで、(x+y)%3=0,1,2それぞれについて、最初はどの色が何個あるのかを持っておきます。

次に、i,j,kの3重ループを0〜cで回し、i≠j≠kの時、(x+y)%3=0のマス目をi, =1のマス目をj, =2のマス目をkで塗るような全探索をします。これによって最小値を調べ、出力すれば良いです。i,j,kを決めれば、あとは(x+y)%3のそれぞれについて、「今塗られている色の個数」*「その色をi,j,kに変える時の違和感」の総和をとります。

以下、コードです(#includeは省略)

int main (){
    int n,c;cin>>n>>c;
    vector<vector<int>> v(3,vector<int>(c)),cost(c,vector<int>(c));
    rep(i,0,c)rep(j,0,c)cin>>cost[i][j]; //違和感
    rep(i,0,n)rep(j,0,n){
        int x;cin>>x;
        v[((i+1)+(j+1))%3][x-1]++;
    }

    int ans=1e18;
    rep(i,0,c){ //%3==0をiに
        rep(j,0,c){  //%3==1をjに
            if(i==j)continue;
            rep(k,0,c){ //%3==2をkにするとき
                if(i==k || j==k)continue; 
                int ret=0;
                rep(ind,0,3){ //%3の値
                    int x;
                    if(ind==0)x=i;
                    else if(ind==1)x=j;
                    else if(ind==2)x=k;
                    rep(val,0,c){
                        ret+=v[ind][val]*cost[val][x];
                    }
                }
                ans=min(ans,ret);
            }
        }
    }
    cout<<ans<<endl;
}

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);  //操作1
    dfs(x+y,x-y,ct+1); //操作2
    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;
}


他には、単純に1文字ずつ見ていく方法があります。

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]は以下のようになります。
f:id:gotutiyan:20181031185446p:plain
.pdeと同じフォルダに画像を置いています。

次に、これを出力すれば以下のような中身のフォルダができます。(画像はmac
f:id:gotutiyan:20181031185555p:plain


これらの起動ファイルを実行しても画像は表示されないので、自分で置きます。(画像はmac
f:id:gotutiyan:20181031185835p:plain

これで起動すると画像が表示されるようになりました。
windowsでも同様に画像を配置すれば良いです。

ノイズ木構造

再帰関数で二分木をどわーっと書いて、点をノイズで揺らしてみました。僕の好きなノイズと再帰でごり押しした感じの作品ですが、動的に生成される木構造が良いですね。本当はノードが増えたり減ったりしたときに、辺をニョキッと滑らかに生やしたかったんですが、やり方がよく分かりませんでした。。

コードは以下の通りです。最初の一回だけ、nowDeepが0なので、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

方向ベクトルを斜めにして、軌跡を点線に。さらに円の内部を動く色付きのものと、円の外を動く白色のものに分けてみました。


白いものは画面外に出たとき、もしくは円の中に入ったときに、強制的に引き戻す方向に変えさせます。
色付きのものは、円を出ようとしたときに、強制的に引き戻す方向に変えさせます。

引き戻す方向は案外簡単に設定できて、引き戻す条件に合致した瞬間のx,y座標をX,Yとおけば、「出て行く」動きを引き戻すなら、X,Yそれぞれの反対の符号を持つdir[ ]を、「入りこむ」動きを引き戻すなら、X,Yそれぞれと同じ符号を持つ dir[ ]を足せば良いです。

また、軌跡を表す線を点線にしましたが、これは軌跡を格納している配列において、「5で割った余りが0,1,2となるような添字の時だけline()を引く」ということをしています。
つまり、3ピクセル描いて2ピクセル描かない、をひたすら繰り返します。

コードは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なら円内部の色付き、1なら円外部の白
  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()」を用いることで、アドレスを取り直して追加することができ、配列の要素が書き換わらなくなりました。

感想

C++vectorの感覚でやっていたら痛い目を見ましたね・・