スポンサーサイト

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

June Cook-Off 2012

2012/06/18 01:00~03:30

ちょっと遅れたり延びたりした。

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

結果

DOWNLOAD: -
GROWGOLD: TLE
NOKIA: -
OLYMPIC: -
TWTCLOSE: AC

問題

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

Golden Trees

一日目は initTax 個の金を納める。
続く slot1 日は、前日収めた金の個数 +1 個の金を納める。
続く slot2 日は、前日収めた金の個数 ×2 個の金を納める。
以降、毎日、( 直前の K 日に収めた金の個数の積 ) 個の金を納める。

N 日目には何個の金を納めているか?
mod 10^8+7 で。

1 ≦ initTax, slot1, slot2 ≦ 50
1 ≦ K ≦ slot1 + slot2 + 1
1 ≦ N ≦ 10^9

Connecting Soldiers

N + 2 箇所の一列に並んだ点に人を配置する。
隣り合う点間の距離は 1 とする。
両端には最初から人がいる。

残り N 人を一人ずつ順番に異なる位置に配置していきたい。
人を位置 i に配置すると、
( 位置 i から左方向に最も近い位置にいる人までの距離 )
+ ( 位置 i から右方向に最も近い位置にいる人までの距離 )
がコストに加えられる。

コストの和が M を超えないようにしつつ、M にどれだけ近づけられるか?

1 ≦ N ≦ 30
1 ≦ M ≦ 1000

Closing the Tweets

N 個のツイートがあって、
「ツイート i をクリックする」
「開いているすべてのツイートを閉じる」
というクエリが K 個くるので、各時点での開いているツイートの個数を求めよ。

1 ≦ N, K ≦ 1000

解答

GROWGOLD.
まず、最初の slot1, slot2 日間の変なパターンは愚直に計算する。
その後は、K 個の数の積だけが現れる規則的なパターンになるので、上手に計算できる。

K 個の数の指数だけに注目すると、線形の K 項間漸化式が得られる。
( よく見ると、この答えは K-nacci 数列 )
これを繰り返し二乗法で N 日目まで一気に計算してやればいい。
ただし、指数を計算しているということを忘れてはいけない。
Fermat の小定理により、mod 10^8+6 で計算すればうまくいくことがわかる。

計算量は O(K^3 log N)。

最後に、これでもまだ TLE するかもしれない。
mod の値が 10^9+7 ではなく 10^8+7 であることに注意すれば、行列の積の計算における mod を取る回数を減らすことができることに気付く。
つまり、K・(10^8+7)^2 は long long に収まる。

これで間に合う。
せっかく解法を思いついていたのに定数倍にやられた。short contest でこういうのが来るときつい。

NOKIA.
素直にやろうとして、O(N^2*M^2) くらいかかってしまって解けなかった。

まず、最小コスト MN と最大コスト MX は DP なり何なりして求められる。
実は、[MN, MX] に含まれるすべての整数が実現できる。
( Editorial に証明も載っていたけどよくわからなかった。2 つに分割した小問題それぞれのコストは独立に決めていいので、なんとなく正しそうな気はする )
これに気付けば簡単に答えは求められる。

TWTCLOSE.
O(NK) でいいので素直に実装すればいい。
Editorial のコメントで、各クエリを amortized O(1) で処理する方法と厳密に O(1) で処理する方法について触れられていて、どっちもスマートで感心した。

ソースコード

GROWGOLD: http://www.codechef.com/viewsolution/1134226
NOKIA: http://www.codechef.com/viewsolution/1134250
TWTCLOSE: http://www.codechef.com/viewsolution/1134321
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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