Entries

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

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

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言語のスパゲッティなコード

続きを読む

Round #209 DIV2 E問題 - Neatness (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 E問題 (2500pt)
Problem description

問題概要

縦横 $n$ マスのグリッドが与えられる.
各セルは部屋で,合計 $n^2$ 個の部屋がある.
最初,各部屋が電気が付いているかどうかが与えられる.
また,最初にいる部屋の位置 $(x_0,\ y_0)$ が与えられる.
全ての部屋の電気を消した上で,最初いた部屋に戻る方法を $1$ つ求める問題.
手順数は最小である必要はないが,手順数は $3 \times 10^6$ 以下でなければならない.
できる手順は以下の通り:
 上下左右にずっと進んだ方向に,$1$ つ以上電気がついた部屋があるなら,上下左右に $1$ マス移動できる
 今いる部屋の電気をつける,もしくは,消す
なお,不可能ならそれを指摘する.

解法

DFSで行けるセルを全て巡る.
その際,初めてそのセルに到着した時に,電気がついていないなら電気をつけ,
最後にそのセルから立ち去るときに,電気を消していけば良い.
以下の解答では,$1$ 回目のDFSで電気をつけて回って,$2$ 回目のDFSで電気を消して回った.

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

続きを読む

Round #209 DIV2 D問題 - Pair of Numbers (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 D問題 (2500pt)
Problem description

問題概要

正整数の配列 $a_1,a_2,\ldots,a_n$ が与えられる.
以下の条件を満たす $(L,\ R)$ を全て列挙する問題.
 1. $a_L, a_{L+1}, \ldots, a_R$ が全て $a_j$ の倍数となるような $j$ が存在する ($1 \leq L \leq j \leq R \leq n$)
 2. 1.の条件を満たすもののうちで,$R-L$ が最大となる
$1 \leq n \leq 3 \times 10^5$
$1 \leq a_k \leq 10^6$

解法

色々な方法があると思う.
$a_j$ は $a_L, a_{L+1}, \ldots, a_R$ の中で最小の要素.
小さい順に $a_j$ を全て試し,全てが $a_j$の倍数となる最大の区間 $[L,\ R]$ を全部求めた.
ただし,一度でも区間 $[L,\ R]$ に含まれた要素は,$j$ として選ばないようにした.
他の方法としては,segment treeでgcdを管理して2分探索で $L, R$ を求める方法など.

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

続きを読む

Round #209 DIV2 C問題 - Prime Number (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 C問題 (1500pt)
Problem description

問題概要

 $\displaystyle \frac{1}{x^{a_1}} + \frac{1}{x^{a_2}} + \ldots + \frac{1}{x^{a_n}} = \frac{s}{t},\ t = x^{a_1+a_2+\cdots +a_n}$
と書いた時,$s/t$ をいくら約分できるか,つまり,${\rm gcd}(s,t)\ {\rm mod}\ (10^9+7)$ を求める問題.
$1 \leq n \leq 10^5$
$2 \leq x \leq 10^9$
$0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^9$

解法

普通に通分すると,分母は $x^{a_n}$ なので,とりあえずそれを基準に考える.($x^{a_1+a_2+\cdots+a_{n-1}}$ では取り敢えず約分できる)
後は,$a_n$ と等しい要素の数 $D$ が,$x$ の倍数なら,もう $1$ 回 $x$ で約分できる.
更に,その時,$D/x + (a_n - 1$と等しい要素の数$)$ が $x$ の倍数なら,更にもう $1$ 回 $x$ で約分できる.
というのを繰り返していく.

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

続きを読む

Round #209 DIV2 B問題 - Permutation (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 B問題 (1000pt)
Problem description

問題概要

要素数 $n$ の置換 $a$ で,
 $\displaystyle \sum_{i=1}^n \left| a_{2i-1} - a_{2i} \right| - \left| \sum_{i=1}^n (a_{2i-1} - a_{2i}) \right| = 2k$
となるものを $1$ つ求める問題.
$1 \leq n \leq 50000$
$0 \leq 2k \leq n$

解法

$2k \leq n$なので,適当に,どうやっても良い.
例えば,$a_1 = 1+k, a_2 = 1$ として残りは昇順にする.
または,$a_i = i$ としておいて,$k$ 箇所だけ $a_{2i-1}$ と $a_{2i}$ をスワップするなど.

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

続きを読む

Round #209 DIV2 A問題 - Table (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 A問題 (500pt)
Problem description

問題概要

縦 $n$ マス,横 $m$ マスのグリッドが与えられる.
各セルは $1$ か $0$ かが書かれている.ただし四隅のセルは全て $0$.
以下の手順を最小で何回繰り返せば,すべてのセルに色を塗ることができるかを求める問題.
 $1$ が書かれているセル $(x_1,\ y_1)$ と,四隅のうちの $1$ つのセル $(x_2,\ y_2)$ を選ぶ.
 その $2$ セルを対角線とする長方形の領域に色を塗る
 つまり,$(x,\ y)$ は $\min(x_1,x_2) \leq x \leq \max(x_1,x_2),\ \min(y_1,y_2) \leq y \leq \max(y_1,y_2)$ であれば色が塗られる.
同じセルに何回色を塗っても良い.
$3 \leq n,m \leq 50$
$1$ が書かれているセルが,少なくても $1$ つある

解法

上下左右の端に $1$ のセルがあれば $2$ 回で全部塗れる.
そうでなければ $4$ 回.

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

続きを読む

Round #208 DIV2 E問題 - Dima and Kicks (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 E問題 (3000pt)
Problem description

問題概要

縦 $n$ マス,横 $m$ マスのグリッドが与えられる.
一度でも訪れた部屋は $1$,訪れなかった部屋は $0$ で表される.
部屋は,上下左右につながっている.
以下の条件をみたすように移動する.
 $1$ 回の移動では,上下左右のどちらかの方向に必ず $k$ マスだけ進む.
 必ず $1$ 回以上移動している.
 $2$ つの部屋を繋ぐドアで $2$ 回以上通ったものはない.
考えうる $k$ を全て列挙する問題.不可能ならそれを指摘する.
$1 \leq n, m \leq 1000$

解法

全ての $k$ について条件をみたすか調べる.
一番左上の訪れたことがある部屋を起点として,$k$ マス飛ばしで見て,その間は通路だと思う.
通路が全部 $1$ になっていればそこは通ったということ.
部屋が全部連結で,奇数次数の部屋が $2$ 箇所以下なら一筆書きで移動できる.
余分な $1$ がないかは,部屋と通路で使った $1$ の数を数えればわかる.
後は,結構愚直に調べても大丈夫.

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

続きを読む

Round #208 DIV2 D問題 - Dima and Hares (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 D問題 (2000pt)
Problem description

問題概要

$1$ 番から $n$ 番のうさぎが一列に並んでいて,好きな順番に餌を $1$ 回ずつあげる.
うさぎ $k$ が餌をもらった時,両隣のうさぎですでに満腹なうさぎが
 $0$ 匹なら $a_k$ だけ
 $1$ 匹なら $b_k$ だけ
 $2$ 匹なら $c_k$ だけ
満足度が得られる.
最も左,最も右のうさぎの隣のうざぎがいない部分は空腹なうさぎとみなす.
満足度の和の最大値を求める問題.
$1 \leq n \leq 3000$
$1 \leq a_k, b_k, c_k \leq 10^5$

解法

最も左の,自分の左右より先に餌付けされるうさぎの場所で場合分けして,DPする.
ただし,一番左のうさぎは自分より右だけを見る.
選ばれたうさぎより左のうさぎは,右から順番に餌付けされることになる.
もしくは,左からどこまで見たか,最後に見たのうさぎは一つ右より先に餌付けされたかどうか,を状態にしてDPしても良い.

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

続きを読む

Round #208 DIV2 C問題 - Dima and Containers (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 C問題 (1500pt)
Problem description

問題概要

スタックとキューとデックが1個ずつあり,最初は全部空.
$n$ 回だけとある非負整数が与えられるので以下のようにする.
 与えられた非負整数 $a$ が $0$ なら,スタック,キュー,デックそれぞれ高々 $1$ 個の要素を取り除いて,取り除いた整数の和をスコアに加える.そして,スタック,キュー,デックを空にする.
 与えられた非負整数 $a$ が $0$ でないなら,スタック,キュー,デックのどれかに挿入する.
入れられる場所,取り出せる場所はそれぞれのデータ構造に依存する.
最大のスコアを得られる方法を $1$ つ求める問題.
$n \leq 10^5$
$0 \leq a \leq 10^5$

解法

色々方法はあるけど,一番簡単なのは,デックの片側に要らないものを全部押し付ける方法.
$a=0$ が来るまでの大きい方から $3$ つをスタック,キュー,デックのもう片側に $1$ 個ずつ入れておいて取り出せば良い.

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

続きを読む

Round #208 DIV2 B問題 - Dima and Text Messages (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 B問題 (1000pt)
Problem description

問題概要

$n$ 個のアルファベット小文字からなる単語 $w_1, w_2, \ldots, w_n$ が与えられる.
単語を順番につなげて,各単語の間と最初と最後に "<3" を挿入した後,更に何らかの文字をいくらか挿入した.
その結果が文字列 $S$ になったという.
矛盾していないか調べる問題.
$|w_1| + |w_2| + \cdots + |w_n| \leq 10^5$
$|S| \leq 10^5$

解法

"<3"を挿入した文字列を実際に作って,$S$ の部分列になっているかどうか調べる.

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

続きを読む

Round #208 DIV2 A問題 - Dima and Continuous Line (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 A問題 (500pt)
Problem description

問題概要

$n$ 個の異なる整数 $x_1,x_2,\ldots,x_n$ が与えられる.
$2$ 次元平面の $y \geq 0$ の部分に,$(x_i, 0)$ と $(x_{i+1}, 0)$ を直径とする半円を描く.
半円が($y > 0$ の部分で)交わるかどうかを判定する問題.
$n \leq 1000$
$-10^6 \leq x_k \leq 10^6$

解法

全ての半円の組に対して交わるかどうかを調べる.

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

続きを読む

Bayan 2012-2013 Elimination Round G問題 - Challenging Balloons (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round G問題 (ACM/ICPC形式)
Problem description

問題概要

以下の問題に対する解答プログラムが問題文に与えられている.
そのプログラムが間違った答えを返すケースを1つ出力する問題.

一直線上に,n個の風船を配置する.nは500以下.
各風船は地面に接するようにおき,各風船の中心のx座標は与えられている.
各風船の最大サイズも与えられる.
風船は接することはできても,重なることはできない.
各風船の半径の和の最大値を求める問題.

解法

jを300までしかチェックしてないのが問題.
 でかい風船,接しないように右に行くにつれて小さくなるように小さい風船たち,でかい風船
で,でかい風船が重なるようにすれば良い.

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

続きを読む

Bayan 2012-2013 Elimination Round E問題 - Flights (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round E問題 (ACM/ICPC形式)
Problem description

問題概要

ノード数n (1000以下),枝数m (5000以下) のDAGが与えられる.
各枝は必ず大きい番号のノードへ向かっている.( (i,j)ならjのほうが大きい )
枝の重みを1か2として,すべてのノード1からノードnへ移動するパスの重みを等しくしたい.
そのような重み付けを1つ求めるか,不可能であることを指摘する問題.
ノード1からノードnに移動するパスが1つはあることが保証されている.

解法

まず,ノード1から辿りつけないノード,ノードnに辿りつけないノードを重要でないノードと呼ぶ.
ノード1から任意の重要なノードjに移動するパスの重みはすべて等しくなければならない.
重要でないノードはどうでもいい.
枝の少なくても片方は重要でないノードは,重みはなんでも良い.以降無視する.
ノード1からノードjに移動するパスの重みの最小値と最大値をベルマン・フォードで更新していく.
途中で,最小値が最大値を上回れば,達成不可能.
そうでなければ,全部最小値(or 最大値)を採用したと思って,枝の重みを復元する.

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

続きを読む

Bayan 2012-2013 Elimination Round C問題 - Mirror Box (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round C問題 (ACM/ICPC形式)
Problem description

問題概要

高さ100cm,幅100000cmの長方形の箱の,上辺,下辺にいくつか鏡がついている.(問題文の図参照)
左側には高さh_l cmに,右側には高さh_r cmに穴が開いている.
左の穴から,レーザーを右の穴に向けて打つ.
その際,2回以上同じ鏡に反射してはいけない.
また,鏡に当たると,それぞれもらえるポイントが設定されている.
最高得点を求める問題.
鏡の数は最大で合計100個まで.

解法

最初に下に向けるか,上に向けるかというのと,跳ね返る回数を指定すれば,軌道は決まる.
跳ね返る回数は鏡の数以下なので,全通りシミュレーションできる.

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

続きを読む

Bayan 2012-2013 Elimination Round A問題 - Build String (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round A問題 (ACM/ICPC形式)
Problem description

問題概要

n個の都市が一直線上に並んでいる.左から番号1~n.nは1000以下.
車で,番号1の都市から,番号nの都市に移動したい.最短時間を求める問題.
各都市間の距離d[i]と,その都市ですぐ用意できる燃料s[i]が与えられる.
都市jについた時,その瞬間燃料s[j]だけもらえる.
また,都市についた後,時間kだけ待つたびに,燃料s[j]ずつもらうこともできる.(kは都市によらず一定)
最初は,都市1についたばかりで,燃焼s[1]だけもっている.
燃料タンクは無限に燃料が入る.
距離1移動するのに,燃料1消費する.

解法

とりあえず,移動出来るだけ移動しておいて,燃料が足りなくなったら,
今まで訪れた都市の中で,最もたくさん燃料が貰える場所でkだけ待ったことにする.

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

続きを読む

Round #147 DIV2 E問題 - Build String (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 E問題 (2500pt)
Problem description

問題概要

100文字以下のアルファベット小文字からのみなる文字列t, s[1], s[2], ..., s[n]が与えられる.nは100以下.
tの文字数だけ以下の操作を行う.
 i回目の操作では,tの1文字目の文字をs[1], s[2], ..., s[n]の中からどれか1文字取り出して,取り出した文字を消す
 その際に,s[k]から取り出したならkだけコストがかかる.
ただし,s[i]から取り出すことができる文字数は合計で最大a[i]文字まで.
操作を完了する最小コストを求める問題.操作を完了できないならそれを指摘する.

解法

最小費用流.
 ソース - アルファベット各文字 - 各文字列s - シンク
といった形のグラフ.(ノード数は1+26+n+1)
自分の解法では,無駄に各文字列sをアルファベットごとに分割してしまって無駄にノード数が多くなってしまっている.

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

続きを読む

Round #147 DIV2 D問題 - T-decomposition (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 D問題 (2000pt)
Problem description

問題概要

ノード数N (100000以下) の木sが与えられるので,以下の条件を満たす木tの中で,w(t)が最小となるtを1つ求める問題.
 tの各ノードは,sのノードの部分集合を表す.tの各ノードの重さをその部分集合の元の数とする
 w(t)はtに含まれるノードのうち,重さ最大のノードの重さ
 すべてのsの枝(a,b)について,aもbも含むような部分集合からなるノードがtになければいけない
 すべてのsのノードaについて,tのノードのうち対応する部分集合がaを含むものだけを取り出すと連結な木になっている

解法

絶対w(t)=2にすることができる.つまり,tのそれぞれノードは,sの枝に対応する.
tで枝をはれるのは,sの枝で端点を共有するようなものの間だけ使って,tを木にする.
なんでも良い.
自分の解法は,すこし勘違いしてたので,sの次数1のノードを根にして,sを根付き木にして,葉から順番になぞって,すべての枝に対して,その親側から更に根に遡る枝へとtで枝を張った.

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

続きを読む

Round #147 DIV2 C問題 - Primes on Interval (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 C問題 (1500pt)
Problem description

問題概要

正整数a, b, kが与えられる.bは10^6以下.
区間[a, b]の任意のL個の連続する整数は,少なくてもk個の素数を含む.
そのような最小のL (b-a+1以下) を求める問題.
存在しないならそれを指摘する.

解法

最初の数字を固定したら,k個先の素数の位置は単調増加なのでしゃくとりメソッドできて,それをやった.端に注意.
Lについて2分探索して,累積和を用いてある区間の素数の数をO(1)で求めれるようにしておくのがミスしなさそう.
答えは,範囲内の隣合う素数の差の最大値,区間の最初と最初の素数までの差,区間の最後と最後の素数までの差を使ってかけるので,それでも良い.

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

続きを読む

Round #147 DIV2 B問題 - Young Table (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 B問題 (1000pt)
Problem description

問題概要

簡単に言えば,任意の場所の数をスワップできるとして,標準ヤング盤にする手順を求める問題.
グリッドに数が書かれていて,n行あって,i行目はc[i]列だけある.(n, c[i]は50以下)
グリッドのマスの数をsとすると,グリッドには1~sまでの整数がちょうど1回ずつ登場する.
任意の異なる2マスをスワップするという操作を繰り返して以下を満たすようにしたい.
 任意の行について,右に行くにつれて単調に増加する
 任意の列について,下に行くにつれて単調に増加する
そのような方法を1つ出力する問題.
操作の回数は最小である必要はないが,sを超えてはいけない.

解法

row-major order(もしくはcolumn-major order)に1から順番に並べれば良い.
1マスずつ見ていって,そこに入れたい要素があるマスとスワップする.

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

続きを読む

Round #147 DIV2 A問題 - Free Cash (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 A問題 (500pt)
Problem description

問題概要

ある1日にN人 (10^5以下) の客が来ることがわかっている.
客が来る時間をhh時mm分の形で与えられる.
精算は一瞬で済み,商品を選ぶのにも時間がかからない.
ただし,レジが使えないと,その瞬間帰ってしまう.
最小で何個レジがあれば全部の客を捌けるかを求める問題.

解法

同じ時間にくる客の数の最大値を求めれば良い.
24*60ぐらいの配列を用意して,最初0にしておいて,来た時間に該当する場所に1を足していく.

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

続きを読む

Croc Champ 2012 Round 2 D問題 - Playing with Superglue (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 C問題 (2000pt)
Problem description

問題概要

n個 (2000以下) の文字列が与えられる.長さの合計は10^6以下.
その文字列をm個 (mは2000以下,同じのが複数回つながっている可能性がある) つなげた文字列をtとする.つなぎ方は与えられる.
また,2000文字以下の文字列sが与えられる.
tとsの最大部分列 (部分文字列ではない) の文字数を求める問題.
文字列は全てアルファベット小文字のみから成る.

解法

DP.
sを1文字ずつ見ていって,それまでの部分列の長さそれぞれに対して,その部分列のtの終点の最小値を覚えておく.
tの各場所に対して,次に文字cが現れる場所,というのを前計算しておいてすぐ求めれるようにしておく必要が有る.

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

続きを読む

Croc Champ 2012 Round 2 C問題 - Playing with Superglue (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 C問題 (1500pt)
Problem description

問題概要

2人でゲームを行う.先手必勝か後手必勝かを判定する問題.
n*m (100*100以下) の盤面の上に2つの駒がある.
2つの駒の初期座標が与えられる.最初駒の位置は異なり,盤面は糊が付着していない.
各ターン,以下のことを行う.
 先手は,糊付けされていない駒を1つ選び,上下左右のどこかに1マスだけ動かす.
 後手は,まだ糊が塗られていない,かつ,駒が存在しないマスを1マス選び,糊を塗る.
糊が塗られているマスに駒が移動すると,糊付けされて動けなくなる.
2つの駒が同じマスに存在する状況になったらその時点で先手の勝ち.
そうでなく,2つの駒が両方糊付けされて動けなくなったら後手の負け.
勝敗が決る前に両者ともvalidな行動ができなくなることはないことは少し考えればわかる.

解法

初期の駒のx座標の差と,y座標の差のみによってかわる.
後手は,厚さ2の壁を作れれば必勝で,それは,x座標の差とy座標の差のうち,どちらかか5以上ならできる.
そうでないときは,難しいが,パターンが少ないので,それぞれ実際に色々考えてみると,x座標差とy座標差の和が6以下なら先手が勝てることがわかる.

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

続きを読む

Croc Champ 2012 Round 2 B問題 - Word Cut (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 B問題 (1000pt)
Problem description

問題概要

長さNの文字列sとtが与えられる.(Nは1000以下) sを以下の操作をちょうどk回 (100000以下) 行なって,最終的にtに一致するのは何パターンあるかをmod 1000000007で求める問題.  s = xyと空でない文字列x,yに分解して,s=yxと置き直す.

解法

この操作1回分は,sの右から1文字以上N-1文字以下選び,それをsの左に移動させるというシフトを表す.
更にいうと,sの最も右の文字を左に移動させるという操作を1回~N-1回やったことに相当する.
なので,最終的に何文字分シフトされたかだけが重要で,更に,シフトされた文字数はmod Nで考えれば良い.
操作回数と何文字分シフトされたかmod Nを状態としてDPしてカウントすれば良く,愚直になるとO(Nk)だが早い言語で軽い処理をちゃんとかければ通るらしい.
実際には,何文字分シフトされたかmod Nは,1~N-1までは対称性より同じと見なせるので,O(k)でDPできる.

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

続きを読む

Croc Champ 2012 Round 2 A問題 - Trading Business (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 A問題 (500pt)
Problem description

問題概要

n個 (10以下) の惑星がある.
m個 (100以下) のアイテムがある.
それぞれの惑星で,それぞれのアイテムが,
 幾らで売られているか
 幾らで売れるか
 そのアイテム買うことのできる上限数(在庫数)
が与えられる.
宇宙船の容量kも与えられ,合計でk個のアイテムしか運べない.
初期資金は大量にあるとして,惑星をちょうど2個(1回ずつ)訪れるとき,儲けれる額の最大値を求める問題.

解法

訪れる惑星とその順番は全探索する.
どのアイテムを買うかは,売値と買値の差が大きい方からgreedyに買えば良い.
損をするものは買わない.

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

続きを読む

Round #115 E問題 - Power Defence (この記事を編集する[管理者用])

Source

RazMERiq 2012 E問題
Codeforces Round #115 E問題
Problem description

問題概要

タワーディフェンス系ゲーム.
敵が1匹,x軸を移動するので,与えることのできるダメージの最大値を求める問題.
タワーを建てれる場所は,y = -1, 1上の格子点のみで,同じ場所には2つ以上建てられない.
建てれるタワーの種類は以下3種類.
 タワー1,2 : 射程範囲内の敵に,毎秒いくらかのダメージを与える
 タワー3 : 射程範囲内の敵の移動スピードを遅くする
それぞれのタワーの種類に対して,射程範囲が与えられ,タワー1, 2に関しては攻撃力も与えられる.
敵の移動スピードは,1 / (1 + 影響を受けているタワー3の数).
それぞれの種類のタワーを何個まで建てることができるかが与えられる.建てられる合計数は20以下.

解法

本番では,以下で解いた.(おそらく想定解法ではない)
まず,タワーは一箇所に集中させた方が良い.
つまり,2m個置くなら (0, 1), (0, -1), (1, 1), (1, -1), ..., (m, 1), (m, -1) に置けばよいし,
2m+1個置くなら,追加で(m+1, 1)に置けば良い.
置き方は最悪で,20!/6!/7!/7!あるが,対称性を考えるとそんなに多くない.
つまり,(0, 1), (0, -1)を入れ替えても同じ置き方を満たせるし,左右反転しただけでも同じ置き方とみなせる.
対称なのを除去して,置き方を全部試すと,タイムリミットぎりぎりではあるけど通った.
その他の枝刈りとかは何も行なっていないので,枝刈ったりすると余裕を持って通るかもしれない.

おそらく想定解法は,タワー3の配置のみ全探索する.
これなら最大で20!/10!/10! = C(20, 10) < 2^20しかパターンはない.
タワー3の配置が決まれば,敵の移動スピードがわかるので,それぞれ空きマスにタワー1,2を置いたときのダメージ量が計算でき,DPにより最大ダメージが求められる.

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

続きを読む

Round #115 D問題 - Plane of Tanks: Duel (この記事を編集する[管理者用])

Source

RazMERiq 2012 D問題
Codeforces Round #115 D問題
Problem description

問題概要

2人でFPSゲームで銃の撃ち合い対戦する.
相手を倒せる確率を求める問題.
時間0では両者とも同時に攻撃する.
自分と敵のステータスとして,それぞれ
 HP : これが0になると倒され,以降攻撃できない
 DT : 攻撃間隔.このプレイヤーは時間0, DT, 2DT, 3DT, ... に攻撃する
 L, R : 最小攻撃力と最大攻撃力.攻撃が命中したら,敵のHPがL以上R以下のランダムの整数だけ減る.
 P : 攻撃を避けられる率.この確率で相手に全くダメージを与えられない.(整数%で与えられる)
が与えられる.
HPは200以下,DTは1以上30以下,攻撃力は10以上100以下.

解法

おそらく想定解法は以下の通り.
それぞれ何回攻撃を食らったら死ぬかという確率を十分大きな回数までDPで求めておく.
DPにおいて,R-L+1個の和を計算するとき,累積和を用いて高速化する.
後は,シミュレーションする.
避けられる率が100%の時は例外処理するのも良い.

本番では,以下で解いた.(おそらく想定解法ではない)
時間は周期LCM(DT1, DT2)で考えればよく,その間の攻撃回数はたかだか60回程度.
時間,自分のHP,相手のHPを状態にして,DPした.
DPする時,次に攻撃が命中する攻撃で場合分けし,ずっと当たらず時間が一周したら同じ状態に戻ってくるので,適当に処理する.
O((DT1+DT2)^2 * HP^2)ぐらい.

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

続きを読む

Round #115 C問題 - Geometry Horse (この記事を編集する[管理者用])

Source

RazMERiq 2012 C問題
Codeforces Round #115 C問題
Problem description

問題概要

コンボのあるシューティングゲーム的な何か.
N種類 (100以下) だけ敵の種類がある.
種類iはK[i]匹 (10^9以下) おり,倒した時にもらえる基本スコアはC[i] (1000以下) である.
好きな順番で倒して良い.
T個 (100以下) の整数P[i] (10^12以下) が与えられる.P[i] < P[i+1].
敵を既にP[i]匹以上倒している (かつP[i+1]匹倒していない) なら,敵を倒した時にもらえるスコアがi+1倍になる.
最終的に獲得可能な最大スコアを求める問題.

解法

Greedy.
だんだん倍率が高くなるので,スコアの小さい敵から倒していけば良い.
1匹ずつ処理するのではなく,同じ種類の敵がいなくなるか,倍率が変わるまで一気に処理する.

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

続きを読む

Round #115 B問題 - Plane of Tanks: Pro (この記事を編集する[管理者用])

Source

RazMERiq 2012 B問題
Codeforces Round #115 B問題
Problem description

問題概要

N回分 (1000以下) のゲームの結果が与えられる.
それぞれのゲームの結果は,プレイヤーの名前と点数が与えられる.
プレイヤーの名前はユニークであるとし,同じプレイヤーが何回もプレイしているかもしれない.
それぞれプレイヤーの最終得点は,プレイした中で最も高い得点とする.
総プレイヤー人数をMとして,各プレイヤーに対して,
 自分より点数が高いプレイヤーが50%*M以上いるなら noob
 そうでなく,自分より点数が高いプレイヤーが20%*M以上いるなら random
 そうでなく,自分より点数が高いプレイヤーが10%*M以上いるなら average
 そうでなく,自分より点数が高いプレイヤーが1%*M以上いるなら hardcore
 そうでなければ pro
と出力する問題.

解法

やるだけ.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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