2017-11

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 倍を引いた.

スポンサーサイト

Univ. of Aizu ICPCPC 2011 TT 18 DIV1

UVa のジャッジサーバが落ちていたため練習会としては流れた.
問題は選ばれていたので 3 問読んで 3 問書いた.後で送ったら一発で通った.

E: Non-Decreasing Prime Sequence (UVa 11669)


有限非減少素数列の weight とは,各項の積のこと.
weight が A 以上 B 以下のうち,「長さ昇順 → 辞書順」で K 番目にくるものを求める.
2 <= A <= B <= 1,000,000,5,000 ケース.

要は A 以上 B 以下の整数を素因数の様子でソートしたときに K 番目.
cntp[x] で x の素因数の個数,minp[x] に x の最小の素因数を覚えさせれば,
a が b より先に来る条件は cntp[a] < cntp[b] or (cntp[a] == cntp[b] and minp[a/g] < minp[b/g]),ただし g = gcd(a, b).
これを用いると O(N (log N)^2) で N までソートできる.
その後,√N 個くらいずつに区切って普通の大小でソートしたものを持っておくと,各クエリに対して O(√N log N) で処理できる.

どう高速化しようか悩んで結構時間を使ってしまった.

F: Dynamic Frog (UVa 11157)


一直線上の川をカエルが往復する.
岩が N 個あり,大きい岩は何度でも踏めるが小さい岩は一度しか使えない (つまり行きと帰りのいずれか).
最大ジャンプ幅を最小化する.
N <= 100.

行きと帰りを同時に左端から作っていく DP.
dp[i][j] から,dp[k][j] と dp[i][k],ただし k >= max{i, j},に配る.
小さい石について dp[i][i] を捨てる.

G: Through the Desert (UVa 11935)


燃料を満タンにして車が砂漠の道を行く.
途中で,燃料の消費率,壊れて燃料がリークする,燃料補給,修理といったイベントが起こる.
必要な燃料タンクの最小値を求める.

二分探索,シミュレーション.

Univ. of Aizu ICPCPC 2011 TT 17 DIV1

2 時間程度遅れて参加.7 問中 5 問読んで 5 問通した.

A: Mirror Clock (UVa 11650)


時刻が与えられるので,時計を鏡で反転させて読んだときの時刻を答える.

分に直して -1 倍した.
01:00-12:59 で表す模様.

B: Circular (UVa 967)


[a, b] の整数で,各桁の数字を巡回置換していっても素数にしかならないものの個数を数える.
100 <= a <= b <= 1,000,000

桁が奇数のみなので dfs で作っていった.
愚直にやっても通るかもしれない.
判定は sprintf して適当に.

C: Conic Distance (UVa 10495)


円錐の側面上の 2 点が頂点からの角度と向きで与えられるので,円錐の側面上での 2 点の最短距離を求める.

展開図で考える.角度の差 (<= π) を (底面の半径)/(母線) 倍すればよい.

D: String Partition (UVa 11258)


数字の列が与えられるので,32bit 符号付き整数たちになるように区切って,和を最大化する.
長さ L <= 200.

leading zero は許されないことになっているが許しても変わらない.O(L^2) の DP.
0 をちゃんと処理すれば O(L).

E: Texas Trip (UVa 11243)


平面上の N 点が与えられるので,それらをすべて含む最小の正方形 (任意の向き) を求める.
N <= 30.

N <= 1 は別途処理.
各 2 点の方向とそれに垂直な方向を列挙してソート.
すると各区間内の方向で見る場合は,上下左右の端に来る点は変わらず,
bounding box の縦横の長さはそれぞれ単調 (たぶん).
なので max{ (縦), (横) } は減ってから増える形になる (たぶん) ので,
三分探索で最小が求まる.



«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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