問題文 : かくれんぼ解法 : 障害物の左上の座標についてそれらを昇順ソートし, 各x座標について障害物の重なりの大きさを持つ. そして、実際に障害物をフィールドに挿入していく. その過程で武器を防げるだけの大きさになれば、その座標を出力する.ここで、…

問題文 : スコーン配達計画(pdf注意, 28枚目-30枚目)解法 : 部分列 mod Mの最大値を求める問題である. 区間[i, j]の和 mod Mをすべて確かめると, 累積和を用いてもO(N^2)となってしまうため、セグメント木を使ってこの計算を高速化する. i jについてはループ…

問題文 : Cactus解法 : 答えは2^(パスs -> tまでの中にあるサイクルの数)になる(図を描いて考察すると分かる.) よって、サイクルを検出して、それを1つの頂点に圧縮する.頂点に圧縮する際に、根付き木にグラフを再構築すると, sとtのLCAをpとしておき s->pの…

結果 : ooox------- 30+50+60=140pts, 63rd.感想 : 最後の一時間は参加していなかったものの、結局これ以上の点は望めなかったと思う. 実力通りかなあ. 結局答え聞いちゃえば分かるんだけど、閃かなかったら何にもならないし、それがコンテストなんだと思う.…

問題文 : 地域解法 : C(x) : 距離x以下でM個の地域に分割できるか、とすると C(x)が成立すればC(x - 1)も成立するので、xについて二分探索を行う. 実際に距離xを超えるかは, 与えられたグラフを根付き木にし, 2つの辺によって結ばれる地域のコストの和を距離…

問題文 : n個の行列の連鎖 が与えられたとき、スカラー乗算の回数が最小になるように積A1A2A3...Anを完全に括弧付ける問題を連鎖行列積問題(matrix-chain multiplication problem)という。n個の行列について、行列Aiの次元が与えられたとき、積A1A2...Anの計…

問題文 : Compatible Numbers解法 : 入力される数はすべて22bitで表現されている数だと仮定する. (∵ 4 * 10^6 (=入力の最大値) a & b となるbはたくさんあるので, bをaのbitを反転したものとする.ここで, dp[k] : 数kを, もとの数列の数を変形して作ることが…

問題文 : ぼくの友達は小さい解法 : 友達を重さでソートし, "使わない友達"を決めると, いくつまでの重量の組み合わせをいれるかを決めることが出来る. この組み合わせを求める部分は, 典型的なナップサック問題を解くDPで求めることが出来る. よって、O(NW)…

問題文 : Buses解法 : 各バスの出発する地点をs[i], 到着する地点をt[i]とすると バスをt[i]について昇順にソートし、その順に番号をつけます.i番目のバスで乗れる地点は, s[i] ≦ x このjたちは明らかに連続しているので、これらの範囲を満たすjたちを二分探…

問題文 : Big Maximum Sum解法 : 各配列について ・配列を横断した時の総和 ・配列の左から項をとっていったときの最大値 ・配列の右から項をとっていったときの最大値 ・配列中の要素の最大値を求めると、求めるべき答えは部分列の連続する項を求める問題(A…

問題文 : プラグ解法 : n * nグリッドの真理値表を考える. マス(i, j)は "プラグiがソケットjに使われるか"を表し, (i, j) が0ならtrue, それ以外ならfalseとする. 上の真理値表でM個の証言で示される長方形領域をすべて塗りつぶすが, その際にはいもす法 (J…

問題文 : ダンジョン解法 : 各階で回復出来る量を記録しながら, 実際にダンジョンを潜っていく. 体力が負になってしまった場合, 最も回復出来る地点で回復する.体力をセグメント木として持っておき, 区間に加算するクエリと区間の最大値を求めるクエリを実装…