Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

UVa 12686 - Trending Topic (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12686

問題概要

$1$ 日毎のWebに掲載された文章が与えられる.
また,$1$ 日毎の文章の間にクエリが与えられることがある.
各クエリでは,最近 $7$ 日間の文章に出てきた単語のうち,出現頻度が高い順から $N$ 個,出現回数と単語をペアで出力する.
ただし,同率 $N$ 位の単語があれば,同率 $N$ 位の単語はすべて出力する.
同じ出現頻度の単語はアルファベット順に出力する.
また,$3$ 文字以下の単語は無視する.
単語は $20$ 文字以下でアルファベット小文字のみからなる
日数は $20000$ 以下
$1$ 日の文章中に出てくる単語の数は $20000$ 以下
全体で出てくる単語の種類数は合計で $20000$ 以下

解法

適当に実装する.
例えば,過去 $7$ 日間の単語の出現頻度をmap<string,int>などで管理し,クエリが飛んできたらマージしてソートして出力する.

UVa 12685 - Binary Tree (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12685

問題概要

無限に大きい $2$ 分木を考える.
各ノードは,左の子供ノード,右の子供ノード,上に親ノードを持っている.
ただし,ルートの親のノードはルートとみなす.
命令の列 $S$ と $T$ が与えられる.
命令はL, R, Uの3種類で,それぞれ,今いるノードから左,右,上のノードに移動することを意味する.
最初はルートにいて,命令列 $S$ を全部こなす.
その後,命令列 $T$ をこなすのだが,命令列 $T$ に関しては,各命令をこなすか,その命令をスキップするかを選ぶことができる.
全ての操作が終わった時に,最後にいること可能性のあるノードの数を mod $ 21092013$ で求める問題.
$S, T$ の命令の数はそれぞれ $10^5$ 以下

解法

まず,$S$ を眺めていって,Uでなければその命令を追加,Uなら最後に追加した命令を削除,として,
$S$ が終わった地点でのいる場所を,ルートからL, Rのみの列を用いて表しておく.
また,命令列 $T$ の各命令に対して,その後に出てくる一番最初の命令L, R, Uの場所を後ろからなぞって計算しておく.
$T$ のある場所以降で,LとRのみを用いて移動できるノードの数をDPで計算する.この時,上で計算した各命令が出てくる最初の場所を使えば $O(|T|)$ で計算できる.
まず,現在位置から,$1$ 歩左に行ってから,および,右に行ってから,その先に移動パターンをDP表から答えに足す.
後は,上に何回か移動した後,逆方向に進んでから,その先の移動パターンを足していく.

UVa 12684 - VivoParc (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12684

問題概要

$N$ ノードのグラフが与えられる.
枝がつながっているノード通しは別の色に塗ることにして,$4$ 色で塗り分ける方法を $1$ つ出力する問題.
答えが存在することは保証されている.
$N \leq 100$

解法

枝刈り探索で間に合う.

UVa 12683 - Odd and Even Zeroes (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12683

問題概要

$f(k)$ を $k!$ を $10$ 進数で書いた時,最後に $0$ が続く数とする.
$f(0), f(1), \ldots, f(n)$ のうち偶数の物の数を求める問題.
$n \leq 10^{18}$

解法

$f(k)$ が偶数である条件は
 $k$ を $5$ 進数で書いた時,$5^{2m}$ の桁の数字を足したら偶数になる
ということ.
与えられた $n$ を $5$ 進数に直して,桁DPする.

UVa 12682 - Joe is learning to speak (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12682

問題概要

Joe君は,昨日までに聞いた英語の文章の連続する $k$ 個の単語の列を全部覚えている($k=1,2,\ldots,n$ で $n$ は入力で与えられる).
また,Joe君は,"Joe"という単語は既に知っており,昨日までに聞いた英語の文章は全部与えられる.
今日聞いた文章が $1$ つずつ与えられるので,各文章に対して
 知らない単語があれば,その単語の意味を聞く
 文章が $2$ つ以上の単語からなり,その文章の連続する $k$ 個の単語の列で,知らないものが $1$ つでもあれば,文章の意味を聞く($k=1,2,\ldots,n$)
もちろん,$1$ 度聞いた文章は昨日聞いた文章と同様に覚える.
Joe君が発する言葉を出力する問題.
単語は,大文字と小文字が違うだけのものは同じとみなす.
Joe君が単語の意味,文章の意味を聞くときは,その時与えられた文章,単語と同じように大文字小文字を使い分ける.
$2 \leq n \leq 5$
$1$ 単語の文字数は $20$ 文字以下で,アルファベットのみ.
$1$ つの文章に含まれる単語の数は $100$ 以下.
出てくる単語の種類は合計で $2 \times 10^4$ 以下
前日に聞いた文章,今日聞いた文章の数はそれぞれ $1000$ 以下

解法

頑張って実装する.
文字列をそのまま扱うと重たいので,単語の連続する列をハッシュ値に変換にしてsetに突っ込んだ.

UVa 12681 - Decoding the Hallway (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12681

問題概要

最初線分が $1$ 個あって,方向は左から右に進むことを考える.
時間 $t=1$ で,$1$ 回線分を左方向に折り曲げる.($2$ つの線分に別れる)
時間 $t=n+1$ では,時間 $t=n$ の各線分に対して,進行方向にそって,左,右,左,右,・・・と折曲げていく.
問題文の図を参照.
時間 $t=n$ の線分を移動するときに,曲がる方向の列を文字列として $S_n$ と書く.
$n$ と文字列 $T$ が与えられるので,$T$ が $S_n$ の部分文字列かどうかを判定する問題.
$n \leq 1000$
$|T| \leq 100$

解法

$S_1 = {\rm L}$ で
 $S_{n+1} = S_n + {\rm L} + f(S_n)$
で求められる.ただし,$f(x)$ は $x$ の文字列の順番を反転させた上に,LとRを反転させたもの.
この規則から,十分大きな $n$ 以降は,$100$ 文字以上の部分文字列が新しく増えることはないので,$n$ が大きい時は,$n=10$ ぐらいに落とす.
後は愚直に判定すれば良い.

UVa 12680 - Shopping Malls (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12680

問題概要

ショッピングモール中の $N$ 個の施設とその場所(何階にあるかと $x,y$ 座標)が与えられる.各フロア間の距離は $5$ m で,$x,y$ の単位は m.
施設間に移動する方法が $M$ 個与えられる.
それぞれの移動方法は $2$ つの施設間を移動でき,以下の $4$ 種類がある.
 walking または stairs:歩く距離は $2$ つの施設間のユークリッド距離(walkingとstairsの違いは施設が同じフロアにあるかどうかのみ)
 lift:歩く距離は $1$ mで移動できる
 escalator:順方向には $1$ mで移動でき,逆方向には,施設間のユークリッド距離の $3$ 倍歩けば移動できる.
クエリが $Q$ 個与えられる.
各クエリでは,施設 $a$ から $b$ に移動する方法のうち,最小の歩く距離で移動する方法を出力する.
たぶん移動方法は一意に定まるか,複数の最適解があればどれを出力しても良いと思われる.
全ての施設間で移動する方法があることは保証されている.
$N \leq 200$
$M \leq 1000$
$Q \leq 1000$

解法

各クエリごとにダイクストラして経路復元する.

UVa 12679 - It Can Be Arranged (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12679

問題概要

$N$ 個の授業があり,授業 $k$ の開始時間 $A_k$ と終了時間 $B_k$,その授業の受講者 $S_k$ が与えられる.
$1$ つの部屋を借りると最大で $M$ 人まで収納できる.
また,ある部屋で授業 $i$ を行った後,授業 $j$ を行う場合,清掃時間として間を $C_{ij}$ だけ空けなくてはいけない.
借りなくてはいけない部屋の最小数はいくらか求める問題.
$N \leq 100$
$0 \leq A_k \leq B_k \leq 10^7$
$0 \leq C_{ij} \leq 10^7$
$1 \leq M, S_k \leq 10^5$

解法

DAGの最小パス被覆の変形版.
それぞれの授業に必要な教室数 $\lceil S_k / M \rceil$ は先に計算しておく.
 すべての授業を別の教室を用いた場合の必要数 - 使いまわした教室ののべ数
で答えを計算する.
使いまわせる最大数は,最大流で求めることができる.

UVa 12678 - Mixing Colours (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12678

問題概要

色を混ぜ合わせると新しい色ができる,
 $C_A + C_B = C_C$
という形のルールが $R$ 個与えられる.
連続する色の列の,隣り合う $2$ つを上のルールを適応して $1$ つの色になるまで続けるというゲームが有る.
ただし,ルールに無い場合は,そのような $2$ 色を混ぜ合わせることはできない.
おそらく,任意の列に対して,どの順番でルールを適応しても最終的にできる色は一意に定まると仮定して良いと思われる.(もしくは $1$ 色のみできない場合も有り得る)

いくつかクエリが与えられる.
各クエリでは,$C$ 個の色の列が与えられる.
ただし,各要素は厳密に何色なのかはわからず,この色である確率がいくらという形で与えられる.
混ぜていって最終的に $1$ 色できるような色の列のうち,最も確率が大きい物を考える.
その列を用いて最後にできる色は何かを求める問題.
ただし,最終的に $1$ 色にできない列しかないならそれを指摘する.
$R \leq 100$
$C \leq 500$

解法

区間DPする.
それぞれの区間において,この色ができるという最大の確率をメモする.
状態数が $O(C^2 R)$ で,計算量は $O(C^3 R)$ になる.($O(C^3 R^2)$ などにすると多分まずい)

UVa 12553 - Countdown (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12553

問題概要

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100 が書かれた24枚のカードのうち6枚が配られる.
配られたカードとターゲットナンバー (1以上1000以下) が与えられる.
毎回,配られたカード2枚を,それが書かれた数字をa,bとすると
 a+bのカード
 a-bのカード (b-aのカード)
 a*bのカード
 a/bのカード (b/aのカード)
1回に変換することができる.
ただし,0以下のカードや,非整数のカードを作ることはできない.
最終的に,手持ちのカードの一枚をターゲットナンバーにできるだけ近づけたい.
カードは全部使う必要はない.
そのような方法を1つ求める問題.

解法

全探索.枝刈りとかしなくても通る.

UVa 12551 - Shares (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12551

問題概要

N個 (500以下) のアイテムの種類がある.
P個 (50000以下) の商品のセットが売られている.各セット1個までしか買えない.
各セットはN種類のアイテムがいくつか含まれている,
各アイテムの今日の値段と,明日の値段が与えられる.
各セットの価格は,含まれるアイテムの価格の和.
各アイテムは明日各値段で売れる.
今C円 (2^30以下) もっていて,借金などはできないとして,1日で儲けられる最大額を求める問題.

解法

DPする.
買えないセットを除外し,各セットの値段と現在持ってるお金のGCDで全部割って状態数を削減すると間に合う.
という解説だった.エスパーゲー.

UVa 12550 - How do spiders walk on water (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12550

問題概要

滝から距離D (10000以下) の位置に蜘蛛がいる.川は一直線で,長さ1ごとのセルに分割されている.
滝にどこまで近づいても滝に落ちずに帰ってこれるかを求める問題.
蜘蛛の力強さを表すパラメータPが与えられ,今いるセルの水の速さがP以下なら水の流れに逆らって移動できる.
各セルの水の速さは,滝に近づくに連れて単調非減少.
各セルの水の速さは全部与えられるか,最初の一部のみ(最小でも4セル分)与えられる.
最初の一部のみ与えられる場合は,各セルの水の速さは,それより手前の2セルの線形結合で書けることが保証されている.(線形結合の定数はすべての場所で同じ)
どこまで近づいても滝に落ちない,距離Dでも滝に落ちる場合はそれを指摘する.

解法

連立一次方程式を解いて係数を求める.
解が不定(行列式が0)の場合は,等比級数になっているので,別処理をする.

UVa 12549 - Sentry Robots (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12549

問題概要

100*100以下のグリッドが与えられる.
グリッドには障害物と,監視したい点がある.
障害物は視界を遮る.
監視カメラを置くと,おいたセルを含めて,そのセルから上下左右の一方向に幅1の半直線上のセルをすべて監視できる.(障害物にあたったらそこまで)
すべての監視したい点を監視するために置かなければいけない監視カメラの数を求める問題.

解法

最大流.
縦,横の各線分を切り出して,それぞれを二部グラフの左右に置く.
各監視したい点について,それが属す縦横セグメント達の間に枝を貼る.

UVa 12547 - RNA Secondary Structure (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12547

問題概要

A,C,G,Uのみからなる文字列が与えられる.
ランレングスで圧縮されて与えられる.
AとU,CとGを線で結んでペアを作りたい.線は交差してはいけない.
また,CとGのペアを作れる最大数(20以下)が与えられる.
最も多くのペアを作った時,何ペアできるかを求める問題.
ランレングスで,最初の要素(最初の同じ文字が続いているブロックの文字数)と最後の要素の大きさは5000以下.
最初と最後を除いた部分の文字数は50文字以下.

解法

最初の要素と最後の要素をペアにできるなら,それをペアにしても他を妨害しないので,ペアを作っておく.
最初に続く文字列の数と,それがペアになれる文字の数を比較して,最初の文字がペアになれないなら消しておく.
などの処理をすれば,文字列の長さは150以下ぐらいにはなる.(もっと短くできるはず)
後は愚直にDPすれば良い.
部分文字列が与えられた時,最初にペアを作る要素の一番左の文字で場合分けして,そのペアになる文字の位置で場合分けして,C,Gのペアが何個作れるかをそれぞれに振り分ける.
一番左の文字を使わない場合は,一つサイズの小さい部分文字列に帰着されるので,そこは全部試したりしない.
O(長さ^3 * 20^2)ぐらいになるが,定数がかなり小さく通る.

UVa 12546 - LCM Pair Sum (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12546

問題概要

nが素因数分解された形で与えられるので,
 f(n) = sum[1 ≤ p ≤ q ≤ n, LCM(p,q)=n] (p+q)
の値を mod 1000000007 で求める問題.
nの素因数はそれぞれ1000以下で,含まれる素因数の種類は15種類以下,各素因数の数は50以下.

解法

p ≤ qという大小関係を無視して,(p, q) = (n, n)だけ1回しか登場しないので,後でそれを足して2で割る.
nが素因数pをk個含んでいるとしたら,pとqの少なくてもどちらかはpをk個含んでいる.
それぞれの素因数pについて,
 pだけk個含んでいる,qがk個含んでいる(pもk個含んでいるかも)
で最大2^15通り場合分けする.
場合分けすれば,それぞれpとqの取りうる値の数とか取りうる値の和など簡単に求めれるのでそれをかけたり足したりしていけば良い.
メモできる部分はメモしてO(2^15)にしないとTLEになりがち.O(2^15 * 15),O(2^15 * 50)などは厳しい.

UVa 12545 - Bits Equalizer (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12545

問題概要

同じ長さの文字列SとTが与えられる.長さは100以下.
Sは0, 1, ? のみ,Tは0, 1 のみからなる.
Sを変換してTに一致させるのに必要な最小手順数を求める問題.
行える変換は
 0を1に変える
 ?を0に変える,または,?を1に変える
 好きな2箇所の文字ををスワップする

解法

Greedyに変換していく.
0を1に変えなければいけない場所の数,などを最初に数えて処理していくと楽.

UVa 12544 - Beehives (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12544

問題概要

ノード数n (500以下), 枝数m (20000以下) の無向グラフが与えられる.
2個以上のノードからなる集合で,そのノードのみから成る部分グラフが任意の枝を1個取り除いても連結である,という条件を満たすものを考える.
そのような集合が存在するかどうかを判定し,存在するならその集合の最小サイズを求める問題.

解法

長さ3以上のサイクルのうち,最も短いものを求めれば良い.
始点を適当に決めてBFSして,始点からの距離を求めていく時,すでに訪れたノードに衝突して,さらにそれが今いるノードより遠いか等しいならそれでサイクルができている.
(サイクルの長さは始点から今いるノードまでの距離 + 始点からぶつかったノードまでの距離 + 1)
どこを始点にするかは全部試してO(n*(n+m)).

UVa 12543 - Longest Word (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12543

問題概要

単語は,アルファベット小文字,大文字,ハイフンのみからなる連続した文字のこと.
文章が与えられるので,最も長い単語のうち,最初に出てくるものを求める問題.
その単語の中のアルファベット大文字はアルファベット小文字に直して出力する.

解法

やるだけ.

UVa 12542 - Prime Substring (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12542

問題概要

255文字以下の数字から成る文字列が与えられる.
その部分文字列に現れる100000以下の素数のうち,最も大きいものを求める問題.
問題文には書かれてないけど,必ず部分文字列に100000以下の素数が含まれることは仮定して良さそう.

解法

最初に素数を列挙して,O(1)で各数が素数かどうかチェックできるようにしておく.
後は,長さ5以下の部分文字列に対して全部素数かどうかチェックする.

UVa 12541 - Birthdates (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12541

問題概要

N人 (100以下) の人の名前と誕生日が与えられる.
最も若い人と最も年老いた人の名前を求める問題.
同じ誕生日の人,同じ名前の人はいない.

解法

最小値,最大値を求める.

UVa 12540 - Warp Speed II (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12540

問題概要

ある宇宙船はN個 (100以下) の状態に変形ができる.状態を0~N-1で番号付ける.
時間1経過ごとに1回変形(もしくはその形態を維持)でき,状態iから状態jに変形するコストが与えられる.(維持にもコストがかかる)
その宇宙船はM個 (1000以下) のアクションが出来る.アクションを0~M-1で番号付ける.
各状態において,各アクションを行うのに必要なコストが与えられる.ただし状態0では何もアクションできない.
クエリが幾つか与えられる.
各クエリは,アクションの列 X[1], X[2], ... X[k] (kは1000以下) で,時間iでアクションX[i]を行わなければならない.
また,時間0,時間k+1では状態0にならなければならない.
最小コストと,それを満たす変形の列を求める問題.複数あるなら変形の列は辞書順最小のものを求める.
与えられるコストは全部100以下.

解法

DP or メモ化再帰 + 経路復元.
 今何回目のアクションをしたか,今どの状態か
を状態にして最小コストをメモる.
DPなら最後から順番に処理すると辞書順最小を求めやすい.
各クエリに対してO(N^2 M).

UVa 12537 - Radiation (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12537

問題概要

二次元平面上にN個 (200000以下) 家がある.座標が与えられる.
2つの原子力発電所A, Bが与えられる.座標が与えられる.
Q個 (20000以下) のクエリに答える問題.
各クエリでは,発電所Aに対する半径R1とBに対する半径R2が与えられる.
発電所Aからの距離がR1以下の家には防災グッズが与えられる.
発電所Bからの距離がR2以下の家には防災グッズが与えられる.
防災グッズが2個もらった家の人は,防災グッズがもらえなかった家の人に上げることができる.
防災グッズを所持できない家の数の最小値を求める問題.
各半径は13000以下の正整数,各座標は20000以下の非負整数.

解法

結局は,max(0, N-もらえる防災グッズの数)が答え.
各発電所からの距離で家をソートしておくと,各発電所からもらえる防災グッズの数は二分探索ですぐ求まる.
半径が整数で小さいので累積和みたいなのを求めておいても良い.

UVa 12536 - Optimal Spaceway (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12536

問題概要

2次元平面上のN個 (10000以下) の点が与えられる.
まず,それぞれの点との距離の二乗和を最小にする直線を求める問題.(距離の二乗和のみ答える)
その後,Q個 (100以下) のクエリに答える問題.
各クエリは,N個のうちの1点kと,その重みMが与えられるので,
 kまでの距離の二乗 * M + その他の点まで距離の二乗和
を最小にする直線を求める.(和のみを答える)

解法

要するに各クエリに対してO(N)で答えられれば良い.(最初のはM=1とすれば良い)
最小二乗法 (y座標の差の2乗和を最小にするやつ) で直線を求め,その直線がx軸に平行になるように,各点を回転するというのを繰り返し,
最小二乗法で求まる直線がx軸に十分平行に近くなるまで行った.
その際,毎回愚直に計算するとTLE.
最小二乗法では,直線を求めるのに必要なのは
 x座標の和,y座標の和,(x座標)^2の和,(y座標)^2の和,(x座標)*(y座標)の和
等なので,それらを1回求めておくと,回転した後の上の5つの値は回転角から計算可能.
なので,毎回回転させなくてもよく,直線を求めるだけならO(1)でできる.
なので各クエリに対して,上の計算は1回のみで良い.(または最初に1回だけ計算しておけば良い)
また,距離の二乗和も十分平行に近くなった時のみ計算すると各クエリに対して1回のみ計算すれば良い.
もっと良い方法がある気もする.

UVa 12535 - Probability Through Experiments (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12535

問題概要

円周上の異なるN点 (20000以下) が与えられる.(円の中心から引いた線とx軸とのなす角で与えられる)
その中から3点を選んで鋭角三角形を作る作り方は何通りか求める問題.

解法

直角 or 鈍角三角形を数える.
それは,1つの頂点を決めると,残りの2つの頂点は,自分のarg - 180度以上,自分のarg未満の角度の点から2点選べば良い.
尺取メソッドでそのような範囲を辿って,組み合わせの数を求めていく.

UVa 12533 - Joining Couples (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12533

問題概要

Nノードの有向グラフを考える.(Nは10^5以下)
各ノードからはちょうど1つの枝が出ている.
Q個 (10^5) のクエリに答える問題.
各クエリは,ノードA, Bが与えられる.
各ターン,A, Bのどちらかが,枝にそって1個移動できる.
ノードが一致するまでの最小ターン数を求める.一致させられないならそれを指摘する.

解法

移動していくと,いずれループに陥る.ループは連結成分ごとに1つだけ(枝数の関係より).
そのため,同じ連結成分であれば必ず一致できる.
どのノードがループの一員かを調べておいて,ループ内のノードは順番に番号をつけておく.
ループのサイズと,ループ内のノードの番号から,ループの中では最小ターンがO(1)で求められる.
ループをルートとする木を考えて,ループに辿り着くまでの枝数と,ループに辿り着くノードの番号を計算する.
後は,LCAをdoubling等でO(log N)やO(1)求められるようにしておく.
すると,お互いLCAに移動するのが最小ターン数になる(距離はループに辿り着くまでの枝数から計算できる)し,
LCAがルートの場合,ループ内での最小距離も使えば求まる.

UVa 12532 - Interval Product (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12532

問題概要

N要素 (100000以下) の整数列Aが与えられる.各要素は-100以上100以下.
K個 (100000以下) のクエリに答える問題.各クエリは以下の2種類のうちのどちらか.
 C i v : A[i]をvに変更する
 P i j : A[i]*A[i+1]*...*A[j]が正か負か0かを求める

解法

Fenwick Treeを2つ使って,各区間の0の数,負の数の数を覚えておく.

UVa 12531 - Hours and Minutes (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12531

問題概要

アナログ時計を考える.
短針は12分毎に1回,1/60だけ回転する.
長針は1分毎に1回,1/60だけ回転する.
最初は一致していて,同時に動いた直後.
A度は短針と長針とのなす角としてありうるかどうかを判定する問題.
Aは0以上180以下.

解法

1/60ずつしか回転しないので,6の倍数でなければならない.
逆に6の倍数なら,そのような角になる時間が存在する.

UVa 12530 - Game of Tiles (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12530

問題概要

50*50以下のグリッドが与えられる.
幾つかのセルは黒く塗りつぶされていて,他のセルは白い.
2人でゲームを行う.順番に行動する.行動できなくなったら負け.先手必勝か後手必勝かを判定する問題.
 前回黒く塗ったセルの上下左右の白いセルを1つ選び黒く塗る.
 最初はどの白いセルを選んで黒く塗っても良い.

解法

各白いセルをノードと見なして,上下左右の白いセルに枝をはる.
そのようなグラフにおいて,完全マッチングが存在すれば後手必勝.
なぜなら,後手は,マッチングにそって動かせばいつでも動ける.
そうでなければ,先手必勝.最大マッチングに含まれない白いマスを最初に選んで,後は後手必勝の後手のように動けば良い.
二部グラフなので,完全マッチングが存在するかどうかは最大流などで求められる.

UVa 12529 - Fix the Pond (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12529

問題概要

2N*(2N+1)のグリッドを考える.(Nは300以下)
座標(x,y), (x+y)%2=0 に縦または横に壁がある.(問題文参照)
それを縦・横をいくつか切り替えて,すべてのセル間を移動可能にしたい.
最小でいくつ切り替えればよいか求める問題.

解法

1つ切り替えるごとに連結成分を1つ減らせるので,連結成分の数-1が答え.
DFSなどで塗りつぶしながら連結成分の数を数える.Union Findなどを使っても良い.

UVa 12528 - Environment Protection (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12528

問題概要

xが0以上W以下,yが-D以上0以下の領域を考える.
有理関数y1とy2が与えられる.分子分母の次数はそれぞれ8以下.
xが0以上W以下のとき,それぞれの有理関数は,
 分母は0にならない
 y1(x)はy2(x)より大きい
 y1(x), y2(x)は-Dより大きくて,0より小さい
を満たす.(つまり考えている領域を左から右に突き抜けて,お互い交わらない)
有理関数で囲まれている場所のうち,-dより大きい部分の面積がちょうどAになるようにしたい.
dを求める問題.存在することは保証されている.

解法

2分探索+数値積分.
数値積分は,台形公式とかでも十分.
出力は小数点以下5桁だが,正しく四捨五入するために,もうちょっと精度良く求めなければならない.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。