lp6m’s blog

いろいろかきます

Schemeのメモ

Schemeのリストの操作

> (list 1 2)
(1 2);普通にリスト
> `(1 2)
(1 2);これもリスト
> (define a 1)
> (define b 2)
> (list a b 3)
(1 2 3);aとbは中身が展開される
> `(a b 3)
(a b 3);aとbは中身が展開されない
> `(,a ,b 3)
(1 2 3);aとbの中身が展開された どうやら`を利用したリストの中では変数の前にカンマをいれると中身が展開されるみたい
> (list (list 1 2) 3 4)
((1 2) 3 4);リストの中にリストがあるやつ
> `(`(1 2) 3 4)
(`(1 2) 3 4);なんで(1 2)の前に`があるのか謎い
> (equal? (list (list 1 2) 3 4) `(`(1 2) 3 4))
#f;上の二つは違うらしい・・・・・・・?
> `(,@(list 1 2) 3 4)
(1 2 3 4);,@をつかうと直後のリストのカッコが外れる
> `(,@`(1 2) 3 4)
(1 2 3 4);同様
> `(,@`(,a ,b) 3 4)
(1 2 3 4);合わせ技

バーサライタを作った

この記事はKMC Advent Calendar 2015 - Adventar22日目の記事です。
昨日はastatineさんのboost::property_treeでした。
kmc.hatenablog.jp

はじめに

KMCID:lp6mです。今年部費を払って以来一度もKMC部室に行ったことのない幽霊部員です。。
クリスマスといえばイルミネーションなので、LEDを使って何か作りたくなりました。
バーサライタというものが面白そうなので、作ってみることにしました。

バーサライタとは

バーサライタ、といってもピンと来ないかもしれませんが画像をみたらわかるかもしれません。
f:id:lp6m:20151222032139j:plain:w300
f:id:lp6m:20151222032146p:plain:w300

光が動いても、人間の目は残像としてそこに光があったかのように認識します。これを利用して、空間上に文字や絵を映し出す装置のことです。海外ではPOV(Persistent Of Vision)と呼ばれたりします。
LED部分がモーターで回転するものがオーソドックスですが、回転ではなく反復するものや、手で光源をもって振り回すことで残像を作り出すものもあります。

制作

電子工作の知識がほとんどないので、インターネットで情報を集めます。LED制御にはArduinoを使います。Arduinoめちゃくちゃ便利です。
色々な情報が手に入りました。

とりあえず部品を買ってきて、組み立てます。
ユニバーサル基板に、電池BoxとLEDとArduinoを乗せて、配線するだけです。電池boxの固定や、基盤とモーターとの固定に必要なネジ・ナットも購入します。穴あけには電動ドリルを利用します。
モーターは強力なほうがいいとおもったので、マブチモーターRS-380PHを使いました。モーターの固定にはパイプのL字固定具を使用しました。

モーターと基盤を接続する部分の部品選びにかなり時間がかかりました。大阪のデンデンタウンを歩き回っていました。
f:id:lp6m:20151222032400j:plain:w300

※1点固定だと重心がぶれて軸がぶれまくるので、2点以上で固定すべきかもしれません。

またモーターが必要とする電圧が高かったので電池駆動は諦め、ACアダプタを買おうとしたのですが、今後も工作をするのに必要だろうと思い電源装置を購入しました。高かった・・
f:id:lp6m:20151222033816j:plain:w300
めんどくさい配線作業を終えると、完成です。あとはプログラムを書きます
LED5個の縦バージョンも作成しました。
f:id:lp6m:20151222034647j:plain:w300

制御プログラム

Arduinoを使用したことある人はわかるとおもうのですが、Arduinoではloop()という関数が一定時間ごとに呼び出されます。
このloop()が呼び出される間隔がバーサライタでのLEDの表示切り替え間隔より大幅に遅く、悩まされました。

完成!!



いい感じです。撮影するときはシャッタースピードを遅くしたほうがいいです。このためにわざわざ
ProShot

ProShot

  • Edward Kezeli
  • 写真/ビデオ
  • ¥360
このアプリを買いました。

本当はしたかったこと

もともとはフルカラーバーサライタで絵を表示するぞ!と思ってAdafruitのフルカラーLEDスティックマイコン内蔵RGB 8LEDスティック: LED(発光ダイオード) 秋月電子通商 電子部品 ネット通販を使おうとしていました。
しかし回転させると・・
f:id:lp6m:20151222034243j:plain:w300
外側のLEDが内側のLEDの色の変化より遅れています。1本の信号線で複数のLEDをコントロールできるからなのか、応答速度が遅いようです。バーサライタ向きではないですね。
結局いろいろ試行錯誤したのですが、結局今回は赤色LEDでのバーサライタのみにしました。
絵を表示するときは、LEDが1周する間に1枚の絵の分光らせないといけないので、回転速度なども検出しないといけません。このために赤外線センサのRPR-220などを利用するとよいです。

感想

電子工作も工作も、知識がないのにするのは大変ですが、完成したときはとても楽しいです。
ぜひみなさんも作ってみてください!!
f:id:lp6m:20151222035905j:plain:w300(試行錯誤途中の写真。上手くやればAdafruitのスティックでもフルカラーバーサライタ作れるかもしれない)
あしたはtaiseiさんの「Unreal Engine 4を触る」です。楽しみですね!

CODE THANKS FESTIVAL 2015に参加しました

去年

lp6m.hatenablog.com

”””来年は普通に予選突破できるレベルまで上げたい”””なんて言ってたのに結局何もしなかった・・・のでまたTHANKSに出た。(出れるだけありがたい)

出発〜開会式

行きは飛行機に乗った。離陸直前にAOJの1126The Secret Number | Aizu Online Judgeを通した。



羽田からバスにのってなんとかテレコムセンターについた。
去年と同じ場所だったので迷わなかった。テレコムセンター駅で外でつったっていたのは@kenkooooさんだったみたい。すごい人外に立たせるのか。
参加賞のCODE THANKS FESTIVAL Tシャツをもらった。
弁当、位置的に焼肉弁当を手に入れられなかったつらい。去年は近かったから焼肉弁当手に入れた。
開会式、ちょくだいさんの走り方がかわいかった。

コンテスト

去年はFirst ACにアマゾンギフト券があったのでC問題あたりでFirst ACできるだろうと思ってCからといた。
C 02:04 日本語が一番簡単なのがこの問題. なんとかboundとかいうvectorの便利なやつしらないのでちゃんと復習しようとおもった
A 06:09 なにをあせってたのかすごく時間かかってる・・・?もっとはやく解けただろって感じ
B 17:57 なんかこれも謎かった(結構時間潰してる人多いみたい)簡単なのになんかダメダメ
E 46:27 そもそもTに含まれるアルファベット全部がSに含まれてないとダメ,
あとはTに含まれる文字列以外をSから全部除去した文字列にTが部分文字列として含まれてなかったらダメ,でいけると気づいた(気づくのおっそ まあ自分で気付けたからいいか)string.findみたいなのはなんか覚えてた。

D 57:37 これはまあ10分程度でかけたし特に詰まったりしなかったのでよしとする

去年は5完で42分なのでちょっとおそいかんじ。

H を触る。累積和をとればはやいぞ!とおもって累積和のとりかたは知ってたから実装する。めっちゃ汚いけどサンプルあったし提出してみたらACしてて何個かTLE 提出したのはこれ(コンテストから数日しないとURLみれなさそう)http://code-thanks-festival-2015.contest.atcoder.jp/submissions/587635


うーんうーんと言ってる間にコンテスト終了

Hはしゃくとりでオーダー落とすんかなとおもって解説前につぶやいやらkenkooooさんにふぁぼられた。解説でもしゃくとりって言ってた。
部分点ほしかったかなあ。。

そのあとは解説聞いて、懇親会とかでわいわいしてた。みんなフレンドリーで優しかった。
スタンプ全部あつめたのうれしい


帰りは新幹線 帰る時間おそくてつらかった。

いやなんていうか来年は決勝でるって決めたんだし出るぞ。ちゃんと毎日練習するんやで。

追記

CはFAでした。ありがたい。

UnityのShaderLabでわからないこと

分からないことのメモなので、解決策があれば教えてほしいです。

半透明だけど輪郭は色が濃くなるようなシェーダを書いた。

球体のオブジェクトに割り当ててみた。
Sceneビューでは見えるんだけど、Gameビューでは見えない。
他のマテリアルを割り当てるとGameビューで見えるのに、自分でかいたシェーダを使ったマテリアルだと、Gameビューでなにも表示されない。
f:id:lp6m:20150926160602p:plain

なんでこんなことになるんでしょうか・・・・誰かおしえてください。 @まで。

Xcodeでテキストファイルを読み込めないときの解決策

全然たいしたことじゃないのにこれで結構時間くうことあるのと、日本語でググってもなかなかヒットしなかったのでメモ。

XcodeでCとかC++を書いていて、コードが間違っているわけではないのに、ファイルを読み込めないときがある。

    FILE *fp;
    char *filename = "load.txt";
    if ((fp = fopen(filename, "r")) == NULL) {
        fprintf(stderr, "%sのオープンに失敗しました.\n", filename);
        exit(EXIT_FAILURE);
    }else{
        printf("成功!!\n");
    }

解決策

①Product->Scheme->Edit Scheme...を選ぶ.
f:id:lp6m:20150804131530p:plain
②OptionタブのUse Custom Working Directoryをオンにして、読み込みたいテキストファイルがあるディレクトリを選択.
f:id:lp6m:20150804131535p:plain
動きました。

終わり。

英語で調べたらすぐでてくるんだけど。これの通りです。stackoverflow.com

何回か同じ処理を繰り返すタイプの探索 AOJ1174同色パネル結合

あんまり自分で解いた問題をここに書くことはないけどメモとして。

自分は初めてアルゴリズムっぽいアルゴリズムを勉強したのは、迷路の問題
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder

幅優先探索深さ優先探索はかける。いや深さは迷路だとかけるのに他になるとあれ??再帰呼び出しはどこにかけばいいんだ?再帰がストップする部分はどこにかけばいいんだ?となってしまう。

さて、
1回の試行で選択肢がk個かあって、その試行をn回かするタイプの問題で、単純にk^n回調べればいい問題がある。nが問題で決まっている場合はn重ループをかけばいいんだけど、ダサいのでちゃんと再帰で書く。

再帰しまくりになるとスタックサイズがデカくなって死んでしまうらしい。回避方法はよくしらないので困ってから考えることにする。

0と1をn個ならべるときの全ての場合の列挙

たとえばn = 3のときは000, 001, 010, 011, ... 111というように並べたい.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int S[10];
int n;
void rec(int k){
	if(k == n){
		REP(i,n) cout << S[i] << " ";
		cout << endl;
		return;
	}
	rec(k+1);
	S[k] = 1;
	rec(k+1);
	S[k] = 0;
}

void makecombination(){
	REP(i,n) S[i] = 0;
	rec(0);
}

int main(){
	n = 5;
	makecombination();
}

イメージはなんか、S[k] = 1;でk文字目を1に変更してrec(k+1);で再帰するんだけど、再帰して次の場合を考えるときにはその変更はなかったことにしたい、だからS[k] = 0;する、みたいな感じ。

0からp未満の数字をn個ならべるときの全ての場合の列挙

void rec(int k){
	if(k == n){
		REP(i,n) cout << S[i] << " ";
		cout << endl;
		return;
	}
	rec(k+1);
	REP(i,p){
		S[k] = i;
		rec(k+1);
		S[k] = 0;
	}
}

これも同じようにかける。なんかこう、樹形図をイメージしていくとわかる(自分用のメモなので樹形図は略、ノートに書いた)

同じようにしてAOJ1174 同色パネル結合を解いた。

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int h,w,c;
int data[100][100];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int ans;

int check(int grid[100][100]){
	int issearched[100][100] = {0};
	issearched[0][0] = 1;
	int cnt = 1;
	queue<int> qx,qy;
	qx.push(0); qy.push(0);
	while(!qx.empty()){
		int x = qx.front(); int y = qy.front();
		qx.pop(); qy.pop();
		REP(i,4){
			int nx = x + dx[i]; int ny = y + dy[i];
			if(nx > -1 && ny > -1 && nx < h && ny < w && issearched[nx][ny] == 0){
				issearched[nx][ny] = 1;
				if(grid[nx][ny] == c){
					cnt++;
					qx.push(nx); qy.push(ny);
				}
			}
		}
	}
	return cnt;
}

void change(int col,int grid[100][100]){
	int issearched[100][100] = {0};
	queue<int> qx,qy;
	qx.push(0); qy.push(0);
	int stcol = grid[0][0];
	grid[0][0] = col;
	while(!qx.empty()){
		int x = qx.front(); int y = qy.front();
		qx.pop(); qy.pop();
		REP(i,4){
			int nx = x + dx[i]; int ny = y + dy[i];
			if(nx > -1 && ny > -1 && nx < h && ny < w && issearched[nx][ny] == 0){
				issearched[nx][ny] = 1;
				if(grid[nx][ny] == stcol){
					grid[nx][ny] = col;
					qx.push(nx); qy.push(ny);
				}
			}
		}
	}
}

int solve(int n,int grid[100][100]){
	int bgrid[100][100];
	REP(i,h) REP(j,w) bgrid[i][j] = grid[i][j];

	if(n == 4){/*終了条件*/
		change(c,grid); /*最後は1つでも多くしたいので色はc*/
		ans = max(check(grid),ans);/*結果を更新*/
	}else{
		REP(i,6){
			change(i,grid);
			solve(n+1,grid);
			REP(i,h) REP(j,w) grid[i][j] = bgrid[i][j];	//パネルの状態をもどす
		}
	}
	return ans;
}

int main(){
	while(1){
		cin >> h >> w >> c;
		if(h==0) break;
		c--;
		ans = 0;
		REP(i,h) REP(j,w) cin >> data[i][j];
		REP(i,h) REP(j,w) data[i][j]--;
		cout << solve(0,data) << endl;
	}
}

solve()の中が深さ優先探索。たぶんICPC2015模擬国内予選のC問題も同じように(1回の試行で9通りの選択肢があって、それを5回する)書ける。

ICPC2015国内予選に参加しました

ICPC2015国内予選に参加しました. 去年はKMC(京大マイコンクラブ)の競技プログラミング練習会に参加していたメンバーと参加したけどレベルが違うので今年は2回生の情報学科の人たちで出た.
記念にメモ.
※去年の参加記 2完: LP6m メモ ICPC予選に参加してきました

結果は3完、90位/316チーム.
ACM-ICPC 2015 国内予選順位表

A問題 開始11分

forループで試すだけ.焦って問題文の意味がとれなくて時間がかかった.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
#define ll long long
int m,nmin,nmax;
int data[200];
using namespace std;
int main(){
	while(1){
		cin >> m >> nmin >> nmax;
		if(m == 0) break;
		REP(i,m) cin >> data[i];
		
		int ans =0;
		int anss = nmin;
		FOR(i,nmin,nmax+1){
			if(ans<=abs(data[i-1]-data[i])){
				ans = abs(data[i-1]-data[i]);
				anss = i;
			}
		}
		cout << anss << endl;
	}
}

B問題 開始24分

これも試すだけ.一発でサンプルが通ったので嬉しかった.
実はこのとき29位くらいにいた気がする.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
#define ll long long
using namespace std;

int n;
int w[50];
int ans = 0;
int test[5] = {5,7,5,7,7};
bool solve(int gyo){
	int nowgyo = gyo;
	int testpos = 0;
	int nowac = 0;
	for(;;){
		if(nowac < test[testpos]){
			if(nowac+w[nowgyo] > test[testpos]){
				return false;
			}else{
				nowac += w[nowgyo];
				nowgyo++;
				if(nowac == test[testpos]){
					nowac = 0;
					testpos++;
				}
			}
		}
		if(testpos==5) return true;
	}
}

int main(){
  while(1){
	cin >> n;
	if(n==0) break;
	REP(i,n) {
		string tmp;
		cin >> tmp;
		w[i] = tmp.size();
	}
	
	REP(i,n){
		if(solve(i)) {
			ans = i;
			break;
		}
	}
	cout << ans+1 << endl;
  }
  

}

C問題 開始131分

逆ポーランド法みたいなやつだからスタックつかえばいけるとわかって実装したけどWA.
ドットの数が減るのは数字のあとしかないと考えていたがそうではなかったので訂正するもWA.

この辺で開始70分くらいでは???っていいながらダウンロードしたテストケースを手で解いていた。ほとんどあってて意味わからんっていってチームみんなで笑ってた。3問とかないと・・って思ってた。

デバッグしてたらとてつもないミスに気付いた. スタックに数字と記号を積んでいたのだが、+と*を10と100で代用していた(入力が0から9までしかないから大丈夫と思い込んでいた)計算途中で10,100になるケースで死んでいることに気付いた. -10, -100にしたら通った.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)a; i<(int)(b);i++)
using namespace std;

long long int n;
stack<long long int> st;

void mydebug(){
	return;
	stack<long long int> st2 = st;
	while(!st2.empty()){
	if(st2.top()==-10) cout <<'*' <<':';
	 else if(st2.top()==-100) cout <<"+ : ";
	 else cout << st2.top() << ":";
	st2.pop();
	}
	cout << endl;
}

void calcstack(){
	vector<long long int> array;
	long long int enzansi;
	mydebug();
	while(!st.empty()){
		long long int elem = st.top();
		st.pop();
		if(elem==-10||elem==-100){
			if(elem == -10) enzansi = 0;
			else enzansi = 1;
			break;
		}else{
			array.push_back(elem);
		}
	}
	long long int ans;
	if(array.size()!=0){
		if(enzansi==0){
			ans = 1;
			REP(i,array.size()) ans*=array[i];
		}else{
		  ans = 0;
		  REP(i,array.size()) ans+=array[i];
		}
		st.push(ans);
	}
	mydebug();
}

int main(){
	while(1){
	  long long int pcnt = 0;
	  long long int oldpcnt = 0;
	  while(!st.empty()) st.pop();
	  cin >> n;
	  if(n==0) break;
	  REP(i,n){
	  	string tmp;
		cin >> tmp;
		pcnt = 0;
		while(1){
			if(tmp[pcnt]!='.'){
				break;
			}else{
				pcnt++;
			}
		}
		long long int num;
		long long int a;
		if(tmp[pcnt]=='*'){
			a = -10;
		}else if(tmp[pcnt]=='+'){
			a = -100;
		}else{
		  num = tmp[pcnt]-'0';
			a = num;
		}
		if(oldpcnt > pcnt){
			REP(j,oldpcnt-pcnt)calcstack();			   
		}
		st.push(a);
		oldpcnt = pcnt;
		mydebug();
	  }
	while(st.size()!=1) calcstack();
	  cout << st.top() << endl;
	}
}

あとは適当に遊んでいた.

今年の問題はどうやら難しくて差がつきにくかったっぽい.予選突破したチームおめでとうです〜〜〜

来年は4問ときたいです!!!
1ヶ月後の試験 is 何って感じだ.