読者です 読者をやめる 読者になる 読者になる

AOJ 0281 Formation

問題 Formation 解く 最初簡単だろうと思って、貪欲法で解いたら、WA。 DPで解こうとするとMLEになる。 適当な人数になるまではCANにしとけばいいことに気づく。 cとaが小さくなるまでCANに割り振って、そこからDP,runtime error 数分悩む。1000 1000 3とか…

AOJ 0212 Highway Express Bus

問題 Highway Express Bus 解法 拡張ダイクストラ法。初めて解いた。拡張グラフのダイクストラとかなんとか、 グラフを3次元方向に掘ってく 心臓に悪いコード typedef pair<int, int> pi; // 残りの割引券 現在の街 typedef pair<int, pi>P; // コスト pi struct edge{ int to,</int,></int,>…

AOJ 0551 Icicles

問題 日本語なので説明はありません Icicles 解法 これもDPって言うらしいです。誰かがDPだって言ってました。知りません。 つららが両端のつららよりも長ければ解け始めるってことからそのつららの長さに影響するのは両端だけ、つまり各つららに対して両端…

AOJ JOI 2013,2014

予選4完、本選2完です。たしか本選Aランクが220点以上だったと思います。 0592 Average Score やるだけ。下を40にそろえて平均を出す。 0593 Vote 面白い競技の順に走査してく 0594 Super Metropolis 幅優先探索で解こうとしたけど、無理。普通に計算で解け…

AOJ JOI 2012,2013

本選の問題がAOJで見つからないです。4完。 0576 Homework Lから国語と算数の両方の宿題が終わるのにかかる日数を引く 0577 Unique number それぞれの数字をカウントしとく。制約読み間違えてWAだした。 0578 Signboard 新しい看板の一文字目と二文字目を探…

AOJ JOI 2011,2012

予選で4完、本選で3完です。本選はWA連発のすえなんとかACでした。実際にはWAとかでないので一発でACできるように精進 0565 Lunch パスタの最安値とジュースの最安値を足して50引く 0566 Soccer 勝ち点数えて順位付け 0567 Best Pizza 結構迷った。結局貪欲…

AOJ JOI 2010

昨日今日、二日間でやりました。予選5問本選2問、本選2問目はヒント見てやったので、実質1問。 0554 Total Time 分と秒に直す。 0555 Ring 文字列探索 0556 Tile 斜めに割った部分のどの部分にあたるか調べ、そとがわから何個目から調べる 0557 A First Grad…

AOJ JOI 2009

予選4完、本選1完です。本選のAランクが36点ですので後1問取りたかった。 0543 Receipt 合計から9冊分の価格を引く。 0544 Sugoroku シュミレーションする。 0545 Party 数えるだけ。最初、友達の友達ってどこまでも行くと思ってグラフ書いてた。 0546 Lin…

AOJ JOI 2008

今日は予選4問、本選1問解けました。予選はなんとか通れそうですが本選がやっぱりたいへんです。 部分点は解ける感じなんですけど満点解法がやっぱり難しい 0532 Time Card 秒に合わせて計算する。 0533 Contest ソートすると楽になれる 0534 Chain 実装ミス…

AOJ JOI 2007

予選は全完だったのに、本選はsubmitすらしてない。頭が回らない。明日は朝のうちに予選も本選もやろうと思う。 0521 Change 500円玉から数えてく。 0522 JOI and IOI やるだけ 0523 Card Game 実装に迷った。 0524 Searching Constellation 0518のThe Oldes…

AOJ JOI 2006

一日ぶりです。昨日は仲間の家に泊まってたので、問題は説いてないです。 0510 Score やるだけ。4つの合計だして比較。 0511 Who Are The Student Yet To Submit やるだけ。提出した人のフラグを立てて、フラグの立ってない二人を出力とか。 0512 Caesar Cip…

AOJ JOI 2005

今日はJOI 2005の問題 7/10解きました。 0500 Card Game やるだけ。3つに分岐してそれぞれ処理させる。 0501 Data Conversion やるだけ。二次元配列なんかで変換用の表を作っておく。mapを使ったりすると便利。 0502 Dice 実装ゲーっていうのかな。今回、ダ…

AOJ DPL_1 C Combinatorial Knapsack Problem

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

AOJ DPL_1 A Combinatiorial 0-1 Knapsack Problem

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

AOJ DPL_1 A Combinatiorial Coin Changing Problem

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

AOJ 2575 D's Ambition

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

AOJ 2189 Addition Game

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

AOJ 2163 Tatami

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

AOJ 1232 Calling Extraterrestrial Intelligence Again

問題 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)のシェル…

AOJ 1241 Lagrange's Four-Square Theorem

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

AOJ 1285 Grey Area

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

AOJ 1063 Watchin' TVA

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

AOJ 1046 Ghost Buster!

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

AOJ 1036 Monster Factory

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

AOJ 1034 Line Puzzle

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

AOJ 0232 Life game

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

AOJ 0230 Ninja Climbing

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

AOJ 0242 Input Candidates

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

AOJ 0223 Stray Twins

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

AOJ 0145 Cards

問題 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までの塊を重ねるためのコストの最小値。>

AOJ 1174 Identically Colored Panels Connection

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

PKU 3132 Sum of Different Primes

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

AOJ 1115 Multi-column List

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

AOJ 1111 Cyber Guardian

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

AOJ 2008 Dragon Fantasy

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

AOJ 2019 Princess's Marriage

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

AOJ 1166 Amazing Mazes

問題 Amazing Mazes 解法 寝落ちして、1時ぐらいに解いた。一発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…

AOJ 1156 Twirling Robot

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

AOJ 1108

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

AOJ 1077 The Great Summer Contest

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

AOJ 1020 Cleaning Robot

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

AOJ 1091 KND is So Sexy

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

AOJ 1016 Fibonacci Sets

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

AOJ 1127 Building a Space Station

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

PKU 1007 DNA Sorting

問題 DNA Sorting 解法 ソートするだけの問題。 逆順になっている要素を数える。 コード int n, m; char c[64]; bool cmp(const string &a, const string &b){ int ac = 0, bc = 0; rep(i, a.size()){ REP(j, i, a.size()){ if(a[i] > a[j]) ac++; if(b[i] >…

AOJ 0190 Eleven Puzzle

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

AOJ 0152 Bowling

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

PKU 1005 I Think I Need a Houseboat

問題 (http://poj.org/problem?id=1005)。翻訳されてます。 解法 (0,0)から家までの距離を求めて、円の半径がそれを超えたら浸食される。 コード double x, y, d; int N; int main(){ scanf("%d", &N); rep(i, N){ scanf("%lf%lf", &x, &y); d = sqrt(x*x+y*…

PKU 1002 487-3279

問題 (http://wikiwiki.jp/pku/?1002%20487-3279)。 解法 map使うと簡単、入力を全部数えていって、複数あるやつだけ表示させる。 cin使うとTLEになった コード int n; vector<string>s; char in[100]; int main(){ map<char, int>m; m['A'] = m['B'] = m['C'] = '2'; m['D'] = </char,></string>…

AOJ 0151 Grid

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