Entries

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

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

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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