AOJ

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

ToDO List in September

PCK予選 PCKの過去問解く 蟻本 集合知プログラミング 英語 OpenGLES 早寝早起き

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…