問題文 : スコーン配達計画(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…

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

問題文 : 村解法 : Rによってブロック分けをする. 近傍の8ブロックを1つのグループとみなして, このグループの数を幅優先探索で求める. setを使っているので, O(NlogN)時間で探索を終えることが出来る.コード : #include <cstdio> #include <cmath> #include <set> using namespa</set></cmath></cstdio>…

問題文 : 魔法少女さやかちゃん解法 : 問題文で示されている円環が直線だと考えると, ある音符とある音符の間は、昇順になっていることが望ましい. そこで、始点を音程のうちもっとも小さいもの, 終点を音程のうちもっとも大きいものとし, 始点->終点 にいく…

問題文 : 米集積場 (pdf注意)解法 : C(x) : Bバーツ以内でx個の水田から米を届けられるか, とすると, C(A)が成り立つ時, C(A - 1)も成立する. よって, xについて二分探索を行う.このとき, 集める水田が連続していたほうがいいことは明らかなので, R - x個の,…

問題文 : 本棚解法 : にかいどうさんの言うとおり, 昨日解いた「House Moving」と同じ問題でした.(重さがそれぞれ違いますが, あまり関係ない) ということで, 解説は昨日のもの参照です. BITでも解けるみたいなので, あとでBITで実装してみます.コード : #in…

問題文 : 引越し解法 : 荷物を動かすために使う体力を最小化する、ということは 動かさない荷物の重量を最大化する、ということと等しい. ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.荷物の重さをkとし, dp[k] -> …

問題文 : Cleaning Shifts解法 : dp[Ei] -> Ei秒まで掃除するのに必要な時間, とし, 牛iが時間Si秒からEi秒まで掃除でき, 雇うのに給料がMiかかるとすると dp[Ei] = min(dp[Ei], min(dp[Si] ~ dp[Ei]) + Mi) となる. dpテーブルはINFなどで初期化しておく. …

問題文 : タコヤキオイシクナール解法 : Nに対してMが小さいので, Nの座標圧縮を前もって行なっておく. (こうしても正しい結果が得られることは, 美味しさrのたこ焼きが(1, 0)と書かれたタコヤキオイシクナールを通っても美味しさrが保たれることから分かる.…

問題文 : Frequent values解法 : 各ノードは昇順になっているため、各数字の出現頻度をノードとして持つセグメント木を構築する. 各クエリについて, a[s] = a[t]であればt - s + 1を, そうでなければa[s]とa[t]を適切なだけ削り, RMQの処理を行う.コード : #…

問題文 : カード解法 :dp(l, r) -> 区間(l, r)のカードを併合するために必要な最小コストとすると, l番目のカードが最も上に, r番目のカードが最も下になるのは明らかなのでdp(l, r) = min(dp(l, r), dp(l, i) + dp(i+1, r) + a[l] * b[i] * a[i+1] * b[r]) …

問題文 : サージェント・ライアン解法 : 最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる. ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.コード : #include <cstdio> #include <cstring> #include <vector> #define INF</vector></cstring></cstdio>…

問題文 : 会津の埋蔵金解法 : f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う. 状態空間が5*10^4になるため, 楽にメモ化再帰ができる. …

問題文 : 人生ゲーム解法 : dp(i, j) -> 場所iにいてj円を持っている確率, とし動的計画法を行う. int型にキャストして表示することに注意.コード : #include <cstdio> #include <cstring> #include <algorithm> typedef struct { int dx; int money; } State; using namespace std; int </algorithm></cstring></cstdio>…

問題文 : 自転車ダイエット解法 : ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う. "一度訪れたケーキ屋に再び訪れることができない"ということに注意.コード : #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cstring></cstdio>…

問題文 : The Great Summer Contest解法 : 2つのペアをグループ化することが出来るので, 2つのペアをグループ化する. 4番目のタイプのコンテストは, 3つあると1 ~ 3番目のコンテストを1回ずつ開くのと同義になるので0回, 1回, 2回開く場合を考えて貪欲的にコ…

問題文 : 日本情報オリンピック旗解法 : 旗を4つに分解し, それぞれに何を割り振るのかが最適なのかを深さ優先探索で決めていく. ここで, 旗の大きさに対して最初から書かれている文字の個数が少ないので, 見ている範囲に文字が無い or 旗のレベルが0のとき…

問題文 : カンニング対策 (pdf注意, 3枚目)解法 : 監視する装置の範囲の最大値を求めれば良いから, すべての装置の精度を等しいものとして考える. すると, 端から貪欲的に装置を置いていける. 装置の範囲の最大値は, 二分探索で決めてやることで, O(Mlog(max…

問題文 : パチモンクリーチャー解法 : 最初に選ぶパチクリを決めると, 次に選ぶパチクリが決まっていく. このパチクリ同士の関係を線で結んでいくと, 必然的にグラフになっている. ゆえに, この問題はグラフの最短経路を求める問題に帰着できる. ここでは, …

コンテストページ : Cf#138 Div.2結果 : ox-x- 1122th 1495 -> 1409 (-86)感想 : これは笑う. Bは配列の要素が1つ少なくてWAしてしまった(絶望) 今回のセット頑張れば上位食い込めたのに色々こけてしまって残念...解法 :A. 平行六面体の, 3つの面の表面積が…

問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…