スポンサーサイト

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

ABBYY Cup 2.0 - Easy

2012/04/21
ABBYY Cup 2.0 - Easy

どの問題にも部分点がある。

Tags : プログラミング Codeforces 未解決

問題

問題セットの原文はここを参照。

A. Good Matrix Elements

n × n ( n は奇数 ) のマトリックスの
・ 対角線上のマス
・ まん中の行
・ まん中の列
を塗りつぶす。
塗りつぶしたマスに書いてある数字の合計はいくらか?

1 ≦ n ≦ 101

B. Rectangular Game

最初 n 個の石がある。
石を長方形状に並べる。ただし、行数は 2 以上にしないといけない。
1 つの行を残して、そのほかの石をすべて捨てる。
石の数が 1 つになるまでくり返す。
各ステップで捨てずに残した石の個数の和を最大化せよ。

2 ≦ n ≦ 10^9

C. Party

n 人の人がいて、
・ ある人とある人は友達である
・ ある人とある人は互いを嫌っている
という関係が複数与えられる。

人の部分集合 S で、
・ S に人 a が含まれているなら、a の友達もすべて S に含まれている
・ 人 a, b が互いに嫌いあっているなら a と b は S に同時には含まれない
をみたすようなものの最大サイズを求めよ。

2 ≦ n ≦ 2000

D. Encrypting Messages

長さ n の数列 a と長さ m の数列 b が与えられる。
a[0]+=b[0], a[1]+=b[1], ..., a[m-1]+=b[m-1];
a[1]+=b[0], a[2]+=b[1], ..., a[m+0]+=b[m-1];
a[2]+=b[0], a[3]+=b[1], ..., a[m+1]+=b[m-1];

a[n-m]+=b[0], a[n-m+1]+=b[1], ..., a[n-1]+=b[m-1];
という変換を施した後の数列 a を求めよ。

ただし、加算は mod c で行う。

1 ≦ m ≦ n ≦ 10^5
1 ≦ c ≦ 10^3

E. Space Voyage

n 個の町にそれぞれ一回ずつ出かける。
町 i には a[i] 個のかばんを持っていくことにしていて、b[i] 人の人が住んでいる。
一つのかばんには x 個のプレゼントが入っている。
町に滞在している間、最初の一日目は何もせず、二日目以降は住人全員に一つずつプレゼントをあげていく。
次の日に全員にプレゼントを上げられなくなった日の前日に町から出て行く。
すべての町の滞在日数の和がちょうど c 日になるような x は何通りあるか?
無数にあるときは -1 と答えよ。

1 ≦ n ≦ 10^4
0 ≦ a[i] ≦ 10^9
1 ≦ b[i] ≦ 10^9
1 ≦ c ≦ 10^9

F. Script Generation

n 頂点の重みつき二部グラフで、重みが t 番目に小さいマッチング ( の重み ) を求めよ。
ここで、マッチングの重みとはそのマッチングに使われた辺の重みの和であるとする。

1 ≦ n ≦ 20
1 ≦ 辺数 ≦ min(100, n^2)
1 ≦ t ≦ 2・10^5

small:
1 ≦ n ≦ 5

G.

解答

A.
n が小さいのでふつうにやる。
http://www.codeforces.com/contest/177/submission/1594338

B.
n を素因数分解すれば法則が見えてくる。
素因数の小さいものから順に取り除いていくのが最適。
http://www.codeforces.com/contest/177/submission/1595632

C.
一人を集合に加えると、友達関係でつながっている全員を集合に入れないといけない。
無向グラフの言葉で言うと、連結成分をまとめて集合に入れないといけないことになる。
なので、各連結成分に対して、集合に入れられるかどうか ( 嫌いなペアが存在しないか ) を判定して、入れられるなら答えに加えればいい。
http://www.codeforces.com/contest/177/submission/1596398

D.
縦に見ると各 a[i] に対して b のある区間を足しているのがわかる。
なので、Fenwick Tree ( のようなもの ) で高速に処理できる。
そんなことをしなくても線形でできるけど、頭がこんがらがったのでやめた。
http://www.codeforces.com/contest/177/submission/1597709

E.
合計滞在日数は x について単調に増加するので、x について二分探索できる。
std::equal_range みたいなことをすればいい。
すべての a が 0 のときがコーナーケース。
http://www.codeforces.com/contest/177/submission/1651308

F.
small しか解けてない。
small なら単に全探索するだけでいい。
http://www.codeforces.com/contest/177/submission/1600999
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。