スポンサーサイト

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

Codeforces Round #122 (Div. 1)

2012/06/04 00:30 ~ 02:30
Codeforces Round #122 (Div. 1)

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

結果

A: AC
B: AC
C: -
D: -
E: -
21332132


問題

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

A. Cutting Figure

n × m のグリッド上の図形が与えられる。
図形のマスをいくつか消して、図形が非連結になるようにしたい。
最小で何マス消せばいいか。
与えられる図形は連結であることが保証される。
どうやっても非連結にできないときは -1 と答えよ。

1 ≦ n, m ≦ 50

B. Xor

整数列 a[1], a[2], ..., a[n] に対して、次の操作のいずれかを合計 u 回施す。
(1) すべての i に対して a[i] = a[i] xor b[i] と更新する
(2) すべての i に対して a[i] = a[p[i]] + r と更新する

操作が終わった後の a について a[1]・k[1] + ... + a[n]・k[n] を最大化せよ。

1 ≦ n, u ≦ 30
0 ≦ r ≦ 100
1 ≦ a[i], b[i] ≦ 10^4
-10^4 ≦ k[i] ≦ 10^4
p[i] は { 1, 2, ..., n } の順列

解答

A.
みたまんま、無向グラフの全域最小カット。
ただ、頂点数がやばいので汎用的なアルゴリズムは使えない。
いつものように、グラフの特殊性を利用する。つまり、格子。

じっくりにらんでいると、二つ消せば非連結にできそうな気がしてくる。
というのも、いつも角があるから。

なので、一つ消して非連結になるかどうかを見て、すべての場所を試してもダメだったら答えは 2 だ、とすればいい。

コーナーケースは非連結にできない場合で、頂点を分離する前にすべての頂点を消してしまうときがまずい。
これは、グラフは元々連結なので、頂点数が 2 以下であることと同値になる、ということが考えればわかる。

O(m^2 n^2)
http://www.codeforces.com/contest/193/submission/1800143

B.
+ と xor は相性が悪くて ( 私見 )、いい方法がみつからない。

ここは、不自然に小さい制約に注目する。
探索っぽい?
でも、素直にやると分岐の数は 2^u になるので、間に合わない。

そこで、xor を 2 回とれば元に戻るという性質を利用すれば、xor を 2 回連続でとる意味はほぼないことに気付く。
( ただし、ぴったり u 回の操作をするための回数あわせとしてだけは有効 )
なので、探索の分岐が一気に減る。
これはよくあるパターンで、分岐の数は Fibonacci 数列になる。
Fibonacci 数列の 30 項目を見てみると、8 × 10^5 くらいで、それぞれについて O(n) の処理が入るので、なんとか間に合う。

答えを計算するのにカッコよく inner_product を使ってみたら、int がオーバーフローして resubmit する羽目になった。ださい。

O(n fib(u)) ( fib(u) は u 番目の Fibonacci 数 )
http://www.codeforces.com/contest/193/submission/1758402
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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