来年度の目標として, 今年の頭に掲げた目標があります.年度でいくとあと3ヶ月ほどありますが, 正直キリが悪いので今日で撃ち切って, 確認ついでに来年の目標を立てます.・JOI本選に出場する. -> passed system test ・AOJ Volume5の問題をすべて解く. -> pas…

問題文 : Dungeon (I)解法 : クエリでの求める距離fs_iと, スタートからの最短路についてソートし, BITで数え上げを行うと O(N log N)時間でこの問題を解くことが出来る. クエリや最短路は, 数に対し範囲が大きいので座標圧縮を行うと管理が楽になると考えら…

問題文 : Mars Map解法 : 座標において長方形が重なっている領域の面積を求める問題. 平面走査を行った.具体的には, ある長方形について, (x1, y1, y2)の間その領域を存在することにして, (x2, y1, y2)をその領域を消すタイミングとする.これをO(logN)で実現…

問題文 : 委員会(pdf注意, 1-2ページ目)解法 : 各頂点ごとに, やる気の最大値をメモする. 答えは, やる気の最大値が最も大きい頂点となる. ある頂点のやる気の最大値は, 自分自身のやる気＋自分の子までのやる気の最大値のうち, 負で無いものの和, として求…

問題文 : 貫きピラミッド解法 : 自分の地点での大きさを, 次のように, 2方向から伝搬しながら更新してやれば良い.どちらから先に行なっても良い. この更新が終われば, あとは各マスの和を取るだけである.O(WH)回の上書きで答えが求まるので, 計算量はO(WH)時…

問題文 : 国際情報オリンピック解法 :まず,"G を，N 問の合計点が G 点以上の選手の人数が全体の 1 / 12 以上となるような最大の値とする．このとき，金メダルが与えられる条件は，N 問の合計点が G 点以上であることである．"ということを, 問題を解きやす…

問題文 : 星空解法 : N個ある各星のLについて, そのLで囲める星の最大値を求める.ここで, 走査をする際に, x軸のみを走査し, y軸はセグメント木で, "ある点に於いて観測できる星の最大値"を管理すると, x軸の走査がO(N), その過程でのセグメント木の走査がO(…

問題文 : 解読解法 : dp[i][j], i番目の文字まで, jで終わる暗号の総数, とするとdp[i][i番目の文字] = Σ[j = 'A'...'Z' + ' ', j + i番目の文字は禁止されていない] dp[i - 1][j]となります. 答えは Σ[i = 'A'...'Z'] dp[L][i] です. dp[0][' '] = 1として…

結果 : oo△ 700 / 1000pts.3問目をバグらせてしまいBronze残留です. 来月はSilver行きます>それぞれの問題の詳細な解説はサイトにあるのでコードのみ.1. Meet and Greet 入力数に比例した時間の解法があるみたいですが, 解いた時頭が回っていなかったので愚…

問題文 : 高速道路解法 : 次のように, 2つの木を考える. 辺の更新のクエリが来た時は, euler-tourを行った時に、それぞれの辺が上りだったか、下りだったかを覚えておき処理する.頂点uからvへ行くクエリが来た際は, u->lca(u, v)に行くときは逆辺の木, lca(u…

問題文 : Housewife Wind解法 : 頂点u, vの最小共通祖先をpとすると, cost(u, v) = cost(u, p) + cost(v, p) = cost(root, u) + cost(root, v) - 2 * cost(root, p)となる. rootからある頂点への距離は, 通った辺を相殺する形で, BITで管理することでO(log N…

問題文 : お土産購入計画解法 : 上または左に3回しか戻れないということは, 7ターン以上前の状態に戻ることが不可能ということを指す. そこで, 6ターン前までに移動した方向を, bitで管理して持つ(e.x: 00->右 01->下, 10->左, 11->上).1つの方向を2bitで管…

こんにちは, kagamiz(@kagamiz) です! この記事は, Competitive Programming Advent Calendar Div2012 18日目の記事として書かれました. この記事では, ぼくが気に入っているデータ構造であるセグメント木について, 説明と問題演習・問題紹介を交えながら紹…

順当にいけば104点だと思います. (2以外の)解答も載せるので良ければ参考にしてください. 一応ソースや解答, validationのために作ったプログラムは http://www1.axfc.net/uploader/so/2717504に置いています.1.解法 : 答えは L - max(国語を終わる日数, 算…

問題文 : Trailing little cats解法 : a_{ij} = i回目のセットでj番目のネコが持っているピーナッツの数, とすると, a_{ij}は以下の2つのいずれかとなる :・a_{i-1σ(j)} + a_{i-1j} ・a_{i-1j}ここで, f(i)を ベクトルa_{i-1}からベクトルa_iを作る操作とす…

Virtual Participationでは2問, そのあと全部解き直しました.Cの問題文意味不明すぎて, DかEかを選ぶときにEを選んだのが失敗でした. (Dの方が簡単だったので...)DとEはとっても面白かったです. ちゃんと問題を取捨選択して取り組めるようにする力付けていき…

問題文 : Circular RMQ解法 : Starry Sky木をそのまま実装すれば良い問題です. ちなみに, Starry Sky木とは, ・区間[a, b]に値を加算する. ・区間[a, b]の(最大・最小)値を求める の操作が同時に出来るようなデータ構造を指します.この問題特有の「Circular…

JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.・ファレイ数列とは？ 約分された分数を昇順に並べた一群の数列であり、正の整数 n に対して、n に対応する (または、属する、深さn…

問題文 : Milking Time解法 : dp[N] : 時間Nまでに得られるミルクの最大量, とすると,dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)となる. ここで, 区間の端以外の時間はい…

問題文 : Crazy Thairs解法 : dp[i][j] = j番目を終点とする長さi + 1のLISの総数, とするとすべてのjについてdp[0][j] = 1,dp[i + 1][j] = Σ[k = 1...j - 1 | a[k] となります. Σの部分の計算をBITを使うと, O(nlogn)時間でこの問題を解くことができます.あ…

問題文 : 台風(pdf注意, 2ページ目~3ページ目)解法 : 昔解いた気もするのですが, そのときはセグメント木を使っていました.基本的には昔と方針はいっしょなのですが, 今回はReactive型の問題として出題されたときに対応できるよう, オンライン風に書いてみま…

問題文 : DNAの合成解法 : dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると, M + 1 ~ M + kまでの部分文字列s_kがあるとするとdp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる. DNA素を全て確かめるとO(strlen(合成したい…

問題文 : 占い解法 : あるカードを奇数回ひっくり返せばそのカードは裏で, 偶数回ひっくり返せばそのカードは表である.これは, カードをひっくり返す順序によらないので, y1 ≦ y ≦ y2 行 x1 ≦ x ≦ x2列のカード をひっくり返す, という命令を x1 ≦ x ≦ x2と…

問題文 : MooFest解法 : 2匹の牛について、離れている距離*Max(牛iの聴力, 牛jの聴力)が必要な声のレベルなので、 (全ての声の大きさの総和) = 最も聴力が必要な牛 * 離れている距離の総和 + 次に聴力が必要な牛 * 離れている距離の総和 + ... となる.ゆえに…

結果 : ooo--o---- 4完 31点 3WAくらい. 9位でなみだらしい＞＜感想 : デバッグに2時間位費やした点以外はだいたい良かったと思う. 5は思いついていた解法の計算量を測り間違えて書かずに残念なことをしてしまった. 4も簡単な幾何だったので, ちゃんと読もう…

問題文 : ルパン四世解法 : まず, bitDPで最短時間を求める. その後に, 最短時間を達成する訪問の仕方を出発するノードから確かめていく. 出発するノードは, dp[S | S_n = 1, else S_i = 0][n]の中で最も小さいものとなる.誤差に注意して計算していくこと.コ…

問題文 : 冊子の配布解法 : 得られるやる気を最大化したいので, 葉まで冊子を流し, その中の最大値を取っていけば良い. つまり、葉までやる気を伝搬させれば良い. この操作をM回繰り返す.木の操作、最大値の取得をO(N)時間で行うことで, O(MN)時間でこの問題…

問題文 アナグラム(pdf注意, 1枚目)解法 : 元の文字列sの各文字を昇順にソートしたs'を考える. 目的の文字列の前にある順列の総数は, s'の先頭から文字を選んでいき, 元の文字列の接頭辞にならない文字列の組み合わせを全て求めれば求まる. もとの文字列と現…

問題文 : 象使い(pdf注意, 2-3ページ目)解法 : 辺と辺で成される角を求めるには, (直前の点, 今いる点, 次に行く点)の3つの情報が必要である.直前の点をvec(P_0) = (x0, y0), 今いる点をvec(P_1) = (x1, y1), 次に行く点をvec(P_2) = (x2, y2) とすると (vec…

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