問題リンク Sheets 解法 a[y][x]: 左下の座標が(x, y)である1*1のマスを覆うシートの数 という表をyについて1行ずつ更新する方法で解くことができました。 シートの枚数が変わるタイミングはシートの上辺と下辺の部分です。 面積はa[y][x]が正になっている部…

問題リンク Walking Santa 解法 x座標方向とy座標方向について独立に考えます。 ある点Xと、N個のx座標の差の絶対値の総和が最小になる場所はど真ん中の座標です。例えば、Nが奇数なら中央のx座標、Nが偶数個なら中央2つのx座標の区間内が最小になる場所です…

問題リンク Bingo 解法 DPで解いたわけですが、DPについて色々と考えさせられる問題でした。 まず、ビンゴカードは狭義単調増加の長さN*Nの1次元配列と捉える事が出来ます。つまり、1〜Mの中からN*N個の要素を取り出して、その和がSになるパターン数を答える…

問題リンク Card Game II 解法 公式解説を読んで解きましたが、所々理解が追いついてない状態です。 Mで場合分けして解くようです。 M=0のとき、nk枚目に引くカード(最後に引くカード)が1である場合が、ゲームをクリアする必要十分条件というらしいのです。…

問題リンク Dividing Snacks 解法 DPです。 dp[ i ][ j ][ k ]: 左からiミリメートルまでを考えて、k個分のお菓子を得るための最小コスト。j = 0なら、場所 i を切らない場合で、j = 1なら場所 i を切ることを表す という表を埋めて解きます。 初期値はdp[0]…

問題リンク Shuffle 解法 数字が連続しているカードをまとめて区間としてシャッフル毎に区間を管理するのが方針です。 最終的に意味のあるカードの山はp〜q番目の部分だけなので、この部分のみを区間の初期値とし、シャッフルを逆に辿るようにしていきます。…

問題リンク String With Rings 解法 ? えー、先に言っておきますと真っ当な方法でAcceptに辿りついていません。 真面目なプログラムで解きたい方の疑問には答えられません、よしなに。以下、自分の思考の変遷をつらっと書きます。1. 反復深化法でいこう 到達…

問題リンク JOI Flag 解法 ビットDPで解きました。 旗の種類は3^(?の数)だけあります。求めたいのは良い旗ですが、その余事象である悪い旗を数えても、解が求まります。 左上からマスを決定するとして、(i, j)のマスXについて考えます。もしNマス前に、"JO"…

問題リンク Zig-Zag Numbers 解法 DPもといメモ化探索で解きました。 扱う数値の範囲が異常に広く、更にその中のMの倍数にしか興味がないというのが厄介なところです。500桁近いある値がMの倍数かを判定するのもままならないかもしれません(自分がそうでした…

問題リンク Bug Party 解法 「X匹の虫をシャーレに入れることができるか」というXについて２分探索して解きました。 各Xについてのチェックについて説明します。 まず、虫をX匹選んだとして、許容量の一番小さい虫がボトルネックとなります。その虫の放出量…

問題リンク Reindeer with no sense of direction 解法 プレゼントの置き順をそのまま追おうとすると４方向＋その中のどこに置くかで遷移先が多いですが、置いたプレゼントを逆に辿ろうとすると、最初にぶつかったプレゼントを取るしか選択肢がないので探索…

問題リンク Cup 解法 Mが結構大きい数字ですがコップの動きをシミュレートするだけで解けます。 あるコップの状態において動かし方は高々2通りしかありません。更にそのうちの1通りは1手前の状態に戻すための動かし方なので、結局動かし方は1通りに定まりま…

問題リンク Nails 解法 2次元int型配列 t[i][j]を用意します。t[i][j]は(i, j)を上の頂点とする「よい正三角形」の中で最も長い1辺の値が入っているとします。「よい三角形」が無い場合は負の値とします。初期値は-1です。サンプル入力では、 t[2][2] = 1 t[…

問題リンク Night Market 解法 DPです。 dp[i][j]: 夜店iまでを使って時刻jまでで得られる最大満足度 という表を埋めれば解けます。 夜店iを時間jに遊び終えるように訪れるとき、花火を見逃すようなら夜店で遊べません。 ソース

問題リンク Card Game is Fun 解法 Bの連続部分列のうち、Aに部分列として登場するものの中で最大の長さは何かという問題と同義です。Bの中で連続部分列の先頭hを決めたら、Aの中でその数字が一番最初に登場する場所を記録します。以降、一番最初に登場する…

問題リンク JJOOII 解法 Oがk個連続している部分の左側にk個以上連続しているJ、右側にk個以上連続しているIがあればレベルkのJOIが存在することになります。また、この場所ではレベルk以外のJOIを作ることはできません。同じ文字が連続している部分を圧縮す…

問題リンク 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…

問題リンク Dice 解法 サイコロをきちんと実装できればやるだけ問題となります。 自分は手元にライブラリがあったのでそれを使うだけでした。 ソース

問題リンク Data Conversion 解法 変換表はMapで作りました。 作る文字列の長さは最大で10^8近くなってStringを+で連結していくとまずTLEするでしょう。 StringBuilderを使えば高速です。 ソース

問題リンク Card Game 解法 ルール通りに得点を計算します。 ソース

問題リンク Authentication Level 解法 a[i] (0 という表を２つのマップについて作って解を調べる、というのが方針です。 マップの大きさが最大500*500と大きめなので少し工夫しないとTLEに引っかかると思います。 入り口を訪れたら、次の訪問先の候補は隣接…