2017-10

Latest Entries

スポンサーサイト

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

Next generation Contest 6

5 時間 10 問.
序盤は,2 問目以降は statistics 見て提出があるものを追いかけた.B (1WA) → D → J → I → A → G → H → C → F が 90 分で終わり,E に 3 時間かけて 11 回目の提出で通った.単独全完で 1 位.
問題文は短く,実装も軽め.典型アルゴリズムという感じの出題が多かったが,ちょっと考えるタイプも多かった.また,似た感じのが何組かあったという印象.

A: Again Lucky Numbers


N 桁の非負整数であって整数 M を文字列として含まないものの個数を mod 10,000,007 で求める.
1 <= N <= 100,1 <= M <= 10^100,(ケース数) <= 1,000.

M を文字列とみて KMP で状態遷移を作って状態数 O(N |M|) の DP.

B: BFS (Binary Fibonacci String)


BFS(0) = "0", BFS(1) = "1",BFS(n) = BFS(n - 2) ~ BFS(n - 1) (n > 1) で定まる文字列 BFS(n) を考える.BFS(N)[i .. j+1] を求める.
0 <= N, i, j <= 2^31 - 1,0 <= j - i <= 10,000,j < |BFS(N)|,(ケース数) <= 100.

長さは Fibonacci 数で,事前にテーブルを作る.n >= 60 で既に長さが 2^32 は超えているので,BFS(n) の代わりに BFS(n - 2) を考えればよい.あとは 1 箇所ずつループを回すか,全体を再帰に投げるか,などで求める.

BFS(n - 2) が先であることを意識せず,N >= 60 のとき単に N = 60 としてしまった.

C: Colorful Eggs


n 個のバスケットに卵が何個かずつ入っていて,卵を追加したり移動させたりの操作が定まっていて毎日行われる).d 日後の各バスケット内の卵の個数を mod 1,000,000,007 で答える.
1 <= n <= 60,1 <= d <= 1,000,000,000,(ケース数) <= 111.

操作による卵の個数の変化は線形.行列累乗.

D: Divisors


d(n) = (n の約数の個数),σ(n) = (n の約数の和) とする.a <= i <= b なる k の倍数 i についての d(i) の総和,σ(i) の総和を求める.
0 < a <= b <= 10^5,0 < k < 2,000,(ケース数) <= 75.

d(n) と σ(n) を事前計算する.素因数が見つかればそれで割り切れるだけ割れば小さい n に帰着できる.√n までみて大丈夫だった.事前計算後は i をすべて見た.

E: Extreme Divisors


d(n) = (n の約数の個数),σ(n) = (n の約数の和) とする.a <= i <= b なる k の倍数 i についての d(i) の総和,σ(i) の総和を mod 2^64 で求める.
0 < a <= b <= 10^12,0 < k < 2,000,(ケース数) <= 75,TL 3 秒.

問題 D の a, b が大きいバージョン.
0 < i <= nk について 2 回解く.
d(n) や σ(n) の和を,約数視点で数える.すなわち,m に対して,nk 以下の k の倍数であって m の倍数でもあるものの個数を f(m) とすれば,f(m) あるいは m f(m) の和を求めればよい.ここで f(m) = floor( n * gcd(k, m) / m) となる.主要なアイデアとして,m が小さいところでは m について和をとり,m が大きいところでは f(m) について和をとる (Riemann 積分と Lebesgue 積分の使い分け,というイメージ).これで √(10^12) 程度の計算量が見える.
割り算して m = kq + r とおく.r で場合分けすれば gcd(k, m) は一定であるから,f(m) から q の範囲が求まる.これで O(k √b) で答が求まるが TLE.
高速化のために,gcd(k, m) が等しい r をまとめて扱う.f(m) から m の範囲が求まったときその範囲で gcd(k, m) = g なる m の個数や m の和を求める部分が厄介だが,サイズ k の配列いくつかで r の個数や r の和を表す部分和をもっておけば解決する.これで O(d(k) √b) になり通る.

TL が厳しく,通ったものも 2.9 秒台だった.手元で d(k) が大きいケースを並べると 4 秒台.行った高速化としては,
・r が 1 個のときに特別処理して定数倍高速化 (O(k √b) で TLE したコードを流用).
・Riemann 積分側で,m をループで回して mod k で適切な r になるかを見るのではなく,r たちの配列を用意.
・「√ くらい」で区切るの定数倍調整.
といったあたり.

TLE 解消後 WA をもらった.これは mod 2^64 をそのまま long long で計算してしまえばよいだろう (出力用には unsigned long long),とだけ思っていたため.x 以上 y 以下の整数の和を求める,という機会があり,2 除がでてくる.(x + y) と (y - x + 1) で 2 で割れる方を先に割る,として解決.

F: Fun with Strings


'a', 'b' からなるある文字列から初めて (1 番目とする),「'a' を "b" に,'b' を "ab" に」という置換を繰り返していったら,N 番目の長さが X,M 番目の長さが Y となった.可能かどうかを判定し,可能なら K 番目の長さを mod 1,000,000,007 で求める.
0 < N, M, X, Y, K < 10^9,N != M,(ケース数) <= 1,000.

最初の 'a' と 'b' の個数を a, b とすれば n 番目の長さは a, b の Fibonacci 係数 1 次式で書けるので,N や M が小さい方の係数より大きい場合は不可能としたのち,連立方程式 (常に full rank) の整数解 (a, b) を求めればよい.
大きい N, M を無視するにあたって,60 以上,などの決め打ちは連立方程式を解くステップでオーバーフローの危険があるので回避した.

G: Great Numbers


10 進法で N 桁の整数であって,桁に 6 以下のみが現れ,どの桁でも割り切れるようなものの個数を mod 1,000,007 で求める.
1 <= N <= 40,(ケース数) <= 40.

桁数,どの桁をもったか,mod 60 で DP.

H: Highest Paid Toll


頂点数 N,辺数 M の重み付き有向グラフが与えられる.s から t まで合計重み p 以下で行くとき,通る辺のうちの最大の重みの最大値を求める.
2 <= N <= 10,000,1 <= M <= 100,000,(ケース数) <= 50.

各辺に対してそれが使えるかどうか調べればよい.s から順方向と t から逆方向に Dijkstra しておけば各辺 O(1) で判定できる.

I: Inhabitants


凸 n 角形が与えられ,その後 Q 個の点が与えられるので,内部 (周上を含む) であるかを判定する.
3 <= n <= 10^5,1 <= Q <= 10,000,(ケース数) <= 10.

凸なので適当な内部の点から見た角度で二分探索できる.ライブラリそのまま.

J: Just Prune The List


2 つの多重集合が与えられるので,それぞれからいくつか取り除いて同一にする.取り除く最小個数を求める.
1 <= (多重集合のサイズ) <= 10,000,(ケース数) <= 100.

set で共通部分を数えて,要素数の和から 2 倍を引いた.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/31-78faefbe

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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