ICPC2016国内予選に参加しました
今年も参加しました.情報学科3人で.
2年前: 126位 LP6m メモ ICPC予選に参加してきました
1年前: 90位 ICPC2015国内予選に参加しました - lp6m’s blog
今年: 67位 3完
去年は「来年は4完するぞ」とか言ってたのにできなかった.
去年終わってから競プロの勉強をぜんぜんしてこなかったし,前日までHardware and Software Laboratory Project 3B (Software Part) に追われていたのが完全に悪い.それでもとりあえずいま自分ができる実力を発揮しようということで頑張った.
A問題 4分
2重forループ回しただけ.
チーム全員で問題を読んだ.自分は後ろでコードを眺めて指示したりした.2分でかいて4分でACしたっぽい.
ちなみにこの時点では15位でイエーイとか言ってた.
int main(){ while(1){ int n; cin >> n; if(n == 0) break; ll int a[1001]; for(int i = 0; i < n; i++){ cin >> a[i]; } long long int res = 1000000000; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == j) continue; res = min(res, abs(a[i] - a[j])); } } cout << res << endl; } }
B問題 24分
自分はCを読んでいたので問題を見ていない.ちょっとだけハマったらしいけど焦ってたからだと思う.
int main(){ while(1){ int n; cin >> n; if(n == 0) break; map<char, int> m; for(int i = 0; i < 26; i++){ m[i + 'A'] = 0; } char tmp[101]; for(int i = 0; i < n; i++){ cin >> tmp[i]; } for(int i = 0; i < n; i++){ char c = tmp[i]; m[c]++; vector<pair<int, char> > result(26); for(int i = 0; i < 26; i++){ result.push_back(make_pair(m['A' + i], 'A' + i)); } sort(result.begin(), result.end()); reverse(result.begin(), result.end()); int sub = result[0].first - result[1].first; if(sub > n - i - 1){ cout << result[0].second << " " << i + 1 << endl; break; } if(i == n - 1) cout << "TIE" << endl; } } }
C問題 70分
自分はCをずっと眺めていたのにふるいすれば終わりに気がつかなかった。言われて実装したらなんかなかなか処理が終わらない.ぼくが無駄な処理してるところに気がついて直してAC
int oksize = 7400000; int main(){ int n,m; bool ok[oksize]; while(1){ cin >> m >> n; if(n == 0 && m == 0) break; REP(i,oksize) ok[i] = true; REP(i,m) ok[i] = false; int cnt = 0; int tmp = m; REP(j,n){ for(int i = 0; i * tmp < oksize; i++){ if(i*tmp < m) continue; ok[i*tmp] = false; } FOR(i,tmp,oksize){ if(ok[i]){ tmp = i; break; } } } cout << tmp << endl; } }
D問題 提出できず
C問題をACしてとりあえず去年と同じなのでホッとした.D問題を読んだ.ダルマのどこを崩すかって枝分かれしていくわけだからdfsを思いついたので一番競プロをまじめにやってるチームメイトに書いてもらった.サンプルが通ったので入力データをダウンロードして実行したが全然終わらない.とりあえずメモ化できるのでメモ化してみたんだけど、全然早くならなかった.
結局そのまま試合終了まで考えてもどうにもならなくて終わってしまった.
以下、遅いコード
int n; int ans = 0; map<vector<int> , int> m; int solve(vector<int> v){ // cout << v.size() << endl; if(m.find(v) != m.end()) return m[v]; m[v] = n - (int)v.size(); for(int i = 0; i < ((int)v.size() - 1); i++){ //cout << "jhe" << v.size() <<" " << i << endl; if(abs(v[i] - v[i + 1]) <= 1){ vector<int> newv = v; newv.erase(newv.begin() + i); newv.erase(newv.begin() + i); m[v] = max(solve(newv), m[v]); } } return m[v]; } int main(){ while(1){ cin >> n; if(n == 0) break; vector<int> w; for(int i = 0; i < n; i++){ int tmp; cin >> tmp; w.push_back(tmp); } ans = 0; m.clear(); cout << solve(w) << endl; } }
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を使って何か作りたくなりました。
バーサライタというものが面白そうなので、作ってみることにしました。
バーサライタとは
バーサライタ、といってもピンと来ないかもしれませんが画像をみたらわかるかもしれません。
光が動いても、人間の目は残像としてそこに光があったかのように認識します。これを利用して、空間上に文字や絵を映し出す装置のことです。海外ではPOV（Persistent Of Vision）と呼ばれたりします。
LED部分がモーターで回転するものがオーソドックスですが、回転ではなく反復するものや、手で光源をもって振り回すことで残像を作り出すものもあります。
制作
電子工作の知識がほとんどないので、インターネットで情報を集めます。LED制御にはArduinoを使います。Arduinoめちゃくちゃ便利です。
色々な情報が手に入りました。
とりあえず部品を買ってきて、組み立てます。
ユニバーサル基板に、電池BoxとLEDとArduinoを乗せて、配線するだけです。電池boxの固定や、基盤とモーターとの固定に必要なネジ・ナットも購入します。穴あけには電動ドリルを利用します。
モーターは強力なほうがいいとおもったので、マブチモーターRS-380PHを使いました。モーターの固定にはパイプのL字固定具を使用しました。
モーターと基盤を接続する部分の部品選びにかなり時間がかかりました。大阪のデンデンタウンを歩き回っていました。
- RS-380PHの軸(2.3mm)から3mmに変換するアダプタ デジットBlog:レインボープロダクツ メカトロパーツの新製品が登場！
- 3mm軸ジョイント レインボープロダクツ アルミダブルストッパー内径3mm
- 3mmネジつきシャフト
- 3mm 3mm軸アダプタ
※1点固定だと重心がぶれて軸がぶれまくるので、2点以上で固定すべきかもしれません。
またモーターが必要とする電圧が高かったので電池駆動は諦め、ACアダプタを買おうとしたのですが、今後も工作をするのに必要だろうと思い電源装置を購入しました。高かった・・
めんどくさい配線作業を終えると、完成です。あとはプログラムを書きます
LED5個の縦バージョンも作成しました。
制御プログラム
Arduinoを使用したことある人はわかるとおもうのですが、Arduinoではloop()という関数が一定時間ごとに呼び出されます。
このloop()が呼び出される間隔がバーサライタでのLEDの表示切り替え間隔より大幅に遅く、悩まされました。
完成!!
https://twitter.com/lp6m/status/678990382756040704
https://twitter.com/lp6m/status/678955161817972736
いい感じです。撮影するときはシャッタースピードを遅くしたほうがいいです。このためにわざわざ
本当はしたかったこと
もともとはフルカラーバーサライタで絵を表示するぞ！と思ってAdafruitのフルカラーLEDスティックhttp://akizukidenshi.com/catalog/g/gM-08435/を使おうとしていました。
しかし回転させると・・
外側のLEDが内側のLEDの色の変化より遅れています。1本の信号線で複数のLEDをコントロールできるからなのか、応答速度が遅いようです。バーサライタ向きではないですね。
結局いろいろ試行錯誤したのですが、結局今回は赤色LEDでのバーサライタのみにしました。
絵を表示するときは、LEDが1周する間に1枚の絵の分光らせないといけないので、回転速度なども検出しないといけません。このために赤外線センサのRPR-220などを利用するとよいです。
感想
電子工作も工作も、知識がないのにするのは大変ですが、完成したときはとても楽しいです。
ぜひみなさんも作ってみてください！！
（試行錯誤途中の写真。上手くやればAdafruitのスティックでもフルカラーバーサライタ作れるかもしれない）
あしたはtaiseiさんの「Unreal Engine 4を触る」です。楽しみですね！
CODE THANKS FESTIVAL 2015に参加しました
出発〜開会式
行きは飛行機に乗った。離陸直前にAOJの1126http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1126を通した。
https://twitter.com/lp6m/status/672910101120880640
https://twitter.com/lp6m/status/672938739413286912
羽田からバスにのってなんとかテレコムセンターについた。
去年と同じ場所だったので迷わなかった。テレコムセンター駅で外でつったっていたのは@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
https://twitter.com/lp6m/status/673014031096025090
https://twitter.com/lp6m/status/673014419673055232
うーんうーんと言ってる間にコンテスト終了
Hはしゃくとりでオーダー落とすんかなとおもって解説前につぶやいやらkenkooooさんにふぁぼられた。解説でもしゃくとりって言ってた。
部分点ほしかったかなあ。。
https://twitter.com/lp6m/status/673019270352142336
そのあとは解説聞いて、懇親会とかでわいわいしてた。みんなフレンドリーで優しかった。
スタンプ全部あつめたのうれしい
https://twitter.com/lp6m/status/673176055545397248
帰りは新幹線 帰る時間おそくてつらかった。
いやなんていうか来年は決勝でるって決めたんだし出るぞ。ちゃんと毎日練習するんやで。
UnityのShaderLabでわからないこと
分からないことのメモなので、解決策があれば教えてほしいです。
半透明だけど輪郭は色が濃くなるようなシェーダを書いた。
球体のオブジェクトに割り当ててみた。
Sceneビューでは見えるんだけど、Gameビューでは見えない。
他のマテリアルを割り当てるとGameビューで見えるのに、自分でかいたシェーダを使ったマテリアルだと、Gameビューでなにも表示されない。
なんでこんなことになるんでしょうか・・・・誰かおしえてください。 Twitter:@lp6mまで。
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...を選ぶ.
②OptionタブのUse Custom Working Directoryをオンにして、読み込みたいテキストファイルがあるディレクトリを選択.
動きました。
終わり。
英語で調べたらすぐでてくるんだけど。これの通りです。
stackoverflow.com
何回か同じ処理を繰り返すタイプの探索 AOJ1174同色パネル結合
あんまり自分で解いた問題をここに書くことはないけどメモとして。
自分は初めてアルゴリズムっぽいアルゴリズムを勉強したのは、迷路の問題
C - 幅優先探索
幅優先探索や深さ優先探索はかける。いや深さは迷路だとかけるのに他になるとあれ？？再帰呼び出しはどこにかけばいいんだ？再帰がストップする部分はどこにかけばいいんだ？となってしまう。
さて、
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回する）書ける。
