問題リンク Illumination 解法 建物があるマスにおいて、隣接している屋外のマスの数だけ飾りが必要になります。よって、屋外であるかどうかの判定表を先に作ります。適当な屋外のマス( (0,0)など )から幅優先探索をかければ作れます。あとは、建物マスにつ…

問題リンク Pasta 解法 DPもといメモ化探索です。 dp[v][s][c]: V日目からパスタSを厳密にC日間続けたときのV〜N日目の予定の組み合わせ数 という表を埋めることで解けます。 各パスタを1日続ける場合、2日続ける場合から予定が始まるので、最終的な答えは (…

問題リンク Best Pizza 解法 DPです。 dp[i][p]: i番目までのトッピングとpドルを使って得られる最大カロリー という表を埋めれば解けます。 ピザには生地を必ず使わなければならないので、表を埋めるときに、トッピングだけからなるカロリーを計算してしま…

問題リンク Soccer 解法 勝ち点計算してから順位付けするだけです。 クラスを作るとすっきり書けると思います。 ソース

問題リンク Lunch 解法 パスタの最小 + ジュースの最小 - 50 を求めるだけです。 ソース

問題リンク Shopping in JOI Kingdom 解法 ある1本の道に着目し、この道の上でショッピングモールからもっとも離れている場所はどこかを考えるのが方針です。そのためには、道の両端にある町それぞれについてショッピングモールとの最短距離が求まっていない…

問題リンク Books 解法 「ジャンルGの本の中からX冊を売るときの最大売値」は売値が高いものから売った場合になります。そのときの売値は 売値の大きいX冊の総和+(X-1)*X です。この値を全てのジャンル、売り冊数について求めておきます。 これを求めておく…

問題リンク Planetary Exploration 解法 sj[i][j]: (1, 1)-(i, j)の区画に現れる'J'の総数 という意味の表を'O'と'I'についても作ります。 (a, b)-(c, d)のクエリについて、この長方形に表れる'J'の個数は sj[c][d] - sj[a-1][d] - sj[c][b-1] + sj[a-1][b-1…