スポンサーサイト

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

Codeforces Round #140 (Div. 1)

レーティングは減少しつづける。
いつもの感じで書くのは大変なので簡単に。

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

問題

A. Flying Saucer Segments
宇宙人とか flying saucer とか出てきて変な問題文だけど、ようするにハノイの塔。
N 個の円盤があるハノイの塔で、隣接する棒にしか移動できないとき、最短手数はいくつか? mod M で。
1 ≦ N ≦ 10^9

B. Naughty Stone Piles
N 個の積み木があって、積み木 i は高さ a[i]。
積み木 i を積み木 j の上に置くと、コスト a[i] かかり、積み木 i は消滅し、a[j]+=a[i] となる。
ただし、同じ積み木には高々 K 回しか積めない。
積み木が一つになるまで操作を繰り返す。
最小合計コストを求めるクエリを Q 個処理せよ。

1 ≦ N, Q, K ≦ 10^5

C. Anniversary
Fibonacci 数列の l, l+1, ..., r 項目から k 個選んで GCD をとる。GCD の最大値を mod m で求めよ。

1 ≦ m ≦ 10^9
1 ≦ l < r ≦ 10^12
2 ≦ k ≦ r-l+1

D. The table
M×N の行列 A があり、各要素は整数。
任意の行、列を選んで符号を反転させてよい。
どの行和、列和も 0 以上となるようにできるか?

1 ≦ M, N ≦ 100
-100 ≦ A[i][j] ≦ 100

解答

A.
ペグが n 枚あるとすると、具体的な手順は
1. 上 n-1 枚を棒 1 から棒 3 へ
2. n 枚目を棒 1 から棒 2 へ
3. 上 n-1 枚を棒 3 から棒 1 へ
4. n 枚目を棒 2 から棒 3 へ
5. 上 n-1 枚を棒 3 から棒 3 へ
となる。
n 枚のときの最小手数を T[n] とすると、この手順から
T[n] = T[n-1] + 1 + T[n-1] + 1 + T[n-1]
= 3*T[n-1] + 2
となって、これは行列べき乗で計算できる。
ちなみに、漸化式を解くと T[n] = 3^n - 1 となる。

http://www.codeforces.com/contest/226/submission/2239589

B.
解けなかった。
解法が Twitter で流れたりしていたのでまとめなおし。

積み木を頂点として、積み木 i を積み木 j の上に置くとき辺 j → i を張ると、グラフは最後に残った積み木を根とする有向木になる。
しかも K についての制約からこれは K 分木。( どの頂点も子の個数が K 以下 )
木を作ったとき、合計コストの計算は簡単にできる。
合計コストは
Σ depth(u)*a[u]
となる。根の深さは 0 とする。
深いところに a[u] の小さい頂点を ( 浅いところに a[u] の大きい頂点を ) もってくるのがよい。
深さ i には K^i 個の頂点を割り当てることに注意して、a[u] の降順にソートして浅いところから順に割り当てていけばよい。

http://www.codeforces.com/contest/226/submission/2246602

C.
二分探索はダメらしい。
題意がわからないので、なぜ二分探索なのかも不明。

[追記]
難しい。
Editorial を見ながら解いた。
まず、( 全然自明じゃないけど ) gcd(Fib[i], Fib[j]) = Fib[gcd(i, j)] が成り立つ。
このことから、S := { l, l+1, ..., r } の中から k 個選んで gcd を最大化する問題に帰着できる。
さらに言い換えれば、S の中に g の倍数が k 個以上含まれるような最大の g を求める問題ともいえる。( この言い換えはちょっとだけギャップがある。)
上記の g を求めるのに素直に全部試すと r-l+1 個も候補があって全然ダメ。
候補を絞り込む。
ちょっと考えれば、S に含まれる g の倍数の個数は r/g - (l-1)/g 個となることがわかる。割り算は小数以下切捨て。
なので、試すべきは r/g, (l-1)/g の値が切り替わるタイミングだけでいい。
r の約数、l の約数とその ±1 の値、そして 10^6 以下のすべての g (これは必要??) を全部試したら通った。
これだと、試すべき候補は O(sqrt(r)) 個なので間に合う。
最後に Fib[g] を計算するのはもちろん繰り返し二乗法でやる。

http://www.codeforces.com/contest/226/submission/2293454

D.
Editorial 見た。
行和 or 列和が負になっているところを見つけてフリップするという操作を変化が起こらなくなるまでくり返す。
フリップするごとに Σ_{i,j} A[i][j] は strict に増え、Σ_{i,j} A[i][j] の上限は 10^6 だから、行和と列和を管理しながら賢くやると最悪でも 10^8 回程度のループで変化が起こらなくなる。
このとき、実は解が求まっている。
なぜなら、もしある行和or列和が負ならそこはまだフリップできるはずだから。

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

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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