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

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

昨日、ひぐらしを見終わったのでなんとか7月になりました。西暦では7月2日らしいですが、そんなことは知ったこっちゃありません。 7月に入ったので今月やっとかなきゃならんことでも列挙しときます。 DPの勉強(8月に情報オリンピックの問題解くために) AOJ/P…

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