AOJ JOI 2011,2012
予選で4完、本選で3完です。本選はWA連発のすえなんとかACでした。実際にはWAとかでないので一発でACできるように精進
0565 Lunch
パスタの最安値とジュースの最安値を足して50引く
0566 Soccer
勝ち点数えて順位付け
0567 Best Pizza
結構迷った。結局貪欲法で解いた。DPで解き直すつもり
0568 Pasta
飯多い。初めに全探索した。そこから、一昨日と昨日のパスタさえ分かればいいと分かった。んでメモ化再帰。DPでは実装してない。今度する。
0569 Illumination
解いてない。地図に余白を儲け、外側を塗りつぶす。再帰とかBFSとかで、境界線の長さを計る。
0570 Zig-Zag Numbers
意味分からない。典型らしい。桁DPだって。
0571 JJOOII
O(N)に落とすと解ける。実装でミスった。JOIそれぞれの数を数える。
0572 Card Game is Fun
問題読み間違える。Aから適当にすてる。Bからは前と後ろからしか取れない。Bは連番になる。Bのカードを端から見て行って、連続でAに含まれているか調べてく。想定解とか違うのかな。O(AB)。
0573 Night Market
メモ化再帰で解いた。後でDPで解く。解説のPDFが丁寧。 これも典型DPらしい。
0574 Nails
解いてない。累積和もしくは最大値を伝搬する解法で解ける。
累積和の計算は単純なO(数x面積)からO(数+面積)に短縮できる。
最大値の伝搬:一番上の頂点に三角形の大きさを入れる。上からmax(自分, max(左上, 右上) - 1)
0575 Festivals in JOI Kingdom
グラフ大きすぎてまったく分からないので解けてない。Dijkstra、深さ優先探索、二分探索、Union-Find、Lowest Common Ancestorなど。
最後の方まったくわからん、データ構造が素人。DPもです。一発ACできるように実装力と問題を読む国語力をつけます
