スポンサーサイト

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

Codeforces Round #142 (Div. 1)

C, D がすごく良い問題だった。

Tags : プログラミング Codeforces

結果

A を 7 分で通した。
B を読んでダイクストラやるだけにしか見えないので誤読を疑いつつ書く。
配列サイズの上限間違いで 1 RE を出した後 pretest passed。INF の上限間違いで systemtest failed。10^9+1 で十分だと思ってしまった。
C が好きな感じの問題でしかも結構提出されているのでがんばって考えるも全くわからない。
C を諦めて D にとりかかる。
左から見ていって増加列になるように貪欲に積み上げればいいんじゃない?という発想に至りサッと書いて提出。pretest で落ちる。
ちょっと考えると反例が見つかりダメだった。もう少し考えていると JAG 夏合宿の問題(AOJ 2430)とほぼ同じだということに気付いた。AOJ 2430 でACしたコードを貼り付けて微修正して提出。pretest で落ちる。
よく読むと AOJ のは狭義増加列で今回は広義増加列だった。lower_bound を upper_bound に直して再提出。pretest 通る。
systemtest で TLE で落ちる。n ≦ 5000 で O(n^2 log n) だとダメかもなぁ、とは薄々思っていた。
結局 A の 1 完でレートはまだ落ちる。

問題

A. Shifts
n×m の 0-1 行列があり、任意の行を左右どちらにでも rotate していい。
少なくとも一列に 1 が揃うようにするためには最小で何回の rotate が必要か?

1 ≦ n ≦ 100
1 ≦ m ≦ 10000

B. Planets
無向グラフで頂点 1 から頂点 |V| まで移動したい。
各辺を移動にかかる時間が指定される。
また、各頂点に時刻の列が与えられていて、与えられた自国ちょうどには出発できない。( 到着はできる。 )
頂点を出発するのは整数時刻でないといけない。
頂点 1 から頂点 |V| まで移動するための最小時刻を求めよ。

2 ≦ |V| ≦ 10^5
0 ≦ |E| ≦ 10^5

C. Triangles
n 頂点の完全無向グラフから m 個の辺を選ぶ。
選んだ辺たちを辺集合とする部分グラフを G、G の補グラフを G' とする。
( G に含まれる三角形の個数 ) + ( G' に含まれる三角形の個数 ) を求めよ。

1 ≦ n ≦ 10^6
0 ≦ m ≦ 10^6

D. Towers
n 本の塔が一直線上に並んでいる。
塔 i を塔 i+1 の上に積み上げるという操作を好きなだけ行い、最終的に塔の高さが広義単調増加するようにしたい。
必要な操作の最小回数はいくつか?

1 ≦ n ≦ 5000
1 ≦ 塔の高さ ≦ 10^5

E. Gifts
名前と価格で特徴付けられる品物がいくつかある。
名前が等しく価格が異なる品物や、名前が異なり価格が等しい品物はありうるが、名前と価格が共に等しい品物はない。
n 個の品物を選んで、選んだ価格の和を最大化したい。
品物を選ぶ際には、品物の名前を指定することしかできない。
指定された名前をもつ品物が複数あるときはどれかが等確率で選ばれる。
最大の価値が得られる可能性のあるすべての指定方法から等確率で指定方法を決めるとき、実際に最大の価値が得られる確率を求めよ。

1 ≦ n ≦ 品物の総数 ≦ 1000

解答

A.
各列について、1 をそろえるための最小の手間を求めて min を取った。
各行に対して 1 の個数の位置を抜き出しておくと、列を固定したときに最小の手間を計算する部分が二分探索で O(n log m) でできる。
全体で O(mn log m) となる。
Editorial にあるように、二分探索のかわりに一番近い 1 の位置を DP して覚えておけば O(mn) になる。

http://www.codeforces.com/contest/229/submission/2274292

B.
ほぼふつうの Dijkstra。
出発時刻が遅れる部分は、二分探索で本当に出発できる時刻を求めるようにした。
わかってないけど、うまくやるとそれすらも要らないらしい。

http://www.codeforces.com/contest/229/submission/2292967

C.
Editorial そのまま。

1 つの頂点を共有する ( 完全グラフの ) 辺のペア (e1, e2) に対して、次のように重みを割り当てる。
・ e1, e2 が共に G の辺であるとき、重みは +2
・ e1, e2 が共に G' の辺であるとき、重みは +2
・ e1, e2 の一方だけが G の辺であるとき、重みは -1

このように重みを定めて、すべての (e1, e2) のペアについて重みの和をとる。
すると、
・G に含まれる三角形は、重み +6 に相当
・G' に含まれる三角形は、重み +6 に相当
・G の辺と G' の辺を両方含む三角形は、重み +0 に相当
となることがわかる。
なので、重みの和 / 6 が答えになる。

いい感じにキャンセルさせてほしいものだけを数えている。
すばらしい解法だと思う。

http://www.codeforces.com/contest/229/submission/2296405

D.
Editorial を読んでもよくわからなかったので、Comments で紹介されていたほぼ同じ問題(USACO 2009 Open の 3 問目)解説を参考にした。

塔 i, i+1, .., j をマージしてできる塔を [i..j] と書くことにする。

まず思いつくのは、
dp[i][j] := ( 塔 0, 1, .., j を見ていて、一番右の塔が [i..j] であるときの、建っている塔の最大個数 )
という DP。
これを素直に実装すると、遷移に O(n) かかるので O(n^3) 解が得られる。もちろん TLE。

O(n^3), TLE
http://www.codeforces.com/contest/229/submission/2298633

この方法を改善する。
新しく塔を作る遷移を O(n) 通り全部試しているけど、全部やる必要はない。
具体的には、
・dp[i][j] -> dp[i][j+1] の遷移 ( 塔 [i..j] を塔 j+1 の上に積む )
・dp[i][j] -> dp[j+1][k] の遷移 ( 塔 [i..j] 以上の高さをもつ塔を [i..j] の右に作る )
の二つの遷移があれば十分。
ここで、k は
( 塔 [i..j] の高さ ) ≦ ( 塔 [j+1..k] の高さ )
をみたす最小の k。

k を見つけるのに結局 O(n) のループが必要なので結局 O(n^3) だと思うかもしれないけど、j が増えるにつれて k も増えるという性質を使えば、j のループごとに k の値を初期化する必要がないことに気付く。
つまり j と k について尺取法みたいなことをする。
( Dinic のアルゴリズムで blocking flow を流す部分が O(VE) でできるのとも似ている気がする。)
これで amortized O(n^2) が達成され、accepted がもらえる。

O(n^2), 468ms
http://www.codeforces.com/contest/229/submission/2296405

この問題はさらにオーダーを落とすことができる。
dp[i][j] のキー i は実は要らない。
dp[j] := ( 塔 0, 1, .., j について、一番右の塔が最小でいくつの塔をマージしてできているか )
とする。
計算したい値を陽に持っていないけど、最後に DP テーブルを逆向きに辿れば塔が何本あったかがわかる。
これを素直に実装すると O(n^2) となる。

O(n^2), 62ms
http://www.codeforces.com/contest/229/submission/2298788

上の amortized O(n^2) 解法と同じように、必要な 2 箇所への遷移だけを考えることでオーダーを落とせる。
新しく塔を作る遷移は、dp[j] が j について広義単調増加することを使えば二分探索で遷移先の位置が求められる。

O(n log n), 31ms
http://www.codeforces.com/contest/229/submission/2298811

さらに、新しく塔を作る遷移で、遷移先の候補として dp の値が単調に増えるものだけを残すようにする。
queue を使ってうまく管理すれば amortized O(n) が達成できるらしい。( よくわかってない。蟻本のスライド最小値みたいな感じ? )

E.
DP。
最大の価値を得る可能性があるということは、価値の高い品物から順番に指定していくということ。
なので、品物は
(1) 絶対に指定しないといけないもの
(2) 指定する選択肢も指定しない選択肢もあるもの
(3) 絶対に指定してはいけないもの
の三種類に分類できる。

(2) をどうするかが問題になる。
dp[i][j] := ( (2)に属する i 番目の品物まで見ていて、あと j 個選ぶときに、最大の価値が得られる確率 )
とする。DP の遷移は、(2)に属する i 番目の品物を指定した場合と指定しなかった場合を両方考えればいい。係数に現れる確率は簡単な計算で出る。二項係数を組み合わせたものになる。

メモ化再帰の終端条件を間違えてちょっとはまった。( n==0 のとき return 1; としていた。)

Div.1 の E 問題にしてはかなり簡単なほうだと思う。
このセットについて言えば C, D の方が難しく感じた。

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

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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