問題 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+…

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

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

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

問題 Princess's Marriage 解法 距離と期待値を期待値の降順でソートしてどれだけ護衛を雇えるか計算する 心臓に悪いコード int N, M; bool cmp(const pi &a, const pi &b){ return a.S > b.S; } int main(){ int D, P; while(scanf("%d%d", &N, &M) && N+M)…

問題 Amazing Mazes 解法 寝落ちして、１時ぐらいに解いた。一発AC。 BFSで解けます。下か上に行く時はin[y*2±1][x]が1なら進めない。左右はin[y*2][x]が1なら進めないってやっていく。 コード int w, h, maze[128][128], dy[] = {0,-1,0,1}, dx[] = {-1,0,1…

問題 Twirling Robot 解法 BFSで解けます。priority_queue使ってコストの低いとこから見ていって、goalについたら答えです。 コード int w, h; int s[32][32], dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, c[4], used[32][32][4]; int main(){ while(scanf("%d%d…

問題 A Long Ride on a Railway 解法 路線図が与えられる。最長経路の長さとそのパスを表示する。グラフの最長パスを計算するのですが、駅の数が10以下なので全探索でいける。 コード int cost[10][10], ns, nl, res, vres[100], pres; int dfs(int sum, int…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1077)[The Great Summer Contest] 解法 ここの説明が分かりやすいのでどうぞ(https://eagletmt.github.io/contests/blog/aoj-1077/)[プログラミングコンテストの記録] コード cpp ll Math, …

問題 Cleaning Robot 解法 dpでやった、dp[i][y][x] := iターン目に(y,x)につく確率。 漸化式は dp[i+1][次のy座標][次のx座標] += dp[i][今のy座標][今のx座標] * 0.25 if(進めるなら) dp[i+1][今のy座標][今のx座標] += dp[i][今のy座標][今のx座標] * 0.2…

問題 KND is So Sexy。 解法 シュミレーション問題です。 ヘロンの公式っての使った。あとは三角形の周長が同じ場合は正三角形が一番大きくって一辺が固定されているなら２等辺三角形が極大。知りませんでした。 コード int main(){ double a, l, x; while(~…

問題 Fibonacci Sets f(i) = f(i-1) + f(i-2) フィボナッチ数です。で、1001で割って。 i...Vのノードがあって、iとjが | F(i) - F(j) | < d ならiとjは同じ集団に属している。 集団の数はいくつか 解法 Union_Find木を使うと解けます。 蟻本の出番。 コード…

問題 たくさんのなんかコロニーみたいなのがあって、全部のコロニーに行ったり来たりできるようにしたい。 各コロニーのx,y,z座標と半径rが与えられるのでコロニー間に設置する道の最短総距離を求める。 解法 似たような座標から距離求めて最短経路を求める…

問題 Eleven Puzzle。 解法 BFSだと間に合わない。地球は爆発しないよね。 id:nanikakaさんのはてなダイアリーで両側探索というものがあるのを知った、 実装はJavaだったので見ずに勘で実装してみた。 一発AC。 嬉しかったです。 コード vi p, next, now; ve…

問題 Bowling。 解法 シュミレーションの問題でいいんだよね。 ストライクとスペアに関するフラグを立てて、 ２倍足す(f--); 1と一緒 ３倍足す(f=1); って処理してく。10フレーム目はめんどくさい。 実装量が多いというか、きれいなコードにならなかった。 …

問題 Grid。 解法 縦横斜めで走査していって1の数をカウントする 斜めに走査するループの回し方が自分で書いたのにどうなってるのかよくわからない コード int n; char grid[256][256]; int solve(){ int res = 0, c; rep(i, n){ c = 0; rep(j, n){ if(grid[…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119)。 解法 なんか論理の問題かな、推論とかするのかなと思っていたら、 (きこえますか...あなたの脳内に...直接語りかけています...トロピカル...いえ...トポロジカルソートを使うのです…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157) 解法 DPで解きます。ソートした後最長増加部分列を求めます。 コード int n, m; vector<pi>s; int dp[1024]; int main(){ while(scanf("%d", &n) && n){ s.clear(); int h, r; rep(i, n){</pi>…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153)。 解法 BFSで解く。今まで通った場所を記憶するのにmapを使うとメモリが足りなくなる。 コード int W, H, used[52][52][52][52]; int dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0}; char le…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026) N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。 解法 DFSで解く。普通に解いても無理だった。逆から解くとできるんだって コー…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218) 図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか 解法 BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるか…

問題 AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ 解法 DFSで解きます。 コード int board[4][4]; int dy[4], dx[4]; int dfs(int n){ if(n >= 8) return 1; int res = 0; int y, x; rep…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169) 解法 DFSが楽。あとは1以外を全部足してから1をどうするかってやる。 コード DFS int a[512], p; int dfs(int n, int c){ if(n > 21) return 0; if(c == p) return n; if(a[c] == 1) …

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1210) top、north、westはそれぞれ1,2,3とする さいころを指示通りに転がした時、topに来る面は何か？ 解法 シュミレーション問題です。 コード int n, top, west, north; string op; int m…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0199。 解法 シュミレーション問題です。 Cの座る条件をいくつか見逃していてWA連発。 『How to Solve It』に問題を理解することって書いてあったのに。 ちゃんと問題を読むようにします コ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0178。 解法 シュミレーション問題です。 指示通りに処理すればできる高さは十分にとっておかないとRUNTIME ERROR吐かれる コード int t[UNDER+10][5], n; int count(){ int res = 0; rep(i,…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1117。 所々、虫食いになってる表が与えられるからそれを埋める。 解法 一カ所だけ?の行(列)なら埋められる。 コード int p, s; char row[10]; int a[128][128], b[128][128]; int main(){ b…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。 ２つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか？ 重りはより少なく、軽いものを選ぶ。 解法 aの数、xがでれば、yは一つに定まる。xに関するループを回…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165。 解法 p-m以上p+m以下の素数数えていく。素数を用意する配列にはa[i]、i以下の素数の数を累積和で記録しておかないとTLEになる コード int p[MAX_P], n, sum[MAX_P]; int main(){ p[0]…