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

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できるように実装力と問題を読む国語力をつけます