Entries

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

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/953-7d42eb3b
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 5725 - 123 Sequence [KSEQ] (この記事を編集する[管理者用])

Source

Kurukshetra OPC 2010
SPOJ 5725 [KSEQ]

問題概要

123からなる単調非減少の数列で,全ての要素間の差(の絶対値)が与えられている.
 差が0の要素のペアの数は X
 差が1の要素のペアの数は Y
 差が2の要素のペアの数は Z
さて,そのような123からなる単調非減少の数列は何個あるかを求める問題.
X, Y, Zは10^8以下.

解法

場合分け問題.
0の数をa,1の数をb,2の数をcとすると
 2x = a(a-1) + b(b-1) + c(c-1)
 y = ab + bc
 z = ac
となるa, b, cの数を求めれば良い.
zが0でなければ,満たすa, cのペアを全部試す.
zが0でyが0でなければ…,などと場合分けして残りのパターンも調べる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/953-7d42eb3b
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


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