Lilliput Steps

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

JOI

ファレイ数列のいろいろ

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

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

JOI春合宿 2012-day4 Bookshelf

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

JOI春合宿 2012-day1 JOI Flag

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

JOI春合宿 2008-day2 cheating

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

JOI春合宿 2011-day2 keycards

問題文 : カードキー解法 : 包除原理のようなものをつかう.この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通り…