AOJ 0550: Dividing Snacks

最初, [5001][5001][2]の配列を使ってメモ化再帰をして, メモリと戦っていましたが, forループのdpにすると, 片方が使いまわせることに気づいてACしました.

「お菓子を分割する」, と考えると中々難しいのですが, n個に区切られたお菓子を２つのグループに分ける, と考えると, グループの変わり目の分割点をコストに含んでいけばいいことが分かります.

i番目までのグループ分けの最適解がわかれば, i + 1番目のグループ分けの最適解もわかるので, 動的計画法の考えを用いることができます.

(メモ化再帰の時のコードを残しておくので, そちらを参考にすると良いかもしれません.)

続きを読む

AOJ 0531: Paint Color

座標圧縮の問題でした.
色々と本質でない所で間違ってしまったので, 以後気を付けたいです...

２次元配列で持っている情報は点であって、中の面積ではないことに気をつけましょう.

再帰的にノードを塗ると, スタックオーバーフローが起きてしまうので, キューorスタックを自前で準備して, BFS or DFS をしましょう.

続きを読む

AOJ 0520 : Lightest Mobile

最軽量のモビール.
紙に書いたことを中々実装できずに苦労しましたが, 実際にやることはそんなにないです.

ある端からある端が再帰的に定義されている⇒二分木に落とせる! ということに気づくと簡単になると思います.

帰りがけ順で二分木を走査しながら, 一番下のノードから最軽量のモビールの構成を求めていきます.

続きを読む

AOJ 0540 : Amidakuji

Expoに心を折られていましたが, 気分転換に別の問題にチャレンジ.
あみだくじの問題で, 一本横棒を抜いて (または棒を抜かずに) 得点を最小化しましょう、というのが問題の趣旨です.

(今は時間が無いので, 後日解説をしたいと思います.)
ソースを見ればだいたい分かると思います (小学生以下の説明)

続きを読む

[未]AOJ 0552: Exposition

ある点からの最遠点を求めるのに、O(N) かかり、全体でO(N^2)時間, グループ間の最遠点対をもとめるのにO(N^2)がかかってしまいます... どうしよう.

後者はO(N)にできますが, 前者がうまくいきません....O(NlogN)くらいに落とせないかなあ. (40%解法だと思っていましたが, 1つめのテストケース以外はWAとTLEだったので10%解法です...はああ.)

続きを読む

AOJ 0507 : Square

本選問題, 残り8問です.
2006-2007 JOIの問題は全部おわりました. わーい.

楽しいようで, 負けたくなくて. そんな事を彷彿されるような名前の問題でした.

シンプルな再帰で書けます. 出力をみると楽しいですネ.

続きを読む

AOJ 0509: Sheets

y座標(x座標)ごとに区切って, 面積と周長を考えてみましょう.(近くに解説の画像を用意します)
O(n^3)くらいですが、色々と枝を刈っているので早いです.

続きを読む

AOJ 0527: Setting Go Stones

本選問題、残り10問

なんで解いてなかったんでしょう...
石の数を圧縮してシミュレーションするとよさそうです. リスト使うともう少し早く出来そうです.

続きを読む

AOJ 0508: String with Rings

"JOIの時間制限なら" 簡単すぎる問題なのですが...
下のコードで色々悪の改善をして通しました... (悪すぎる)

ので、綺麗なコードを載せます. (犯罪の隠蔽) (JOI制限ならぜんっぜん大丈夫です)

続きを読む

AOJ 0548: Reindeer with no sense of direction (再)

12月に挑戦して以来の再挑戦です.

...メモリきびしすぎんよ～＞＜ どうしてもメモリとTime Limitの折り合いがつかなかったので, C++のmapを使うことにしました. (kyuridenamidaさんの方法を参考にしました.)

Cで通していた先輩がいたので, こんど聞いてみよう.

"プレゼントを逆順に置く" というのが肝ですね.

続きを読む