スポンサーサイト

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

Codeforces Round #141 (Div. 2)

rated なら大惨事だった。

Tags : プログラミング Codeforces

結果

10 分くらい遅れて参加。unrated なので気楽。
A はすぐにできた。
B の凡ミスではまり、原因になかなか気付かず、終了 10 分前くらいに気付いて提出。
途中で E にも手を出したけど、連立方程式でやろうとしてしまって、ライブラリがなくてコンテスト中に作ったりしていた。結局 E は提出できず。

問題

A. Is your horseshoe on the other hoof?
4 つの靴があって、それぞれ何かの色で塗られている。
どの二つも異なる 4 つの靴をそろえるためには、最小であと何足買えばいいか?

B. Two Tables
二つの 0-1 行列 A, B が与えられる。
ずれ (x, y) に対して、A と B の類似度は
Σ_{i,j} A[i][j]・B[i+x][j+y]
で与えられる。
ここで、i, j は A[i][j]・B[i+x][j+y] が意味をもつような範囲全体を動く。
類似度を最大化する x, y を一組求めよ。

1 ≦ 行数, 列数 ≦ 50

C. Fractal Detector
2 × 2 の四角形で各セルは白 or 黒であるものを基準にして、
・分割を二倍にして白マスには一つ前の図形を当てはめ、黒マスは黒のままとする
という操作を一回以上くり返したものをフラクタルと呼ぶことにする。
与えられる n × m のグリッドにフラクタルはいくつ含まれるか?

1 ≦ n, m ≦ 500

D. Zigzag
1 2 3 4 ... z-1 z z-1 ... 3 2 1 2 3 ...
と続く数列を S[1..] として、与えられる a[1..n] に対して、二種類のクエリ
1. a[p] = v
2. a[l]・S[1] + a[l+1]・S[2] + ... + a[r]・S[r-l+1] を計算
を処理せよ。

1 ≦ n, クエリ数 ≦ 10^5
2 ≦ z ≦ 6

E. The Road to Berland is Paved With Good Intentions
辺に 0 or 1 の重みがついた頂点数 n の無向グラフが与えられる。
・頂点を一つ選んで、選んだ頂点に直接つながっている辺の重みを反転させる ( 0 なら 1 に、1 なら 0 に )
という操作を n 回以下行って、すべての辺の重みを 1 にできるか?
できるなら具体的な押し方も求めよ。

1 ≦ n ≦ 100

解答

A.
set を使うと楽。

http://www.codeforces.com/contest/228/submission/2258238

B.
すべてのずらし方を全探索しても O(H^2・W^2) とかで間に合う。

http://www.codeforces.com/contest/228/submission/2262642

C.
問題文が読みにくかった(らしい)。
自分にとっては前回の Div.1 C の方がよっぽど読みにくかったけど。

解法は DP。
サイズを固定したとき、フラクタルの種類は 2^4 = 16 通りしかない。
bool dp[t][S][y][x] := ( (x, y) を左上とするサイズ 2^(t+1)×2^(t+1) の正方形が種類 S のフラクタルかどうか )
とした。bool の代わりに S を dp の値として持てば 16 倍くらい速くなりそうだけど、しなくても十分間に合う。
dp は t が小さい順に計算していくとスマートに更新できる。というのも、サイズ 2^k×2^k のフラクタルは 2^(k-1)×2^(k-1) のフラクタルを 4 つ組み合わせてできているから。

http://www.codeforces.com/contest/228/submission/2266033

D.
2 ≦ z ≦ 6 なので数列 S は 5 通りしかない。
また、S が左右にどれだけずれているかも 2z-2 ≦ 10 通りしかない。
なので、高々 5・10 通りの Σa[]・S[] を Fenwick 木に保存しておけば、どちらのクエリも高速で計算できる。
更新のクエリは一回あたり 50・log(n)
計算のクエリは一回あたり log(n)
くらいでできる。

http://www.codeforces.com/contest/228/submission/2266257

E.
問題文を見た瞬間にライツアウトを意識してしまって、GF(2) の連立一次方程式にして解けばいいや、という考えに固執してしまった。
O(E・V^2) なのでぎりぎり間に合いそう。
ライブラリが解が一意に存在するときにしか対応してなかったので、コンテスト中は解けなかった。
あとで書いてみたら爆速だった。

別解 (想定解?) として、
・一つ辺の重みを反転する頂点は 2 つしかないから、そのまんま 2-SAT になって、O(V+E) で解ける。
・Union-Find でも解けるらしい ( こっちはよくわかってない )
とかもある。

http://www.codeforces.com/contest/228/submission/2267168
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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