AOJ JOI 2009

予選4完、本選1完です。本選のAランクが36点ですので後１問取りたかった。

0543 Receipt

合計から９冊分の価格を引く。

0544 Sugoroku

シュミレーションする。

0545 Party

数えるだけ。最初、友達の友達ってどこまでも行くと思ってグラフ書いてた。

0546 Lining up the cards

順列つくって数えてく。10P4で5040かな、たぶん楽勝。

0547 Commute routes

not solved. DPでいいのかな。次の交差点で曲がれるか曲がれないかで分けて考えてく。

0548 Reindeer with no sense of direction

not solved. 碁石拾いに制限を加えた感じの、既に拾ったプレゼントの組み合わせと最後にプレゼントを拾った家の組み合わせを状態として各々について考える。後ろからDPとか

0549 A Traveler

累積和を使う。

0550 Dividing Snacks

not solved. DPらしいです。dp[i][j][k]:=左からiミリまででk個分のお菓子を得るための最小コスト。j = 0なら、場所iを切らない。j = 1なら切る。更新には直前の情報しか使わないのでDP配列を減らせる。

0551 Icicles

not solved. DPです。つららxが折れるまでの時間をa[x]とする。つららを長い順に見て行く。長い順に見てくのでa[x+1] > 0 or a[x-1] > 0ならそのつららは今見てるつららよりもながい。つまりmax(a[x+1], a[x-1])時間後から成長し始める。

0552 Exposition

not solved. 何を言ってるのか分からない。

0553 Dungeon

回復する量を記録してって体力が負になったら最も回復できる地点で回復する。体力をセグメント木として持っておき、区間に加算するクエリと区間の最大値を求めるクエリを実装すると旨くできる。 マックスまで回復できると楽なんだけど、

DPが解けないです。データ構造が苦手。解けなかった問題の内4問がDPで解ける。