スポンサーサイト

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

Codeforces Round #143 (Div. 2)

いつもより簡単。

Tags : プログラミング Codeforces

結果

A, B, C, D を 28 分で通した。まったくバグらなくていい感じだった。
E は大まかな方針はすぐに立ったけど、細部が詰められなくて通せなかった。

問題

A. Team
n × 3 の 0-1 行列が与えられる。1 が二つ以上ある行はいくつあるか?

1 ≦ n ≦ 1000

B. Magic, Wizardry and Wonders
各項が 1 以上 L 以下の数列 A があった。
A の末尾の二項 A[n-2], A[n-1] を A[n-2]-A[n-1] に置き換える。( 数列の長さは 1 減る。)
この操作を数列の長さが 1 になるまでくり返す。
今、はじめの数列の長さ N と最後に残った数 d がわかってる。はじめの数列としてありうるものをひとつ求めよ。複数あるときはどれを答えてもいい。一つも存在しないときはそれを指摘。

2 ≦ N ≦ 100
-10^4 ≦ d ≦ 10^4
1 ≦ L ≦ 100

C. To Add or Not to Add
整数列 a[1..n] が与えられる。
操作:a[i]++
を k 回まで行うことができる。
max{ a[1..n] に x が出現する回数 | x は整数 }
を最大化し、また、max を達成する最小の x も求めよ。

1 ≦ n ≦ 10^5
0 ≦ k ≦ 10^9
-10^9 ≦ a[i] ≦ 10^9

D. Magic Box
(0, 0, 0) - (x, y, z) の二点で指定される直方体がある。
各面には数字が書かれている。
位置 (x1, y1, z1) から見える数字の和を求めよ。

E. Cactus
連結無向グラフが vertex cactus であるとは、すべての頂点が高々一つの閉路に属することをいう。
パスが simple であるとは、パスが同じ辺を二回通らないことをいう。
自己ループと多重辺をもたない vertex cactus が与えられる。
二頂点間の simple path の個数を mod 10^9+7 で求めるクエリを k 個処理せよ。

2 ≦ |V| ≦ 10^5
1 ≦ |E| ≦ 10^5
1 ≦ k ≦ 10^5

解答

A.
数える。

http://www.codeforces.com/contest/231/submission/2312163

B.
数列 a を縮める操作を巻き戻すと、
d = a[1] - a[2] + a[3] - a[4] + ... +(-1)^(n+1) a[n]
となっていることがわかる。
各 a[i] の上限と下限は決まっているので、右辺の最大値と最小値は簡単に計算できる。
この max と min の間に d が入っていれば、求める数列が存在することがわかる。
たとえば、min を達成する数列からはじめて、d に等しくなるまで a[i] の値を +1 (or -1) していけばいい。

http://www.codeforces.com/contest/231/submission/2313623

C.
まず、最大の出現回数を達成する最小 x は元々のある a[i] に等しいことに気付く。
なので、すべての a[i] について試す。
a[i] を固定したとき、答え ( a[i] の出現回数の最大値 ) について二分探索にすると最大の出現回数は高速に計算できる。二分探索内部の判定は累積和でいいけどなぜか Fenwick tree を使ってしまった。

http://www.codeforces.com/contest/231/submission/2313955

D.
何も書くことがない。なぜ D 問題に持ってきたのか不明。

http://www.codeforces.com/contest/231/submission/2314323

E.
与えられるのは一般に cactus graph と呼ばれているものではなく、より強い制約がついた vertex cactus である。
これを混同していてはまってしまった。

まず閉路を一点に縮約する。
各頂点は高々一つの閉路に属するのでこれができる。
( ただの cactus ならリボン形みたいなグラフで困ってしまう。)
するとグラフは木になる。

実験していると、答えは 2^( 木の二点間のパス上にある元々閉路だった頂点の個数 ) に等しいことが見えてくる。証明も難しくない。
これは LCA を使って高速に求められる。
LCA はまだライブラリ化してなかったので蟻本のを写経した。

http://www.codeforces.com/contest/231/submission/2353209

閉路を縮約する部分は、より一般に二重辺連結成分分解をしてもよいので、ライブラリチェックにも使えそうだなぁと思った。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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