夏休み期間を使って作ります。部活や競プロもあるので期限は2週間でほぼ完成まで持っていきます 今回はそのためのリソースを探してきました。 slideshareやgithubなどは除きました。OpenGL ESのものを中心にしてあります。API Demo にもOpenGL ESを使ったデ…

八月のタスクです。 AOJ Volume 5 のJOIの過去問を解いてく PKUの問題とく 夏季セミ精進 蟻本読むよー 英語 競技会 Android開発とOpenGLES (http://raven38.hatenablog.com/entry/2014/07/31/225717) 早寝早起き 他にもやらなきゃならんことある気がするけど…

一日目(７月26日) 前泊する予定なので、出発。電車に揺られて、2,3時間。上野についた。湯島天神に城西国際大学と応用情報の御礼参りと競技会の必勝祈願、団体で10位以内と個人入賞、女子部員の入部、をお祈りしてきました。 湯島から歩いて、麺屋武蔵 武骨…

問題 Knapsack Problem 解法 DPです。蟻本に詳しい説明が載ってます。何個でも使えるとかいうって問題使い回しすぎな気も。 心臓に悪いコード int dp[MAX_N+1][MAX_W+1]; int N, W, v[MAX_N], w[MAX_N]; int main(){ scanf("%d%d", &N, &W); rep(i, N) scanf…

問題 0-1 Knapsack Problem 解法 dp[i][j] := i番目までの荷物でjまでの重さを入れた時に価値の最大値 漸化式 dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) (j >= w[i]) DPで解きます。典型問題。問題の下に解説があるので参照。 int dp[MAX_N+1][MA…

問題 Coin Changing Problem 解法 DPのプラクティスのセットのところの問題ですので当然DP。普通にDPを組むと何枚でも使用できるってのkを使用枚数の上限としてO(nmk)ってなるので間に合わない。たぶん正答率が低いのはこれでTLEが出てるからかと。 dp[i+1][…

(http://shinyorke.hatenablog.com/entry/2014/07/20/231609)の記事を読んで、本読みたいなと思う今日このごろ。 知り合いにエンジニアなんかいませんよ。オンサイトは参加しませんし、誰か教えてほしいものです。 本棚見せてください。 4冊しかない。シグナ…

問題 D's Ambition 解法 8文字ずつ読んで"AIDUNYAN"のアナグラムだったら"AIZUNYAN"に置き換える。 実装するだけ、バグを埋めないようにすればいい。アナグラムの判定はアルファベットごとに数えたり、"AIDUNYAN"のアナグラムを先に生成するとか 心臓に悪い…

問題 Addition Game 解法 加法の交換則でどの順番で足しても結果は同じことが分かる 心臓に悪いコード int n; string s; int solve(){ int i = 0; while(s.size() > 1){ char c[4]; sprintf(c, "%d", s[0]+s[1]-2*'0'); s.erase(0, 2); s.insert(0, c); i++;…

問題 Tatami 1:2の大きさの畳をH,Wの大きさの部屋に敷き詰める方法は何通りあるか。 畳の敷き詰め方のルールに乗っ取って敷き詰めて行きます。 解法 畳を敷き詰めるルールは日本人なら誰でも分かるので説明の必要はありませんね。DFSで全探索すれば解けます…

問題 Calling Extraterrestrial Intelligence Again m, a, bが与えられる。 p*q <= m a/b <= p/q <= 1 の制約下でp*qが最大となるp,qを答える。 解法 愚直に全探索、実装したらTLE連発した。(http://d.hatena.ne.jp/k_operafan/20110715/1310695379)のシェル…

問題 Lagrange's Four-Square Theorem 四平方定理っていうのがある。全ての自然数は高々4個の平方数の和で表すことができる。nが与えられる。高々4個の平方数の和がnになる組み合わせの数を答える。 解法 全探索とdpで解けます。両方で解こうと思います 心臓…

問題 Lagrange's Four-Square Theorem 四平方定理っていうのがある。全ての自然数は高々4個の平方数の和で表すことができる。nが与えられる。高々4個の平方数の和がnになる組み合わせの数を答える。 解法 全探索とdpで解けます。両方で解こうと思います 心臓…

問題 Grey Area 問題文の意味がまったく分からなかったのでいろんな方のブログを見てなんとか理解した。 vの数字をwで割ったやつをカウントしていって0から順番にどれぐらい色が必要か見ていく。 問題文さえ読めればなんとかなる 解法 実装するだけ。問題文…

問題 Watchin' TVA 解法 実装するだけ。虫が入らないように丁寧に書くことが必要。 心臓に悪いコード int N; int tominutes(int w, int s){ int h = s/100; int m = s%100; if(h >= 24){ h -= 24; w++; } return h*60+m+w*60*24; } int main(){ while(scanf(…

問題 Ghost Buster 解法 BFSで解ける。リンレンの双子の問題はバグ埋め込んでなかなかACでなかったけど、今回は一発AC。全探索の実装なれてきたのかな 心臓に悪いコード int dy[] = {0, -1,0,1,0}, dx[] = {0, 0,-1,0,1}; int gdy[] = {0, 0, 1, 0, 0, 0, 0,…

問題 Monster Factory 解法 シュミレーションする。真ん中にあるのが下に届いたパッケージでないならpush_right命令を実行する。 心臓に悪いコード int main(){ string top; while(cin >> top, top != "-"){ string left, right, res; cin >> left >> res; c…

問題 Line Puzzle 解法 DFS。左上の起点から順番に走査していく。 心臓に悪いコード int dy[] = {-1,0,1,0}, dx[] = {0,-1,0,1}; int n, used[8][8], p[8][8], res; void dfs(int sum, int y, int x, int rest){ if(res) return; if(sum == 0 && rest == 0){…

問題 Life game 解法 dp。 dp[i][j] := iマス目でお金をjだけ持っている確率 で解く 心臓に悪いコード int main(){ while(scanf("%d%d%d", &X, &Y, &Z) && X+Y+Z){ memset(dp, 0, sizeof(dp)); memset(m, 0, sizeof(m)); rep(i, X) scanf("%d", V+i); rep(i,…

問題 Ninja Climbing 解法 BFSで通った。もしビルの屋上を超えてしまっても屋上につくことはできる 心臓に悪いコード cpp int n, b[2][128]; int rec1(int x, int y){ if(b[x][y+1] == 1) return rec1(x, y+1); return y; } int rec2(int x, int y){ if(b[x]…

国防、安全保障と先端技術開発、そして、教育、人づくり。この三つは予算の都合で減らしてはならないとされている予算らしいです。 国防費は周辺国、そして現在では世界全体のパワーバランスによって決定されるもので、パワーバランスが崩れることは有事、つ…

問題 Input Candidates 解法 入力ができれば楽。fgetsを使ったりgetlineを使ったり。webへアクセスできない状況で出されたら、死ぬ。文字列処理。 心臓に悪いコード int n; char k, s[2048]; bool cmp(const pair<string, int> &a, const pair<string, int> &b){ if(a.S != b.S) return</string,></string,>…

問題 Stray Twins 解法 BFS。入力のところで処理の時とy、x座標を逆にあつかっててwa連発。 心臓に悪いコード int board[51][51], Y, X; int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; pii nextp(pii now, int i, int d){ pii next = now; next.Y += dy[i] * d…

問題 Cards 解法 dpでしょうか。lからrまでを重ねるための最小コストは(l<=i<r)、lからiまでとi+1からrまでのコストにlからiまでの塊とi+1からrまでの塊を重ねるためのコストの最小値。 dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + a[l]b[i]a[i+1]*b[r]) コード int dp[100][100], n, a[100], b[100]; int dfs(int l, int r){ if(l == r) return 0; if(dp[l][r] >= 0) return dp[l][r]; int res…</r)、lからiまでとi+1からrまでのコストにlからiまでの塊とi+1からrまでの塊を重ねるためのコストの最小値。>

問題 Identically Colored Panels Connection 解法 全探索で解けます。O(65)ぐらい 心臓に悪いコード int h, w, c, f[8][8], p[8][8], dy[] = {-1,0,1,0}, dx[] = {0,-1,0,1}; void count(int y, int x){ f[y][x] = 1; rep(d, 4){ int ny = y+dy[d], nx = x+…

問題 Sum of Different Primes 解法 動的計画法の勉強。DPどうやって書くのか、検討つかん。諦めてDFSで書いてみた。引数、３つになる。減らそうと思ったけど減らせない。O(1120以下の素数の数\K\N)で実装できそうだと思ったけど、O(K\N)*の実装考えてた。 …

問題 Multi-clumn List plen行、cnum列のリストを作成して出力する。各列の幅はwidth、列の間には幅cspaceのスペースを作る。 plen行出力した後は'#'を出力して、データセットの出力の最後に'?'を出力する。 サンプルのoutput見ればだいたい分かる。 解法 li…

問題 Cyber Guardian パケットフィルタリングをする問題。n個のruleとm個のパケットが与えられる。ruleの優先順位は後に入力された方が高い。すべてのruleに当てはまらなければ許可されない。通信が許可されるパケットの数とパケットの内容を表示せよ。 解法…

8月に入ったら情報オリンピックの過去問を解いてく予定なので動的計画法が使えないとどうにもならないと思い、勉強します。題材は蟻本の01ナップサック問題から ナップサック問題 重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品…

問題 Dragon Fantasy 解法 全探索＋枝刈り。BFSでときました。枝刈りをするときはループに入らせる前に走査して枝刈りさせないと無駄な探索が入り込んだりすることを知った。 心臓に悪いコード int n; int hx, hy, dx, dy, cx[21], cy[21]; double dist(doub…