Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI

JOI 本選 2012 - 2013 参加記

2 / 9 (Sat.) から 2 / 10 (Sun.) にわたって開催されたJOI (日本情報オリンピック) の参加記を書きます. 2 / 8 (Fri.), Okinawa ・本選開催前日だというのに25 時まで起床する. ・8 時30 分からある生物の試験に恐れ慄きながら就寝する.・生物の試験で(たぶ…

APIO 2012-1 - Dispatching

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

JOI春合宿 2008-day3 Nightman

問題文 : 夜警解法 :登場する点のうち,・警備員のいる点 ・建物の点を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.これが出来れば, あとはダイクストラ法を各点に行うだけである.コード : #include <cstdio> #</cstdio>…

JOI春合宿 2011-day4 orienteering

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

JOI2007 本選

友達に勉強を教えながら, ゆったり2007を解いてみました. 4 -> 3 -> 2 -> 1 -> 5 の順で解きました. 4 が一番簡単なんだよなあ... 1時間半くらい余らせて終了.1. 碁石並べシミュレーションを行う. オセロっぽい操作を行う. #include <cstdio> #include <cstring> #include <algorithm> #i</algorithm></cstring></cstdio>…

JOI春合宿 2011-day1 joitter

問題文 : ジョイッター解法 : (1) 1の人がいる場合 (2) 1の人がいなくて, 2, 3の人がいる場合 (3) 3の人だけの場合で場合分けをする.(1) 1の人がいる時は, その人と他の人を全員友達にしてあげれば, 最小の辺数を達成できる.(2) N人の人がいれば, ある人と皆…

JOI春合宿 2009-day4 Chopsticks

問題文 : 塗り箸解法 : dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とするとdp[i][i] = 1, dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])となる. これは, 区間の幅を小さいものから計算すれば実現できる.コード : #…

JOI春合宿 2009-day3 Ski

問題文 : スキー解法 : 全体の平均速度について2 分探索を行う. ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる. 通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜け…

JOI春合宿 2009-day1 Stamps

JOI

問題文 : 判子解法 : まず, この作業でスタンプを作ることは, スタンプからIOIOI...OIの形を復元することを考える. このとき, 境界条件を考えないために, IO と OI を文字列に連結する. このとき, "OOO"や"III"の形で連結されている箇所があれば, 真ん中を変…

JOI春合宿 2011-day2 guess

問題文 : 数当て解法 : 最初に, 1の数をO(N)時間で当てる. あとは, 1の情報を元に二分探索を行う. Σ[i = 2, 99] ceil(log_{2}i) = 580 くらいなので, 最悪でも580 + 100 コード : #include <cstdio> #include <cstring> using namespace std; void print(int *p, int n) { fo</cstring></cstdio>…

JOI春合宿 2010-day2 aplusb

JOI

問題文 : 足し算解法 : vectorを使って実際に足し算を行う. 繰り上がり/桁数が変わる位置のみに微妙な変化があり, 間の数の計算は省くことができる.コード : #include <cstdio> #include <climits> #include <vector> #include <algorithm> using namespace std; typedef long long lint; typedef</algorithm></vector></climits></cstdio>…

JOI春合宿 2010-day1 sengoku

問題文 : 戦国時代解法 :見張り達の見張るエリアを, 左上と右上の線で分ける.まずは左上側の線の処理を以下のように行う.点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.右…

JOI春合宿 2010-day4 lake

問題文 : 湖解法 :まず,dp[l][r] = 区間[l, r]での運行数の最大値, とすると dp[l][r] = max(dp[l][r], dp[l][s[i] - 1] + dp[s[i] + 1][t[i] - 1] + dp[t[i] + 1][r]);となる. ただし, s[i], t[i]はそれぞれ船の来航する地点の座標で, s[i] これは, t[i]に…

JOI春合宿 2008-day1 committee

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

JOI春合宿 2009-day1 pyramid

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

JOI春合宿 2011-day4 IOI

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

JOI春合宿 2009-day4 Starry Sky

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

JOI春合宿 2011-day3 deciphering

問題文 : 解読解法 : 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として…

JOI春合宿 2010-day4 highway

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

JOI予選 2012-2013

JOI

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

ファレイ数列のいろいろ

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

JOI春合宿 2008-day4 typhoon

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

JOI春合宿 2010-day2 DNA synthesizer

問題文 : 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(合成したい…

JOI春合宿 2012-day3 fortune telling

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

JOI春合宿 2007-day3 Anagram

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

JOI春合宿 2007-day3 Route

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

JOI春合宿 2010-day3 Hide-and-seek

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

JOI春合宿 2010-day2 Regions

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

JOI春合宿 2010-day4 plugs

JOI

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

AOJ 0553 - Dungeon

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