Entries

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

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

SRM563 DIV2 MEDIUM - CoinsGameEasy (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

20*20以下のグリッドが与えられる.各セルは空かコインか障害物がおいてある.
コインの数はちょうど2個.
グリッドを上下左右に一瞬傾けるという操作を行うことができる.そうすると,
 すべてのコインが傾けた向きに1だけ移動する
 ただし,移動先が障害物なら現在の位置に残る
 また,移動先がグリッドの外ならグリッドから落ちてコインがなくなる
いくらか操作した後,1枚のコインが落ちて,1枚のコインがグリッドに残ってなければいけない.
そういう操作の回数の最小値を求める問題.操作の回数が11以上必要,もしくは,不可能なら-1を返す.

解法

各コインがどこにあるかを状態としてBFSする.
4^10通り全部動かし方を試しても良い.

C++によるスパゲッティなソースコード

続きを読む

SRM563 DIV1 HARD - CoinsGame (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV1 HARD (950pt)
Problem Statement

問題概要

40*40以下のグリッドが与えられる.各セルは空か障害物がおいてある.
空のセルにはコインを置くことができる.
その後,グリッドを上下左右に一瞬傾けるという操作を何回でも行うことができる.そうすると,
 すべてのコインが傾けた向きに1だけ移動する
 ただし,移動先が障害物なら現在の位置に残る
 また,移動先がグリッドの外ならグリッドから落ちてコインがなくなる
いくらか操作した後,1枚以上のコインが落ちて,1枚以上のコインがグリッドに残ってなければいけない.
それが可能なコインの置き方は何通りあるかをmod 1000000009で求める問題.

解法

全部の置き方から,置いたコインが全部同時に落ちるしかないという場合の数を引く.
それは,それぞれの空のセルをグループに分ければ良い.
各グループは,どんな操作の連続でも,同じタイミングに落ちる.(もしくは落ちれない)
グループ分けには,ハッシュを使った.
最初全部のセルのハッシュ値を0,グリッドの外のハッシュ値を1として,
グリッドの面積回ぐらい,各セルについて
 上下左右に傾けた時に移動する場所4箇所のハッシュを使って,新しいハッシュ値に置き換える
という操作を同時に行う.
すると,どうやっても同時に落ちる場所のみが同じハッシュ値になる.

C++によるスパゲッティなソースコード

続きを読む

SRM563 DIV1 MEDIUM - SpellCards (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

スペルカードがN個 (50以下) 与えられる.一列に並んでいる.
カードにはそれぞれレベルLとダメージDが設定されている.
カードを使うときは一番左のカードを使わなければならない.
カードを使うには,そのカードを含め,左からL枚だけ捨てれば使える.
使うとDだけダメージを与えられる.
また,いつでも,何回でも,カードは一番左のカードを一番右に移動させることもできる.
最終的に与えられるダメージの合計値の最大値を求める問題.

解法

いつでも自由に左のカードを一番右に移動できるので,いつでもどのカードでも使えて,そのカードからL枚だけ捨てれば使えると考えることができる.
と思うと,使うカードのレベルの和がN以下なら任意のカードの集合を使うことができる.証明は簡単.
すると,典型的なナップサック問題になるので,DPすれば良い.

本番では,回転の仕方は全部試して,右から使っていくというDPを行った.(未使用のカードの枚数も状態として持つ)

C++によるスパゲッティなソースコード

続きを読む

SRM563 DIV1 EASY - FoxAndHandle (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV1 EASY (300pt)
Problem Statement

問題概要

文字列AとBを混ぜて文字列Xを作るとは,
 Xの部分列(部分文字列ではない)としてAが存在して,その部分列を取り除いた文字列は(順番を入れ替えずに)Bに一致させることができる
50文字以下の文字列Sが与えられる.
Sにはアルファベット小文字しか含まず,各文字の種類について,含まれる数は偶数個.
Tと,Tの置換(なんでも良い)を混ぜるとSになるTのうち,辞書順最小のものを求める問題.

解法

Tの1文字目がaにできるかどうか,できなければbにできるかどうか,と判定していって辞書順最小のものを探す.
Tの1文字目がaにできるためには,Sの最初のaを探してそれを使うことにする.
最初のaより前の文字は,Tの置換にしか利用できず,それより後ろのはどちらにも利用できる.
それより後ろのを全部Tに利用したとして,Tに含まれるべき文字が全部含まれるかどうかをチェックする.
2文字目がaにできるかどうかを調べるときは,Sの最初のaを探していたところを,前回使った文字以降で最初のaを探すようにすれば良い.

以下のコードでは,使える文字の中で最小のものを探して,それを1文字目に使って,それに対応するTの置換のをどれにするか全部試した.
愚直に全部試すとTLEすると思うので,適当にメモ化した.
計算量見積もれないけど遅くない.

C++によるスパゲッティなソースコード

続きを読む

SRM562 DIV1 MEDIUM - CheckerFreeness (この記事を編集する[管理者用])

Source

TopCoder SRM562 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

2次元平面上に白い点が222個以下と黒い点が222個以下与えられる.
順番に白い点,黒い点,白い点,黒い点を結んで凸な四角形が作れるかどうかを判定する問題.
どの3点も同一直線上になく,2点の場所は一致しない.

解法

凸な四角形は対角線が交わるので,白い点を2個,黒い点を2個選んで,白い点から成る線分,黒い点から成る線分が交わることがあるかどうかを判定する問題になる.
白い点から成る凸包,黒い点から成る凸包を求める.
交わるなら,白い点か,黒い点か,どちらかは凸包の辺になることがわかる.
なぜなら,まず,凸包の辺が交わっている,凸包が共通部分を持たないなら自明.
残りは,片方の凸包が,もう片方の凸包の中にある場合だけ.この場合,交わるなら中の凸包の辺と必ず交わる.
仮に中にある凸包を白,外側にある凸包を黒とする.
白い凸包の中に黒い点があれば,その点から外側の点に線を引くと,白い凸包の辺と交わる.
そうでないなら,黒い2点は白い凸包の外であり,白い線分(白い凸包の中の線)と交わるなら,白い凸包の辺とも交わるのは絵を思い浮かべればわかると思う.

C++によるスパゲッティなソースコード

続きを読む

SRM562 DIV1 EASY - PastingPaintingDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM562 DIV1 EASY (250pt)
Problem Statement

問題概要

50*50以下グリッドのクリップボードに絵がコピーされている.
絵は各セルR,B,Gのどれかの色か,透明のどちらか.
無限に大きいビットマップに,T回 (10^9以下) だけその絵をコピーする.
k回目のコピーでは,左上の座標が(k, k)になる場所にコピーする.
コピーした時,色があるセルは上書き,透明なセルは変化なし.
最初全部のセルが白のとき,最終状態でビットマップに,R, G, Bそれぞれの色は何セルずつあるかを求める問題.

解法

50回ぐらいコピーしたら後は増分は一定になる.
なので増分を求めて一気に足してあげる.
それぞれのピクセルについて,左上に見ていって,何ターン上書きされないかを求めても良い.

C++によるスパゲッティなソースコード

続きを読む

SRM561 DIV1 MEDIUM - CirclesGame (この記事を編集する[管理者用])

Source

TopCoder SRM561 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

2次元平面上にn個 (50以下) の円が与えられる.
各円周は重なっていないが,ある円が別の円を包含しているかもしれない.
2人でゲームを行う.順番に行動して,行動できなくなったら負け.先手必勝か後手必勝かを判定する問題.
各ターンは以下の行動をする.
 内部に赤い点がない円を1つ選んで,その円の中の好きな(ただし他の円の円周は選ばない)1点を赤くする.

解法

Grundy数を計算する.
円をノードとみなして,中にある円(のうち,中にある円の中でないもの)を子供とみなして森を作る.
ある場所を赤い点で塗ると,該当するノードとその親,その親,…,その木のルートがなくなって,新しい木がいくつかできるような感じになる.
各ノードをルートとみなした時の部分木のGrundy数を全部計算すれば良い.

C++によるスパゲッティなソースコード

続きを読む

SRM561 DIV1 EASY/DIV2 MEDIUM - ICPCBalloons (この記事を編集する[管理者用])

Source

TopCoder SRM561 DIV1 EASY (250pt)
TopCoder SRM561 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

ACM/ICPCのために風船を準備する.
手持ちの風船が与えられる.手持ちの風船の色は50種類以下.
各色の風船の数 (100以下),その風船のサイズが与えられる.
風船のサイズはMとLの2種類のみで,同じ色の風船は全部同じサイズ.
ACM/ICPCはK個 (15以下) の問題から成る.
各問題iに対して,同じサイズで同じ色の風船をA[i]個 (100以下) 用意しなければいけない.
違う問題には,違う色の風船を割り当てないといけない.
風船は自由に色を塗り替えることができる.
色を塗り替える風船の数の最小値を求める問題.不可能ならそれを指摘する.

解法

各問題に対して,使う風船のサイズを全部試す.
後は,A[i]の大きい方から,greedyに手持ちの中から多い風船を割りあてて行けば良い.

C++によるスパゲッティなソースコード

続きを読む

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点選べば良い.
尺取メソッドでそのような範囲を辿って,組み合わせの数を求めていく.

Appendix

Recent Articles

ブログ内検索

Ads


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