Entries

スポンサーサイト (この記事を編集する[管理者用])

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

SRM552 DIV1 HARD - HolyNumbers (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 HARD (900pt)
Problem Statement

問題概要

N以下の正整数で,以下の条件をみたすものがいくつあるかを求める問題.
 Nを素因数分解した時,出てくる素因数は全てM以下.
 素因数pを持つならば,素因数分解した時に,素数pは偶数回出てくる.(詳細は問題文参照)
Nは10^10以下,Mは10^6以下.

解法

基本的には枝刈り全探索すれば良い.
小さい素数から順番に,それが何回素因数分解した時に登場するかを決定していく.
ただし,(N / 現在の数) が (現在の素数の2乗) を上回ったら,後は2個以上の素数をかけることができないから,
何も書けない,1個素数をかける,しか選択肢がなく,かけることができる素数の数は簡単に求めれるから端折る.
計算量は謎いけど,最悪ケースで0.4秒以下ぐらいで終わった.

C++によるスパゲッティなソースコード

続きを読む

SRM552 DIV1 MEDIUM - FoxAndFlowerShopDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N*M (30*30以下) のグリッドが与えられる.
各マスは,空白か,PかLが書かれている.
2つの核軸に平行な長方形型の領域を選ぶ.この時,共通領域があってはいけない.
長方形に含まれているPの数とLの数の差はmaxDiff (900以下) 以下でなくてはいけない.
長方形に含まれているPの数とLの数の最大値を求める問題.
条件をみたすように長方形を選べないときはそれを指摘する.

解法

まず,重ならないように長方形を選ぶというのは,少なくてもx座標か,y座標が共通部分を持っていない.
つまり,2つの長方形を分断するように縦か横に線を引ける.
線の場所で全探索する.(横に線を引くとして,グリッドを回転して2回処理した)

まず,そのマスより左上の長方形領域に含まれるPの数,Lの数を前計算しておく.
すると,包除原理より,ある長方形領域に含まれるPの数,Lの数はO(1)で計算できる.

ある長方形領域を選ぶとき,Pの数 - Lの数が等しいなら,Pの数 + Lの数が大きいほうが良いから,Pの数 - Lの数をキーとして,Pの数 + Lの数の最大値をメモする.
長方形領域の最初の行と最後の行を固定した時でDPした後,最初からある行までの範囲でDPしたりした.

実装方法によるけど,だいたいO(30^4)~O(30^6)程度になる.(6乗は下手に書くとTLEかも)
以下のコードはO(30^5).

C++によるスパゲッティなソースコード

続きを読む

SRM552 DIV1 EASY/DIV2 MEDIUM - FoxPaintingBalls (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 EASY (250pt)
TopCoder SRM552 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

問題文の図のようにボールを並べてN段の三角形を作りたい.
触れているボール通しは違う色でなければならない.
色は3色で,赤のボールの数がR個,緑がG個,青がB個使える.
最大で何個の三角形を作れるかを求める問題.
Nは10^9以下,R, G, Bは10^18以下.

解法

最初の2段は全部違う色でなくてはいけないし,後はボールの色は一意に定まってしまう.
結局は,全部だいたい同じ数だけボールが必要となる.
もうちょっと正確に言うなら,
 N mod 3 = 1の時,必要なボールの数はN(N+1)/3 = 3M+1となって,ある一色はM+1個,他の2色はM個必要
 その他の時,N(N+1)/3 = 3Mとなっと,全てのボールがM個必要
となる.

・解法1 (本番に書いたもの)
R >= G >= Bとする.(ソートする)
1個の三角形を作るのに必要なボールの数をそれぞれ a, b, c (a ≥ b ≥ c) とする.
答えは,
 min( floor(B/c), floor( (G+B)/(b+c) ), floor( (R+G+B)/(a+b+c) ) )
となる.(ボトルネックになる場所を全部調べる)
この問題では,実は,
 min( floor(B/c), floor( (R+G+B)/(a+b+c) ) )
で良い.(b=cであるから)

・解法2
N mod 3が1でないとき,答えは min(R,G,B) / Mとなる.(M = N(N+1)/6は三角形1個作るのに,それぞれの色の必要なボールの数)
N mod 3 = 1のとき,二分探索する.
K個作れるかためには,R-KM, G-KM, B-KMが負にならず,和 (R+G+B-3KM) がK以上でなければいけない.

C++によるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。