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

続きを読む

Round #219 DIV1 C問題/DIV2 E問題 - Watching Fireworks is Fun (この記事を編集する[管理者用])

Source

Codeforces Round #219 DIV1 C問題 (1500pt)
Codeforces Round #219 DIV2 E問題 (2500pt)
Problem description

問題概要

一直線上に $N$ 個の区画($1,2,\ldots,N$)があり,隣り合う各区画間の距離は $1$ である.
$M$ 回だけ花火が上がる.
$k$ 回目の花火が上がる場所は $A_k$ で,時刻は $T_k$ である.
その花火が上がった時に区画 $x$ にいたなら $B_k - |A_k - x|$ だけ満足度が得られる.(負もありうる)
単位時間あたり $D$ だけ移動できるとして,得られる満足度の和の最大値を求める問題.
ただし,花火の上がる時間には,区画のどこかにいなければいけない.また,花火は同時に複数上がる場合がある.
$1 \leq N \leq 150000\ (1.5 \times 10^5)$
$1 \leq M \leq 300$
$1 \leq D \leq N$
$1 \leq A_k \leq N$
$1 \leq B_k \leq 10^9$
$1 \leq T_1 \leq T_2 \leq \cdots \leq T_M \leq 10^9$

解法

DPする.状態は 最後に上がった花火と最後に花火を見た場所 にして それまでの満足度の最大値 を計算する.
その際,状態を更新するのにある区間にある最大値というのが必要になる.
スライド最小値や,Range Minimum Queryを使う.

C言語のスパゲッティなコード

続きを読む

Round #219 DIV1 B問題/DIV2 D問題 - Counting Rectangles is Fun (この記事を編集する[管理者用])

Source

Codeforces Round #219 DIV1 B問題 (1000pt)
Codeforces Round #219 DIV2 D問題 (2000pt)
Problem description

問題概要

$N \times M$ のサイズのグリッドが与えられる.それぞれのセルには $0$ か $1$ が書かれている.
$Q$ 個のクエリが与えられる.
各クエリでは,長方形領域が与えられるので
 その長方形領域に含まれる長方形領域の中で,セルが全部 $0$ となるようなものの数
を求める.
$1 \leq N, M \leq 40$
$1 \leq Q \leq 3 \times 10^5$

解法

クエリの数を考えると最悪ケースでほぼすべてのパターンのクエリが来うるので,最初に全部の長方形領域に対して答えを計算しておく.
まず,ある場所より左上にある $0$ の数とか,そういうのは,縦に横に累積和を取ったり,包除原理を用いたりで $O(\mbox{セルの数})$ 計算できる.
全部 $0$ となるような長方形のうち,左上の場所 $(r_1, c_1)$ を決めつける.
右下の座標としてvalidがどうかを判定する.それは,左上に $1$ がある場所の数が $0$ 個であれば良い.
次に,ある座標 $(r_2, c_2)$ より左上に右下とvalidな座標の数を同様の方法により数える.
後は,その数を,左上 $(r,c)$,$(r \leq r_1,\ c \leq c_1)$,右下 $(r_2,c_2)$ に対応するクエリの答えに足していく.
$O(N^3 M^3)$.
他にもいろいろな方法があるらしい.

C言語のスパゲッティなコード

続きを読む

Round #219 DIV1 A問題/DIV2 C問題 - Counting Kangaroos is Fun (この記事を編集する[管理者用])

Source

Codeforces Round #219 DIV1 A問題 (500pt)
Codeforces Round #219 DIV2 C問題 (1500pt)
Problem description

問題概要

$N$ 匹のカンガルーがいて,$k$ 番目のカンガルーの大きさは $S_k$.
それぞれのカンガルーは $1$ 匹まで他のカンガルーを自分の袋の中に入れることができる.
ただし,袋に入れることができるのは,自分の半分の大きさ以下のカンガルーのみで,袋の中に入ったカンガルーは袋の中にカンガルーを入れていてはいけない.
袋の中に入っていないカンガルーの数の最小値を求める問題.
$1 \leq N \leq 5 \times 10^5$
$1 \leq S_k \leq 10^5$

解法

袋の中に入るカンガルーの数を最大化する.
答えを決めつけると,袋を提供するカンガルーはできるだけ大きいものを,袋に入るカンガルーはできるだけ小さいものを選べば良い.
よって,二分探索で答えを決めつけると,greedyにそれより大きいかどうかが判定できる.(以下のコード1)
また,袋の中に入るカンガルーは最大 $N/2$ 匹程度で,小さい方から半分は袋に入る側,大きい方から半分は袋を提供する側と分類してgreedyにマッチングしていっても良い.(以下のコード2)

C言語のスパゲッティなコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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