Entries

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

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

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

Source

TopCoder SRM598 DIV1 HARD (950pt)
Problem Statement

問題概要

$N$ ノードの木が与えられる.
測定装置を $k$ 個のノードに置く.
各ノードに対して,測定装置からの距離の組を考え,それが各ノードについて異なるようにしたい.(測定結果からどのノードが判断できるようにしたい)
最小の $k$ を求める問題.

解法

まず,$N=1$ なら $k=0$ で良いので,例外処理しておく.
そうでなければ,$1$ 個は測定装置を置かなくてはいけないので,$1$ 個置く場所を全探索して,固定して考える.
測定装置をとりあえずおいたノードを根とした根付き木で考える.
各ノードについて,自分の子供が $2$ つ以上あるなら,それを区別するために,子供からなる部分木のうち,1個を除いて全てのものに測定装置がなければならない.
よって,測定装置を置かなければいけないノードは,子供の方から再帰的にgreedyに求めることができる.

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

続きを読む

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

Source

TopCoder SRM598 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

2人でゲームを行う.最適に行動した時,先手必勝か後手必勝か,永遠に決着がつかないかを判定する問題.
無限に長い一直線上で戦う.
最初,座標 $0$ に先手が,座標 $d$ に後手がいる.
先手の移動力は $M_1$,射程は $R_1$,後手の移動力は $M_2$,射程は $R_2$ である.
各ターン,
 移動力以下だけ離れた場所に移動し,相手キャラまでの距離が射程以下だと勝ち
ということを繰り返す.

解法

$1$ ターン目で先手が勝つ,$2$ ターン目で後手が勝つは,判定しておく.
$2$ ターン目までで決着がつかないなら,移動力が高い方しか勝つ可能性はない.勝てないなら逃げられるから.
移動力が高い方は,好きなように相手との距離を詰めることができる.
近づきすぎると負けるので,相手の移動力 $+$ 射程より $1$ だけ離れた場所に行き,相手が全力で離れた後,$1$ ターンでトドメがさせるかどうかを判定すれば良い.
それができないなら,引き分け.

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

続きを読む

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

Source

TopCoder SRM598 DIV1 EASY (250pt)
Problem Statement

問題概要

$N$ 個のアイテムがあり,$k$ 番目のアイテムの重さは $W_k$ である.
$1$ 個のビンには合計で重さ $300$ までのアイテムを入れることができる.
全てのアイテムを入れるためのビンの数の最小値を求める問題.
$1 \leq N \leq 50$
$100 \leq W_k \leq 300$

解法

まず,重さ $100$ のアイテム以外は高々 $2$ 個までしか同じ瓶に入れることができない.
よって,重さ $100$ のアイテムをどれだけ同じビンに $3$ つ詰め込むかを全探索して,残りはgreedyに詰め込めば良い.(以下の解答)
また,重さ $200$ のアイテムは重さ $100$ のアイテムと一緒に詰め込むほうが良いので,各ビンに対して重いアイテムから詰め込めるだけつめ込むというgreedyでも良い.

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

続きを読む

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

Source

TopCoder SRM564 DIV1 HARD (850pt)
Problem Statement

問題概要

m要素 (50以下) の正整数列Aと正整数Nが与えられるので,以下の条件を満たす非負整数列Xは何個存在するかをmod 1000000007で求める問題.
 X[1] XOR X[2] XOR ... XOR X[m] = N (XORはビットごとにXOR)
 0 ≤ X[k] ≤ A[k]
各整数は10^9以下.

解法

一番大きいXの要素の最上位ビットを使うかどうかで場合分けをする.
最上位ビットを使う場合は,そのビットと,Nの対応するビットを反転させて1つ合計ビットの少ない問題に帰着される.
最上位ビットを使わない場合は,その要素は,最上位ビット以外は自由に設定できる.
ので,他要素のXORの最上位ビットがNと一致していれば,後はその要素で調整できる.
なので,最上位ビットだけを状態としてDPして数えれば良い.
小さい状態に帰着していって,すべてのビットがなくなった場合,N=0のときのみ1つ答えがあるのを忘れないこと.(忘れてしまった)

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

続きを読む

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

Source

TopCoder SRM564 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N個 (100000以下) のボールがあって,それぞれ赤・緑・青のどれかの色をしている.
 赤いボールがあれば赤いボールを1個捨てる
 緑色のボールがあれば緑色のボールを1個捨てる
 青いボールがあれば青いボールを1個捨てる
 以下繰り返し
としたとき,K番目に捨てられたボールが赤であった.
赤・緑・青のボールの数の分布としてありうるのは何通りあるかを求める問題.

解法

今何個目のボールを捨てたか,残ってるボールの種類はどれかを状態としてDPする.
O(色の種類 * N),または,O(2^色の種類数 * N).

本番では,K番目のボールが捨てられた時,残っているボールの種類数が1種類,2種類,3種類で場合分けした.
1種類,2種類の場合は,なくなったボールの種類が使われた個数でループを回して数えた.O(N).
がすぐO(1)にすることもできる.

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

続きを読む

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

Source

TopCoder SRM564 DIV1 EASY (250pt)
Problem Statement

問題概要

W*H (45000*45000以下) のチェス盤を考える.
ナイトを好きなセルにおいて,自由にナイトの動きにそって動かして,元のセルに戻ってくる.
同じセル(最初のセルを含む)を何回訪れても良い.
訪れた(異なる)セルの数の最大値を求める問題.

解法

手を動かして規則を探す.
min(W, H) = 1なら1セルのみ.
min(W, H) = 2なら,(max(W, H) + 1) / 2セル.
W = H = 3なら8セル.(中央以外)
それ以外なら全部のセルを訪れることができる.

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

続きを読む

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

Source

TopCoder SRM586 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$K$ 個の国がある.($K \leq 26$)
各国は1年は同じ長さで,同じタイミングに都市が始まるが,基準となる年が異なる.(A国の第71年目はB国の第91年目かもしれない)
各国は,それぞれ10人以下の王様がいて,王様の任期はある年の始まりから,ある年の終わりまで.
王様の任期が何年に始まって,何年に終わったかというリストが,その国の年の数え方で与えられる.
過去戦争が起こった記録が,どの国のどの王様と,どの国のどの王様とが戦ったか,という記録のリストが与えられる.
戦争は,1年以内に終わり,年をまたぐことはない.
クエリが50個以下与えられるので,それぞれのクエリに答える問題.
各クエリでは,異なる国の王様の名前が2つ与えられるので,その2つ王様が同時に王様になっていた時期がある可能性があるかどうかを求める.

解法

各国同士の年の数え方がどのぐらいずれている可能性があるか,その最大値と最小値を更新していく.
それは,最短路問題に帰着されるので,ワーシャルフロイドなどで計算できる.
あとは,各クエリに答えるだけ.

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

続きを読む

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

Source

TopCoder SRM586 DIV1 EASY (250pt)
Problem Statement

問題概要

関数 $y = f(x)$ は定義域 $[1, n]$ の区分線形関数.$2 \leq n \leq 50$.
$x$が整数の時 の$f(x)$ の値が整数で与えられ,その間は線分で繋いだものが $f(x)$ となる.
$f(x)$ の値は,$-10^9$ 以上 $10^9$ 以下.
$y$ を何か定数とした時,$y = f(x)$ を $x$ についての方程式と思った時の解の個数の最大値を求める問題.
有限でないならそれを指摘する.

解法

$f(x) = f(x+1)$ となる整数 $x$ があれば,答えは無限.
$y$ の値を端点の周辺のみ調べれば良い.(ただし,$y$ の値は整数だけに限定してはいけない)
$y$ を固定した時,$y = f(x)$ の解の個数は,各折れ線と交わるかを端に注意しながら1つずつ判定していけば良い.(これはDIV2 MEDIUMの問題)
以下のコードでは,値が大きいので無駄に座標圧縮して$y$の値を全部調べた.

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

続きを読む

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

Source

TopCoder SRM599 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

各頂点が格子上の単純な多角形のうち,周の長さが $L$ (整数)のもので,
 (1) 頂点数が最も小さいもの
 (2) その中で,最も長い辺と最も短い辺の長さの差が最も小さいもの
を考える.
最も長い辺と最も短い辺の長さの差を求める問題.
ただし,そのような多角形が存在しないならそれを指摘する.
$1 \leq L \leq 5000$

解法

まず,$L$ が奇数ならそのような多角形は存在しない.
なぜなら, $a^2 + b^2 = c^2$ を満たす整数 $a,b,c$ を考えると,奇数の数は $0$ か $2$ 個であるから,一周回って戻ってきて,周長が奇数になることはない.
また,$L \geq 4$ かつ $L$ が偶数なら,四角形は作れて,$L$ が $4$ の倍数なら正方形,そうでないなら,縦の長さが $1$ だけ長い長方形が作れる.
よって,三角形が作れるかどうかを探索し,最も長い辺と短い辺の長さの差が小さい三角形を見つける問題になる.
そこそこうまく探索すると間に合う.
$L$ が $5000$ 通りしかないので,間に合わない場合は,答えを埋め込んでも良い.

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

続きを読む

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

Source

TopCoder SRM599 DIV1 EASY (250pt)
Problem Statement

問題概要

$X=1$ から初めて毎ターン以下のどちらか操作を行う.
 素数 $p$ を $X$ にかける
 $X$ の約数を $X$ にかける
$X=A^B$ となるまでの最小ターン数を求める問題.
$2 \leq A \leq 10^6$
$1 \leq B \leq 10^6$

解法

まず,$A$ の素因数は全部操作1で加えておく.
後は,それぞれの素因数は毎回倍々にできる(端数は適当に調整できる)ので,操作2の回数は最も多い素因数に依存する.
操作1の回数,操作2の回数は愚直に調べれば良い.

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

続きを読む

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

Source

TopCoder SRM597 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

頂点数 $N\ (3 \leq N \leq 50)$ の凸多角形が与えられる.(頂点が反時計回りに与えられる)
各頂点の座標は整数で,絶対値は$10^5$以下.
任意の $3$ 頂点は一直線上にはない.
$2$ 人でゲームをする.行動できなくなったほうが負け.先手必勝か後手必勝かを判定する問題.
各ターンでは,以下の様な凸多角形を作り,次のターンには与えられた凸多角形の代わりにする.
 各頂点は格子点で,与えられた凸多角形の内部,および,周上にある
 各頂点は,与えられた凸多角形の頂点と異なる
 任意の $3$ 頂点は一直線上にない

解法

与えられた多角形の内部に,三角形が作れれば先手の勝ち,そうでなければ後手の勝ち.
なぜなら,後手が打つ手があるなら,その手を先手が打てば良い.(というのを再帰的に繰り返すと後手が打つ手が無い三角形を書ける)
したがって,多角形の内部,および,周上に,一直線上にない $3$ 点が取れるかどうかを判定する問題になる.
基本的には,内部および周上の点を全部列挙して,それらが全て一直線上にあるのかどうかを判定すれば良い.
それは,$x$ 座標を $-10^5$ から $10^5$ まで全部試して,内部の点の $y$ 座標の最大値と最小値を求めれば良い.
ただし,全列挙すると数が多すぎるので,一直線上にあるなら内部の点は高々 $2 \times 10^5$ ぐらいなので,それを超えたらやめるか,
各 $x$ 座標について,数点のみを列挙するなどして適当に端折る必要がある.

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

続きを読む

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

Source

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

問題概要

アルファベッド大文字からなる文字列 $A$ と $B$ が与えられる.
1回の操作で,文字列 $A$ から任意の1文字を取り出し,$A$ の先頭にくっつけることができる.
最小で何回の操作で $A = B$ とできるかを求める問題.
不可能ならそれを指摘する.
$1 \leq |A| = |B| \leq 50$

解法

$A$ と $B$ で含まれる個数が違う文字があれば不可能.
$B$ の後ろから $k$ 文字が $A$ の部分列(部分文字列ではない)ならば,$|A| - k$ 回で可能.
そのような $k$ の最大値を全探索で探す.
部分列になっているかどうかは $B$ の後ろの $k$ 文字をgreedyに $A$ の文字と対応させていってチェックする.

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

続きを読む

SRM306 DIV2 HARD - BlockDistance (この記事を編集する[管理者用])

Source

TopCoder SRM306 DIV2 HARD (1000pt)
Problem Statement

問題概要

1000文字以下の文字列A, Bが与えられる.
1回の操作では以下のことができる.
 Aの好きな場所に,好きな文字列(何文字でも良い)を挿入する
AをBに一致させるために必要な最小手順数を求める問題.
不可能ならそれを指摘する.

解法

DPする.状態は
 dp[a][b][fg] = Aの最初a文字,Bの最初b文字,だけが入力の時の答え
 ただし,fg=1のときは,Aの最後に何かを挿入している(次にAの最後に挿入するときにコストが掛からない)
とする.

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

続きを読む

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

Source

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

問題概要

要素数50以下の配列aが与えられる.
各要素は-1000以上1000以下の整数で,すべて異なる.
1回の操作では,以下のどちらかのことができる.
 1つの要素を取り出して,一番最初に付け加える
 1つの要素を取り出して,一番後ろに付け加える
昇順にソートするのに必要な最小手順数を求める問題.

解法

1つ目の操作をK回,2つ目の操作をL回行うというのは,小さい方からK個,大きい順からL個の要素を無視するというのと同じ.
(取り出す順番を考えれば,必ずソートされている順番にできる)
L, Kを全部試して,残りの部分がソートされているかどうかを調べれば良い.
DIV2 EASYが類題.

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

続きを読む

SRM306 DIV2 EASY - SortMachine (この記事を編集する[管理者用])

Source

TopCoder SRM306 DIV2 EASY (250pt)
Problem Statement

問題概要

要素数50以下の配列aが与えられる.
各要素は-1000以上1000以下の整数で,すべて異なる.
1回の操作では,以下のことができる.
 1つの要素を取り出して,一番後ろに付け加える
昇順にソートするのに必要な最小手順数を求める問題.

解法

K回操作を行うというのは,大きい順からK個の要素を無視するというのと同じ.
(取り出す順番を考えれば,必ずソートされている順番にできる)
Kを0から増やしつつ,残りの部分がソートされているかどうかを調べれば良い.
DIV1 EASY/DIV2 MEDIUMが類題.(以下のコードはそのコードから1行コメントアウトしただけ)

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

続きを読む

SRM300 DIV2 HARD - CircleOrder (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 HARD (1000pt)
Problem Statement

問題概要

円の形をした道路がある.
その上に,$25$台以下の車(アルファベット小文字)と,それぞれの車の目的地(対応するアルファベット大文字)が与えられる.
車は$1$台ずつ動かし,途中で立ち止まらず,目的場所に移動する.
車はすれ違うことはできない.
どの順番で動かせば,全ての車が目的地に辿り着けるか,その順番の中で辞書順最小のものを求める問題.
不可能であるなら,それを指摘する.

解法

まず,全ての車が目的地に辿り着ける必要条件(必要十分ではない!)は
 与えられた文字列から小文字だけ抜き出した文字列を$S$
 与えられた文字列から大文字だけ抜き出した文字列を$T$
としたとき,$S$か$T$を適当に回転(頭から数文字をお尻にくっつける)したとき一致すること.
このときだけ考えると,車はすれ違わないので,どの車から動かしても,他の車が目的地に辿りつけなくなるようなことはない.
(逆に,ある車が目的地にたどり着いた後でないと,動かせない車はある)
なので,greedyに動かせる車のうち,アルファベット順で最も早い車から動かしていって,最終的に全部の車が辿り着けるかどうか調べれば良い.

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

続きを読む

SRM300 DIV2 EASY - Taxi (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 EASY (250pt)
Problem Statement

問題概要

2点間$(x_1, y_1)$と$(x_2, y_2)$との距離を2種類定義する:
 マンハッタン距離 $|x_1 - x_2| + |y_1 - y_2|$
 ユークリッド距離 $\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }$
${\rm maxX}, {\rm maxY}, {\rm taxiDist} \leq 1000000$が与えられる.
3条件
 (1) $0 \leq x_1, x_2 \leq {\rm maxX}$
 (2) $0 \leq y_1, y_2 \leq {\rm maxY}$
 (3) $(x_1, y_1)$と$(x_2, y_2)$とのマンハッタン距離が${\rm taxiDist}$
を満たすとき,$(x_1, y_1)$と$(x_2, y_2)$とのユークリッド距離の最大値はいくらか求める問題.
3条件を満たす2点$(x_1, y_1)$と$(x_2, y_2)$が存在しないときはそれを指摘する.

解法

$x_1 \leq x_2,\; y_1 \leq y_2$としてしまって良い.
最初の2条件は$d_x = x_2 - x_1 \leq {\rm maxX}, \; d_y = y_2 - y_1 \leq {\rm maxY}$となる.
$d_x$を決め打てば,$d_y = {\rm taxiDist} - d_x$で求まるので,$d_x$を(整数の範囲で)全探索する.
もしくは,できるだけ長細い($d_x$が最大,または,$d_y$が最大)の時が答えになるので,それを場合分けして求める.

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

続きを読む

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++によるスパゲッティなソースコード

続きを読む

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

Source

TopCoder SRM560 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

最初,2次元平面上の幾つかの整数座標に点がある.
毎ターン以下の操作を行う.
 (x+0.5, y+0.5), (x+0.5, y-0.5), (x-0.5, y+0.5), (x-0.5, y-0.5) に点があるなら,(x, y)に点を追加する(すべてのx,yについて)
 そして,前のターンにあった点を全部消す
そのような操作を経て,何ターンか後の点の配置が(相対座標で)与えられる.(つまり,座標は平行移動しているかもしれない)
それは,最大で何ターン経過しているかを求める問題.
与えられる点の数は1以上50以下で,点の相対座標の絶対値は70以下の整数からなる.

解法

答えに対する2分探索をする.
kターン経過後に,与えられた配置にできるかどうかを判定するのは,
初期配置になくてはならない点はすぐに求まり,それのみからkターンだけシミュレーションして,
与えられた点のみ残れば,kターン後にそのような配置になれる.

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

続きを読む

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

Source

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

問題概要

ケータイの文字入力.
文字の種類は50種類以下あって,それぞれの出現回数 (各1000回以下) が与えられる.
キーの数は50種類以下あって,それぞれのキーに割り当てられる最大文字数が与えられる.
各キーには,それぞれ1回押すと出てくる文字,2回押すと出てくる文字,…を割り当てることができる.
割り当てを自由にしてよいので,文字を全部入力するのに,必要なキーを押す回数の最小値を求める問題.
割り当て不可能ならそれを指摘する.

解法

出現頻度の高い順に,押すキー回数の小さいほうから割り当てる.

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

続きを読む

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

Source

TopCoder SRM559 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

ノード数n (50以下) のツリーが与えられる.
ノード番号 (1~n) を付け替えて,以下の条件を満たす2分木にする方法の数を求める問題.
 ノード番号kの左の子ノードは2k (2kがnより大きいなら存在しない)
 ノード番号kの右の子ノードは2k+1 (2k+1がnより大きいなら存在しない)
つまり,2分木で,上に詰まってて,一番下の段は左に詰まってるような解釈の仕方のパターン数を求める問題.

解法

どのノードを根にするかは全部試す.
後は,残りノード数から,それぞれの子供の木がどうなるべきかは再帰的に決まるので,条件をみたすようにできるかどうか調べる.

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

続きを読む

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

Source

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

問題概要

R*Cのチェス盤を考える.(R, Cは10^9以下)
ハイパーナイトというコマは,
 上下のどちらかにaだけ,左右のどちらかにbだけ動く
 上下のどちらかにbだけ,左右のどちらかにaだけ動く
という8通りの動き方ができる.
ただし,盤面の外へは移動できない.
そこから1ターンでk通りの移動できるマスは何個あるかを求める問題.
aとbは等しくない.
2*max(a,b)はmin(R,C)より小さい.

解法

どの移動ができるかどうかで,盤面は25通りの場所に分類される.
それぞれ何通り移動できるか,それに含まれるマスの数はいくつかを調べる.

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

続きを読む

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

Source

TopCoder SRM558 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

x軸上にR個の赤い点,x軸より上にB個の青い点が与えられる.(R, Bは300以下)
問題文の図のように,赤い点を2個,青い点を2個選んで,きつね耳のような形にする方法は何通りあるか求める問題.
条件は,内側の三角形は,外側にふれてはならず,それぞれの三角形について,青い点は赤い2点の中になければいけないなど.
座標は正整数で10000以下.

解法

青い2点の選び方は全部試す.
すると,2点を結ぶ直線とx軸の交点,および,2点のx座標を境目に,赤い点がどの三角形にしようできるかが決まる.
あとは適当にそれぞれに使用出来る赤い点の数を数えて,組み合わせの数を足していく.
赤い点を愚直に数えてO(B^2 R),赤い点を累積和とか用意しておけばO(B^2 + R + 座標の最大値).

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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