何回か同じ処理を繰り返すタイプの探索 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回する)書ける。
ICPC2015国内予選に参加しました
ICPC2015国内予選に参加しました. 去年はKMC(京大マイコンクラブ)の競技プログラミング練習会に参加していたメンバーと参加したけどレベルが違うので今年は2回生の情報学科の人たちで出た.
記念にメモ.
※去年の参加記 2完: LP6m メモ ICPC予選に参加してきました
結果は3完、90位/316チーム.
http://storage.googleapis.com/icpcsec/icpc2015-domestic-live/standings.html
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 何って感じだ.
AVのタイトルをマルコフ連鎖のプログラムにかけた
深夜に思いついて1時間くらい遊んだだけの話。もっとGTAのMODをビルドした話とかXamarinでアプリつくってる話もあるけどめんどくさいので書かない.
適当にスクレイピングしてAVのタイトルをダウンロードする
rubyはしらないのでCっぽいのでてきとうにgoogleにruby whileとかruby for ってしらべてかいてるのでてきとう。
マルコフ連鎖のプログラムにかけて何回か表示する
ここを参考にした.
AVのタイトルは比較的短いものもあれば長いものもあるので、分けてみた.
エラーもでることあるけどとりあえず何回か実行した結果
長いタイトルの場合
短いタイトルの場合
あんまりうまくいかなかった。いろんな種類がありすぎるし、もともとのデータをなんらかの方法で絞れば良さそう。
頑張ったらおもしろくなるかもしれないし、だれかやってみて
・・・・オマ○コ航空・・・
cocos2d-x: 角丸のボタン用の画像をつくる
cocos2d-xでゲームを作ってる。わからないことだらけで全然進まない。少しずつわかってきた感じ。
角丸のボタンってデザインがいいかんじなのでゲームで使いたいと思ってまああるだろうとおもって調べてみたら公式にはない。
ここにスプライトに角丸のマスクをする方法が載ってたのでコピー。(ほとんどこれのおかげ.自分で追加したの10行程度・・)
http://discuss.cocos2d-x.org/t/how-can-i-create-sprite-with-rounded-corner/15403/7discuss.cocos2d-x.org
あとは適当に色設定したり、文字表示する用にした。
RoundedBoxSpriteというクラス名にした。
RoundedBoxSprite::setParam(Size size,Color3B BGColor,float CornerRadius,int CornerSegment,std::string String,Color3B FontColor,int FontSize)
CornerRadiusは角の円の半径,CornerSegmentは角あたりの点の数(増やすほど円に近づく).
※2015 04/03 修正
cocos2d-x Ver3.2だと正常に動作しません(スプライトを描画すると背景が真っ白になる)
解決策:
AppDelegate.cppに以下を追加
void AppDelegate::initGLContextAttrs() { //set OpenGL context attributions,now can only set six attributions: //red,green,blue,alpha,depth,stencil GLContextAttrs glContextAttrs = {8, 8, 8, 8, 24, 8}; GLView::setGLContextAttrs(glContextAttrs); }
AppDelegate.hのAppDelegateClassのpublicメソッドに
virtual void initGLContextAttrs();
を追加.
サンプル:
使い方はこんな感じで。
#include "RoundedBoxSprite.h" bool HelloWorldScene::init(){ if(!Layer::init()){ return false; } Color3B MyColor[6]={ Color3B(111,201,88), Color3B(1,186,184), Color3B(65,154,210), Color3B(253,96,167), Color3B(230,75,133), Color3B(253,168,0) }; std::string strarray[6]={ "トレーニング", "プロフィール", "お知らせ", "オプション", "ヘルプ", "クレジット" }; Size visibleSize = Director::getInstance()->getVisibleSize(); Vec2 origin = Director::getInstance()->getVisibleOrigin(); for(int i=0;i<6;i++){ auto test = RoundedBoxSprite::create(); test->setParam(Size(350,80),MyColor[i],10,10,strarray[i],Color3B::WHITE,40); test->setPosition(visibleSize.width/2,visibleSize.height-250-i*100); this->addChild(test); } }
コードはここ。
RoundedBoxSprite.cpp
RoundedBoxSprite.h
CODE THANKS FESTIVAL 2014 A日程に参加してきました
CODE THANKS FESTIVAL 2014 A日程に参加してきました.
※fc2blogから移転しました.
CODE FESTIVAL本戦には予選落ちで参加できなかった.予選落ち救済コンテストみたいな感じ。
1回生で予選通った人たくさんいて悲しいなあ(解いてないから当たり前)とか思いながら,企業の金で東京に行った.企業の金サイコー.
https://twitter.com/lp6m/status/541114174504730624
前日15時に品川についた.ホテルにチェックインしたあと東京の友達が10時まで用事があるみたいだからぼっちで回ってた.
21時からのABCにマクドで参加した.
次の日までしか持たないお菓子を買ってしまったので仕方なく友達と二人で食べた.
https://twitter.com/lp6m/status/541250395670974464
朝8時くらいに起きてだらだらした.
お弁当とTシャツが配られた.企業のお金ってすごい.
コンテスト結果:
515点/800 22位/78.
実は開始3分は1位だった.Eまで解いたときに6位〜とか言ってた.
@lp6m プロ
— そすうぽよ (@_primenumber) 2014, 12月 7
F問題が全く方針たたなかったのでH問題の部分点15点を取った.
https://twitter.com/lp6m/status/541445710378311681
なんでみんな通してるんだ?とか思いながらF問題う〜〜っていってよくわからないコードをかいていた.
20分くらいして,あぁ二つ目の要素が1になってるやつの一つ目の要素の人たちほげほげとか気づいた.
A:計算
B:問題文の意味がよくわからなかったので先Cをといた.next_permutationは使わなかった.
int n; int data[3]; int search(int a,int b,int c){ int ima = 0; int rst = 0; while(ima<n){ if(rst%3==0) ima+=data[a]; if(rst%3==1) ima+=data[b]; if(rst%3==2) ima+=data[c]; rst++; } return rst; } int main(){ cin >> n >> data[0] >> data[1] >> data[2]; int ans = inf; ans = min(search(0,1,2),ans); ans = min(search(0,2,1),ans); ans = min(search(1,0,2),ans); ans = min(search(1,2,0),ans); ans = min(search(2,0,1),ans); ans = min(search(2,1,0),ans); cout << ans << endl; return 0; }
C:計算
D:うまいやり方ありそう・・とか思ったけど場合分けなんて数個しかないやと思って丁寧に書いた.
int n,q; int main(){ cin >> n >> q; REP(i,q){ int a,b,s,t; cin >> a >> b >> s >> t; if(b<=s||t<=a){ cout << (t-s)*100 << endl; continue; } if(a<=s&&t<=b){ cout << 0 << endl; continue; } if(s<=a&&b<=t){ cout << ((a-s)+(t-b))*100 << endl; continue; } if(a<=s&&b<=t){ cout << (t-b)*100 << endl; continue; } if(s<=a&&t<=b){ cout << (a-s)*100 << endl; continue; } } return 0;
E:とりあえず全部ためして書いて提出してからTLEしそうって気づいて書き直した.
TLEするコード:
int r,c,m,n; int ban[100][100]; int funcc[4][5000]; int countsouth(){ int rst = 0; REP(i,r){ REP(j,c){ if(ban[i][j]%4==0) rst++; } } return rst; } void move(int ra,int rb,int ca,int cb){ FOR(i,ra-1,rb){ FOR(j,ca-1,cb){ ban[i][j]++; } } } bool search(int tejun){ REP(i,n){ if(i!=tejun){ move(funcc[0][i],funcc[1][i],funcc[2][i],funcc[3][i]); } } if(countsouth()==m) return true; else return false; } int main(){ cin >> r >> c >> m; cin >> n; REP(i,100) REP(j,100) ban[i][j] = 0;o REP(i,n){ REP(j,4){ cin >> funcc[j][i]; } } REP(i,n){ REP(i,100) REP(j,100) ban[i][j] = 0; if(search(i)) cout << i+1 << endl; } return 0; }
書き直したコード
int r,c,m,n; int ban[100][100]; int funcc[4][5000]; int kekka[100][100]; int countsouth(){ int rst = 0; REP(i,r){ REP(j,c){ if(ban[i][j]%4==0) rst++; } } return rst; } void move(int ra,int rb,int ca,int cb){ FOR(i,ra-1,rb){ FOR(j,ca-1,cb){ ban[i][j]++; } } } void movekekka(int ra,int rb,int ca,int cb){ FOR(i,ra-1,rb){ FOR(j,ca-1,cb){ kekka[i][j]++; } } } void unmove(int ra,int rb,int ca,int cb){ FOR(i,ra-1,rb){ FOR(j,ca-1,cb){ ban[i][j]--; } } } bool search(int tejun){ REP(i,100)REP(j,100) ban[i][j] = kekka[i][j]; unmove(funcc[0][tejun],funcc[1][tejun],funcc[2][tejun],funcc[3][tejun]); if(countsouth()==m) return true; else return false; } int main(){ cin >> r >> c >> m; cin >> n; REP(i,n){ REP(j,4){ cin >> funcc[j][i]; } } REP(i,100) REP(j,100) ban[i][j] = 0; REP(i,100) REP(j,100) kekka[i][j] = 0; REP(i,n) movekekka(funcc[0][i],funcc[1][i],funcc[2][i],funcc[3][i]); REP(i,n){ REP(i,100) REP(j,100) ban[i][j] = 0; if(search(i)) cout << i+1 << endl; } return 0; }
F:25回提出した.WA.
懇親会では,色々と話をしていた.本戦じゃないからか、アルハラはなかった.
帰りのゆりかもめからみえる景色が綺麗だった.結局今回も用事だけ済ませて急いで帰ることになった.ゆっくり旅行したい.
今回のコンテスト、優しめの問題設定で「解いてる」っていう実感があって楽しかった.
来年は普通に予選突破できるレベルまで上げたい.なんだかんだで下がってたプロコンのモチベがあがった.
アプリ開発やらバイトの物理シュミレーションのプログラムやらもあるけどやっぱりプロコンの勉強も少しずつ進める.
ちょくだいさんとのツーショットがとれて幸せだった.笑顔が思いっきりにぱーってしてて素敵でした.
https://twitter.com/lp6m/status/541473872017514496
CODE THANKS FESTIVAL,本当に楽しかったです.スタッフの方々,ありがとうございました!!