Bounder
魂を光のもとに導くゲームです。
クリックとドラッグだけのシンプルで気持ちのよい操作が売りです。たぶん。
Unityでちょちょいと作って
ニコニコ自作ゲーフェス3に出してみました。
ダウンロード先は http://www.freem.ne.jp/win/game/6476 です。
(ふりーむさんに申請中なので、DL先はそのうち変わります)
HSPコンテスト2012(ふるーつぱにっく！)
HSPコンテスト2012が開催されています。
応募締め切りギリギリで提出できました。
ふるーつをいっぱいつなげて、いっぱいたべよう！
でも、こわーいおばけもいるから気を付けてね！
ということで制作上で便利だったHSPネタを紹介します。
モジュール
#module hoge #deffunc local constructor posx = 10 posy = 20 return #deffunc local destructor return #deffunc local draw gsel 0: gcopy 1,posx,posy,32,32 return #global constructor@hoge draw@hoge destructor@hoge
だいたいこんな感じで使いました。
名前空間が圧迫されている時に適応範囲を局所化できるので便利です。
再帰関数
マップ内で果物が何個連結されているかをdfsするときに再帰関数を使いました
object_id = 0 // 対象の果物 dim objects,100,100 // 果物マップ dim visited,100,100 // メモ化的なもの #defcfunc dfs int x,int y if visited(x,y)!=0: return 0 if object_id == objects(x,y): return 1 if x+1<w: visited(x,y) += dfs(x+1,y,object_id) if x-1>=0: visited(x,y) += dfs(x-1,y,object_id) if y+1<h: visited(x,y) += dfs(x,y+1,object_id) if y-1>=0: visited(x,y) += dfs(x,y-1,object_id) return visited(x,y)
こんな感じです。
名前が衝突するとめんどくさいのでvisitedのように引数パラメタごとに変数を用意しておくのがコツです。
入力モジュール
いつもやっている感じで作っちゃいました。
HSPの標準機能でもできるかもしれません。
フレーム内での値が固定化されているのがポイントかも知れません。
//-------------------------------------------------------------------- // // INPUT // //-------------------------------------------------------------------- #module inputs #const LEFT 0 #const UP 1 #const RIGHT 2 #const DOWN 3 #const B1 4 // Z #const B2 5 // X #const ESC 6 #deffunc local init prev_codes = 0 codes = 0 return #deffunc local update prev_codes = codes codes = 0: c=0 getkey c,37: if c: codes += (1<<LEFT) getkey c,38: if c: codes += (1<<UP) getkey c,39: if c: codes += (1<<RIGHT) getkey c,40: if c: codes += (1<<DOWN) getkey c,90: if c: codes += (1<<B1) getkey c,88: if c: codes += (1<<B2) getkey c,27: if c: codes += (1<<ESC) return #defcfunc local pushed int code if ((prev_codes>>code)&1)=0: if ((codes>>code)&1)==1: return 1 return 0 #defcfunc local pushing int code if ((prev_codes>>code)&1)=1: if ((codes>>code)&1)==1: return 1 return 0 #defcfunc local released int code if ((prev_codes>>code)&1)=1: if ((codes>>code)&1)==0: return 1 return 0 #global
浮動少数変数に注意
変数は動的に色んな型に変わる可能性があります。
pos=10.0
とかやっていてもいつのまにか
#const NEXT_POS 50 ... pos=NEXT_POS
とかやってしまって整数型になってしまうことがあります。
根気よくpos=double(NEXT_POS)とかやるといいと思います。（それかsetter命令を作ってラップするか)
その他
buffer -> picload "hogehoge",1 -> gcopy
redraw 0 -> メインループ -> await 1 -> redraw 1
if scene != prev_scene: gosub *change_scene
scene=prev_scene
今年もHSPコンテストは盛り上がっている模様。
みなさんも一度はチェックしてみたらいかがですか？
ICPC2012 国内予選直前対策会議まとめ
国内予選まで一週間きってやばいですけど、みんなでペアプロしようよの会です。
「ガチ勢の奴らから力ずくでスキルを盗み取る」ことがテーマ
LTの部 : 1時間(1枠10分程度)
ペアプロの部 : 2時間(当日集まったメンバーで2人,3人でグループになって練習)
交流の部 : 30分~1時間(気になる人に思いを告げるチャンスです！)
AtCoderの部 : 1時間半(時間が被ったと思ったけど、オフをやっちゃえばいいじゃない)
場所はチームラボのオフィスを貸していただきました。感謝！
LTの部
- mitsuchie「国内予選の傾向と対策」
- tomerun「細かなコーディングテクニック」
- hama_du「二分探索」
- tayama0324「幾何の話」(資料が見つかりませんでした)
ペアプロの部
オリジナル問題の「TUATなのかTATなのか」を解いた順に3人組を作りました。
グループ内で自由に問題選んで取り組む形です。
交流の部
AtCoderに向けて何やら画策している人たちが・・・？
AtCoderの部
AtCoder Regular Contest #005にみんなで挑戦しました。
4完している人もたくさんいて怖かったです。
え、私ですか？D間に合いませんでした、3完です(TAT)
ICPC2012 国内予選直前対策会議 TUATなのかTATなのか
ICPC国内予選直前対策会議(http://atnd.org/events/30281)にて、ペアプログラミングのグループ分けに利用した問題です。
簡単な問題ですが、問題文をちょっとわかりにくくしています。
(サンプルを弄るとすぐわかると思います)
問題 TUATかTATなのか
東京農工大学という大学があるらしい、そこではTUATやTATといった略称を用いるそうだ。
そこで我々は、TUATとTATどちらが頻繁に用いられているか調査しようと思う。
a-zA-Zで構成されるn個の文字列が与えられて、その中にTUATおよびTATがそれぞれ何個含まれているか調査する。
ただし、同じ略称が繋がっている場合は何か深い意味があるとして繋がった回数だけ重みを回数の2乗に増やそうと思う。
たとえば、TATATならば5回、TATATATならば14回現れたこととするが、TATTATは繋がっていないとして2回現れたとする。
また、0<=n<1000かつ1つの文字列の長さは1以上10000以下として，大文字小文字は区別しない．
| input | output |
|---|---|
n S1 S2 … Sn ただし、n=0の時終了 | S1のTUATの数 S1のTATの数 S2のTUATの数 S2のTATの数 … … … … SnのTUATの数 SnのTATの数 |
| sample input | sample output |
|---|---|
5 tuatTUATtat tatatat tuatATat tuaatHaaatat hatuatuat 0 | 2 1 0 14 1 5 0 1 5 0 |
解法
色々な解法があると思いますが、無駄に配列を使った解を紹介します。
#include <iostream> #include <string> #include <cstring> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(n) REP(i,n) typedef long long int ll; const int MAXN=10012; int tuat[MAXN],tat[MAXN]; int main() { int n; while(cin>>n&&n) REP(k,n) { memset(tuat,0,sizeof(tuat)); memset(tat,0,sizeof(tat)); string s; cin>>s; rep(s.size()) s[i]=tolower(s[i]); ll ans1=0,ans2=0; rep(s.size()-2) if(s[i]=='t'&&s[i+1]=='a'&&s[i+2]=='t') { tat[i+2]=tat[i]+1; ans1 += ll(tat[i+2])*ll(tat[i+2]); } rep(s.size()-3) if(s[i]=='t'&&s[i+1]=='u'&&s[i+2]=='a'&&s[i+3]=='t') { tuat[i+2]=tuat[i]+1; ans2 += ll(tuat[i+2])*ll(tuat[i+2]); } cout<<ans2<<" "<<ans1<<endl; } return 0; }
本当はもっとDP的な問題にしたかったんですけどねえ
ICPC2012 新入生教育編おまけ1 おせんべい
前回は全探索の問題をやったので、今回は主にforループの組み合わせで数え上げる感じの応用問題です。
問題はAOJの0525: Osenbeiをやります。
0525: Osenbei
行単位、列単位でおせんべいをひっくり返して表面を最大にしよう そんでもって最大値を答えてね、という問題
テクニックとか気をつけること
- 全探索でいける？オーダーはどのくらい？
- for(int i=(1<
- if((i>>n)&1)でnビット目に1が立っているか確認できるよ
- RC表記がわかりにくかったらxywhで表現するといいよ
- ひっくり返したらもとに戻す
ちょっと難しいかなと思うのはビットで状態を表現するところかな。
巡回セールスマンでビットDPするときとかに使うので慣れておくといいですね。
全探索する解答
#include <iostream> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(n) REP(i,n) const int MAXH=12; const int MAXW=10002; bool U[MAXH][MAXW]; // おせんべいの状態 int W,H; int main() { while(cin>>H>>W&&(H|W)) { REP(y,H) REP(x,W) cin>>U[y][x]; int ans=0; for(int i=(1<<H)-1;i>=0;i--) // 縦状態のループ { REP(y,H) if((i>>y)&1) REP(x,W) U[y][x]=!U[y][x]; // 反転する int res=0; REP(x,W) // ひっくり返す前の表面とひっくり返した時の表面(裏面)の確認 { int v=0; REP(y,H) v+=U[y][x]?1:0; res += max(v,H-v); } ans=max(ans,res); REP(y,H) if((i>>y)&1) REP(x,W) U[y][x]=!U[y][x]; // もとに戻す } cout<<ans<<endl; } return 0; }
ICPC2012 新入生教育編2 全探索
本日は新入生に向けて探索のテクニックを伝授した。以下は、その練習問題と解説を記す。
(ここ教えたほうがいいとかフィードバックあったらコメントにお願いします)
部分和探索
24個の正の整数の並び中で連続した5つを取り出した時、最大値を求めなさい (なお、末尾と先頭は連続しているとする) input n a000 a001 a002 ... a023 a100 a101 a102 ... a123 ... an00 an01 an02 ... an23 0 < axxx < 1000000 0 < n < 1000000 output a0max a1max ... anmax sample input 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 sample output 56
単純に24回ループの中に5回ループを持たせるだけでよい。
ただし、タイプミスや不慮の事故を減らすために定数化はしておくべきである。
新入生に求める解放
#include <iostream> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(n) REP(i,n) const int MAXN=24; // 数字の配列の最大長 const int LEN=5; // 連続する数 int a[MAXN]; int main() { int n; cin>>n; REP(x,n) { rep(MAXN) cin>>a[i]; // 配列に確保しておく int ans=0; REP(i,MAXN) { int v=0; REP(t,LEN) v+=a[(i+t)%MAXN]; //剰余を使って末尾のループに対応する ans=max(ans,v); // 最大値を確保する } cout<<ans<<endl; } return 0; }
もうちょっとまともな回答
#include <iostream> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(n) REP(i,n) const int MAXN=24; const int LEN=5; int a[MAXN]; int main() { int n; cin>>n; REP(x,n) { rep(MAXN) cin>>a[i]; int v=0; rep(LEN){ v+=a[i];} int ans=v; // 初期値 rep(MAXN) { v += a[(i+LEN)%MAXN]-a[i]; ans = max(ans,v); } cout<<ans<<endl; } return 0; }
IO回りなど基本的なところは変わっていませんが、連続した部分和をどう算出するかが異なっています。
int v;を用いて前回の値を利用しています。
例えば、a[0]+a[1]+a[2]+a[3]+a[4]の次の値はa[1]+a[2]+a[3]+a[4]+a[5]です。
つまり、a[0]とa[5]に注目すればよいのです。
今回は5つの連続した値でしたが1000000つの連続した値といったようにオーダーが大きくなったときに対応できるかどうかが肝になってきます。
面積と長さの算出
2次元平面にn個の長方形を貼り付けることを考える。 長方形の左上座標と幅と長さが与えられた時、その面積と辺の長さを出力しなさい。 input n x1 y1 w1 h1 x2 y2 w2 h2 1 <= n < 100 0 <= x,y,w,h < 1000 output a b sample input 2 1 2 3 4 2 5 6 2 sample output 22 24
与えられた長方形を2次元配列にマッピングしていきましょう。
そしてらforループで2次元配列を見ていくだけでよいですね。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(n) REP(i,n) const int MAXN=2048; bool U[MAXN][MAXN]; int main() { int n; while(cin>>n) { memset(U,0,sizeof(U)); int xx,yy,ww,hh; rep(n) { cin>>xx>>yy>>ww>>hh; xx++; yy++; // 0-index => 1-index REP(y,hh) REP(x,ww) U[y+yy][x+xx]=true; } int ans1=0,ans2=0; REP(y,MAXN) REP(x,MAXN) { if(U[y][x]) ans1++; else continue; // 長方形の内部以外は戻す if(!U[y-1][x]) ans2++; // 端っこ判定 if(!U[y+1][x]) ans2++; // 端っこ判定 if(!U[y][x-1]) ans2++; // 端っこ判定 if(!U[y][x+1]) ans2++; // 端っこ判定 } cout<<ans1<<" "<<ans2<<endl; } return 0; }
ICPC2012まとめ(参加までの軌跡)
東京農工大学から出場予定(チームの一員であり、全体のまとめ役でもあるので来年のためにも)
去年は成績が振るわなかったので今年こそは勝ちを狙いに行く
micchan, rm saturday, dogezaの3チームが出場予定。(私はmicchanに所属)
- 4月中はAOJの使い方や蟻本の購入や環境セッティングに当てた
- 2012年度 第一回部内大会 5/2
- ICPC2012 新入生教育編1 ループと配列と 05/08
- ICPC2012 新入生教育編2 全探索 05/15
- ICPC2012 新入生教育編おまけ1 おせんべい 05/22
- ICPC向けペアプログラミング練習会in三鷹 05/27
- 2012年度 第二回部内大会 05/29
- 部内大会反省会 06/04
- 2012年度 第三回部内大会 06/11 & チーム確定
- TopCoderMeetingUp 6/12
- ICPC2012 練習会編1 DFSとBFS 06/15
- ICPC2012 練習会編1 ダイクストラ法とプリム法 06/15
- ICPC2012 練習会編1 数値積分 06/15
- OBOG会国内模擬予選(3完でした残念)
- ICPC2012 練習会編2 DPとメモ化再帰 6/22
- ICPC2012 練習会編2 最大流と最小費用流 6/22
- ICPC2012 練習会編2 強連結成分分解とSAT 6/22
- ICPC2012 練習会編3 オリジナル文字列問題集 6/29
- ICPC2012 国内予選直前対策会議 6/30
- ICPC2012 国内予選直前対策会議 TUATなのかTATなのか 6/30
- KUPC東京オンサイト 7/1
その他SRM,ACRなど各種オンラインコンテストに参加
結果:3完 総合44位 国内予選敗退
