Entries

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

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

February 2012 Cook-off 5問目 - Equation Solver (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 5問目
Problem Statement

問題概要

0以上10^6以下の整数a, b, cが与えられた時,以下の等式を満たす正整数の組(x, y)の数を求める問題.
 x*y = a + b*lcm(x,y) + c*gcd(x,y)
無限に存在するならそれを指摘する.

解法

まず,任意の素数pに対して,yがpを素因数にもつ は 数xがpを素因数にもつ数 以上とする.
(後で,素因数にもつ数が等しくないものは入れ替え可能なので,適当にパターン数2^kをかける)
すると,等式は,
 x*y = a + b*y + c*x
となり,yはxで書き下すことができる.
a mod x = 0でなければならないのと,yはx以上であることを考慮すると,xの取りうるパターンは多くなく,全部試せる.
コーナーケースとして,
 a = b = c = 0の時は答え0
 a = c = 0, b != 0の時は答え無限
であることに注意する.

C言語のスパゲッティなコード

続きを読む

February 2012 Cook-off 4問目 - Daily Train (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 4問目
Problem Statement

問題概要

列車の席は6つの席ごとにグループになっていて,各車両の空席状況が与えられる.
x人分だけ,同じグループになっている席を買いたい.
パターン数を求める問題.

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

February 2012 Cook-off 3問目 - Careful Calculation (この記事を編集する[管理者用])

Source

codechef February 2012 Cook-off 3問目
Problem Statement

問題概要

正整数Nが素因数分解した形
 N = p[1]^k[1] * p[2]^k[2] * ... * p[m]^k[m] (p[i]は100000以下,k[i]は10^9以下)
で与えられる.
Nをphi(N)に置き換えるという操作を何回行うとNは1になるかを求める問題.

解法

置き換える操作は,同時に,それぞれp[k]^xを(p[k]-1)*p[k]^(x-1)に置き換えることになる.
まず,100000以下のそれぞれの素数に対して,p[k]-1を素因数分解しておく.
それぞれの素数に対して,p[k]が最初に現れるのは,何回目の操作が終わってからか?というのも計算しつつ大きい素数からその素因数が消えるまでシミュレートする.

C言語のスパゲッティなコード

続きを読む

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

Source

TopCoder SRM533 DIV1 HARD (1000pt)
Problem Statement

問題概要

N個 (30以下) の単語にピカチュー語を割り振る問題.
k番目の単語の出現頻度freq[k] (1以上1000以下) が与えられる.
k番目の単語に割りふるピカチュー語code[k]は以下を満たさなければいけない.
 code[k] は "pi", "ka", "chu" を何個か繋げてできる単語.(同じのを繋げても良い,pikapi, pikachuなどが可能)
 code[i] は code[j] のprefixになっていない.(i != j)
length(code[k]) * freq[k]の和の最小値と,最小値を達成できる割り当て方が何パターンあるかを mod 1000000009 で求める問題.

解法

メモ付き探索.freqの値はソートしておく.
最初使えるcodeは長さ0のコード1つのみとして,長さkのコードは,単語に割り振るか,長さk+2, k+2, k+3のコードを生成できると考える.
状態を,まだ割り振ってない単語の数,今使えるコードの種類として,以下のように探索していく.
 今使えるコードの種類のうち,最も長さの短いものの数をxとして,その内の何個を単語に割り振るかで場合分けする.(他はコード生成に使う)
 割り振る単語はfreqの高い方から割り振れば良い.割り振る単語の選び方のパターン数,freqが同率の場合はどれに割り振るかのパターン数を計算しながら探索する.
新しくコードを作るときは,残り単語数より多くのコードを生成しても意味無いので,作り過ぎないように適当に処理する.
以下のコードで最悪ケース0.072 sec.

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

続きを読む

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

Source

TopCoder SRM533 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

n*m (50*50以下) のグリッドが与えられる.各セルは#か.のどちらか.
好きな#のセルから初めて良いので,以下のような方法で,すべての#を削除できるかどうかを判定する問題.
 今いる場所の#を消し,
  現在の処理の回数が偶数回目なら,今と同じ行の#のセルに移動する.
  現在の処理の回数が奇数回目なら,今と同じ列の#のセルに移動する.
 最初に動くのは,0回目とする.(最初は同じ行内で動く)

解法

2つセットで考えると,X = #が奇数個ある行の数,Y = #が奇数個ある列の数とすると,
 Xは0以上1以下,Yは0以上2以下
を満たさなければいけないことがわかる.
また,自由に同じ行,同じ列にある#まで動くことができるとすると,すべての#のセルは連結でなければいけない.
逆に,以上の条件を満たせば,必ずすべての#を通るパスが存在することを示すことができる.

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

続きを読む

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

Source

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

問題概要

要素数Nの整数列が与えられる.各整数は1以上1000以下.
要素数が3以上なら,ある要素を消して,その両隣の数字の積を得点として得ることができる.
両端の要素は消せない.
最高得点を求める問題.
DIV1ではNは50以下.
DIV2ではNは10以下.

解法

逆から考える.
最初,両端の要素しかなく,まだ挿入してない要素を挿入すると,その両端の要素の積が得点として得られるとする.
すると,要素を挿入すると,それより左と右の区間は独立に考えることができるので,区間を状態としてDPすれば良い.
DIV2では全探索も可能.

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

続きを読む

UVa 12432 - Inked Carpets (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12432

問題概要

長さL (10^9以下) の床があり,カーペットを重なりなく敷き詰める最小コストと,その最小コストを達成するような色の変化の最小数を求める問題.
色はM (50以下) 種類あり,それぞれのペンキの値段が与えられる.
また,既存のカーペットはN (1000以下) 種類あり,それぞれの情報は
 区間[st, ed]を覆うことができる (区間[st+1, ed+1]などには使えないし,一部分だけ使うこともできない)
 色
 価格
 値引き率(後述)
が与えられる.
敷き詰めるときは,必ず,区間の最初から敷き詰めなければいけない.
できることは,あるカーペットを買ってそのまま敷くか,長さ1の無色カーペット(無料)をインクで塗って敷くかのどちらか.
カーペットを買うとき,同じ色のカーペットを3回以上連続で買うと,3回目以降はmax(価格 - 値引き率, 0)だけの価格で買うことができる.
途中で無色カーペットを使うと,連続して買っていることにならない.

解法

最後に買ったカーペットと,同じ色のカーペットを連続で買ったかどうかを状態としてDPする.
無色カーペットを使うときは,左右と同じ色か,最もインクの易い色しか考えなくて良い.(Mは微妙に小さいので全部考慮しても通る?)

UVa 12431 - Happy 10/9 Day (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12431

問題概要

Xはb進数で,dがn文字並んでいる数字とする.
X mod Mの値を(10進数で)出力する問題.
bは100以下,nとMは10^12以下

解法

漸化式を立てて行列べき乗した.
modの値Mが大きいので,オーバーフローしないように注意する.

UVa 12430 - Grand Wedding (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12430

問題概要

無向グラフが与えられる.枝には長さが設定されている.(ノード数,枝数の制限は書いていない)
各ノードには,守備兵を置くか置かないか,のどちらかにしたいが以下の条件を満たすようにしたい.
 全ての枝のちょうど一方の端にのみ守備兵がいる
条件をみたすことができるかどうかを判定する問題.
もし条件をみたすことが出来なければ,以下のことをして良い.
 長さK以上の枝をすべて破壊する(ただし,全ての枝を破壊してはいけない)
これで条件をみたすことができるならば,そのような最大のKを求める問題.

解法

守備兵が置けるかどうかは,2彩色可能かどうかなので,判定自体は簡単.
2分探索すれば良い.(らしい)
判定する方法として,各ノードkを2倍してノードk+とノードk-にして,(それぞれ守備兵を置く,置かないに相当)
ノードiとノードjに枝があるなら,
 ノードi+とノードj-を繋げ (iに守備兵を置くなら,jには置かないという意味)
 ノードi-とノードj+を繋げ
ノードk+とノードk-が連結でなければ2彩色可能.(連結なら,kに守備兵を置くなら,kに守備兵を置かないという意味になって矛盾)
なので,枝を長さでソートして,短い方からunion findしても良い.(自分はこっちでやった)

UVa 12429 - Finding Magic Triplets (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12429

問題概要

正整数N, K (それぞれ10^5以下) が与えられるので,以下の条件を満たす3つ組(a, b, c)の数を求める問題.
 (a + b^2) mod K = c^3 mod K, 1 ≤ a ≤ b ≤ c ≤ N

解法

bを固定して考える.
aは線形なので,c^3 mod Kがある範囲にあるcの数を高速に計算できれば良く,Fenwick treeを使う.
bを1ずつ変えていった時,cの取りうる値は1個減るか増えるかなので,Fenwick treeの修正もすぐ可能.

UVa 12428 - Enemy at the Gates (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12428

問題概要

ノード数N (10^5以下) ,枝数Mの無向グラフで,以下の条件を満たすもののうち,クリティカルな枝の本数の最大値を求める問題.
 連結で,同じノード間にはたかだか1本しか枝はなく,自分自身につながる枝もない.
クリティカルな枝とは,それを取り除くと連結でなくなるようなもの.

解法

2分探索した.
クリティカルな枝の本数がk以上になれるかどうかは,
 N-k個のノードで完全グラフを作り,
 k個のノードは次数1で,完全グラフのノードと繋げる
として,枝をM本以上消費できているかどうかを調べれば良い.(消費しすぎてる分は完全グラフから後で適当に取り除くと考える)

UVa 12427 - Donkey of the Sultan (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12427

問題概要

1次元上の半無限のグリッドがある.(左端は存在して,右端は存在しない)
2人でゲームをする.行動できなくなったら負け.自分は後手だけど,初期配置決めて良い.
勝てる初期配置の置き方のパターン数を求める問題.
最初,3枚のコインA, B, Cが置かれている.(左から順番に,コインA, B, C)
各ターン,1枚のコインを選び,それぞれ1マス左に移動させるか,コインAとCを同時に左に1マス移動させるか,のどちらかができる.
ただし,コインが重なったり,グリッドからはみ出してはいけない.
初期配置は,
 コインAは左端から,a1マス以上,a2マス以下の空きマスを挟んで置く.
 コインBはコインAから,b1マス以上,b2マス以下の空きマスを挟んで置く.
 コインCはコインBから,c1マス以上,c2マス以下の空きマスを挟んで置く.

解法

実験してみれば良い.
左端,コインA間の空きマスの数が偶数,かつ,コインBとコインCの間の空きマスの数が偶数なら勝てることがわかる.

UVa 12425 - Best Friend (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12425

問題概要

正整数N (10^12以下) が与えられるので,Q個 (50000以下) のクエリに答える問題.
各クエリでは,整数Xが与えられて,GCD(i,N)がX以下となる1以上N以下のiの数を求める.

解法

まず,GCD(i,N)はNの約数にしか成り得ない.
Nを素因数分解して,Nの約数を列挙する.
GCD(i,N) = kとなるiの個数は,GCD(i,N/k) = 1となるiの個数に等しい (iは1以上N/k以下) ので,オイラーのファイ関数を使えば求めれる.
オイラーのファイ関数も,Nの素因数分解は完了しているので簡単に求められる.

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

Source

TopCoder SRM527 DIV1 MEDIUM (450pt)
Problem Statement

問題概要

n*m (30*30以下) のグリッド (rows) が与えられる.
また,m個だけ,長さnの文字列 (cols) が与えられる.
それぞれは,グリッド,文字は,0か1か?からなる.
?を0か1に変えて,以下の条件を満たすようにしたい.
 各グリッドを縦に読んで,得られるm個の長さnの文字列は,(順番を入れ替えると)colsに一致する.
条件を満たすグリッドのうち,辞書順最小のものを求める問題.条件を満たすグリッドは少なくても1つは存在することは保証されている.

解法

つまりは,各列をどの文字列に対応させれば良いのか,マッチング問題になる.
なので,条件を満たす?の変え方が存在するかどうかは判定することができる.
グリッドの?を最初の方から,1文字ずつ0に置き換えて,条件をみたすことができなくなったらそれは1に置き換える,とgreedyに置き換えていく.

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

続きを読む

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

Source

TopCoder SRM527 DIV1 EASY (300pt)
TopCoder SRM527 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

0以上,10000以下の整数列a[1], a[2], ..., a[N]が与えられる.
N+1個のノードからなる全域木に対して,点数を以下のように定める.
 次数がkのノードに対して,a[k]点を与える.
 木の点数は,ノードの点数の合計.
全ての全域木の中で,最高点を求める問題.

解法

全域木であるので,ノード数はN+1,次数の合計は2N,次数の最低は1,最大はNを満たさなければいけない.
逆に,それを満たせば,そのような全域木を作ることはできる.
なので,現在使ったのノード数,使った次数を状態にしてDPすれば良い.

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

続きを読む

UVa 12420 - Item-Based Recommendation (この記事を編集する[管理者用])

Source

Rujia Liu's Present 5: Developing simplified softwares (2012-01-15)
UVa 12420

問題概要

n人 (50以下) のユーザーがいて,m個 (200以下) の映画がある.
各ユーザーは,自分が見た映画に対して,0点以上5点以下の実数点の評価をしている.
あるユーザーにおすすめすべき,まだそのユーザーが見ていない映画の,おすすめ度の計算方法が問題文で与えられている.
あるユーザーに対して,おすすめ度の高い方から10個,おすすめ度と共に出力する問題.

解法

やるだけ.

UVa 12416 - Excessive Space Remover (この記事を編集する[管理者用])

Source

Rujia Liu's Present 5: Developing simplified softwares (2012-01-15)
UVa 12416

問題概要

テキストエディタの置換機能で,連続する半角スペース2文字を,半角スペース1個に置き換えることを考える.
その際,文章に含まれる,まだマークの付けられていない,連続する半角スペースにマークを付ける,と言うことを繰り返す.
その後,マークの付けられた場所を同時に置換する.
(例えば,半角スペース9個からなる文字列は,1回置き換えると,半角スペース5個になる)
1MB以下の文字列が与えられるので,連続する半角スペースがなくなるまでに何回置換すればよいかを求める問題.

解法

まず,連続する半角スペースの最大値を求める.
1回置換すると,N個のスペースがceil(N/2)になるので,実際に割っていって,何回で1に行くか確かめる.

UVa 12414 - Calculating Yuan Fen (この記事を編集する[管理者用])

Source

Rujia Liu's Present 5: Developing simplified softwares (2012-01-15)
UVa 12414

問題概要

4文字以上,10文字以下の文字列が与えられる.
Aを整数STに,BをST+1に,…,ZをST+25に置き換えて,数字からなる文字列を作る.
連続する2文字を,全部同時に,その和 mod 10に置き換えるという処理を3文字以下になるまで行う.
3文字になった時,100になるような,最小のSTを求める問題.
10000以下にそのようなSTが存在しないならそれを指摘し,求めなくて良い.

解法

愚直に全部試す.
シミュレーションはO(length^2)かけても大丈夫だけど,
最後に何が残るかは,各数字が最終的に何回足されるかは2項計数で計算できるので,コンビネーションをかけながら足していけば良く,O(length)でもできる.

UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang) (この記事を編集する[管理者用])

Source

Rujia Liu's Present 5: Developing simplified softwares (2012-01-15)
UVa 12412

問題概要

生徒の簡易成績管理システムを作る問題.
生徒の数は100以下,生徒はユニークなSIDが付けられていて,ユニークじゃないかもしれない名前もある.
生徒が所属するクラスはちょうど1つで,科目は4科目で全部100点満点.
以下のクエリをこなす問題.
 生徒の情報が与えられるので追加する.
 該当するSID,もしくは該当する名前の生徒を消す.
 該当するSID,もしくは該当する名前の生徒の成績,合計点の順位を出力する
 クラス,もしくは,全体の統計データを出力する.
  統計データは,各科目ごとに,60以上,60点未満の人数とその割合,平均点.
  60点以上を合格として,k科目以上合格した人の数,など.
詳しい仕様は問題文を参照.

解法

やるだけ.

Round #107 DIV1 C問題/DIV2 E問題 - Smart Cheater (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 C問題 (1000pt)
Codeforces Round #107 DIV2 E問題 (3000pt)
Problem description

問題概要

電車の車長が,乗客(m人,300000以下)とグルで不正して,儲かるお金の期待値を最大化した時の期待値を求める問題.
各駅と駅の間で,チケットチェックが入る確率が与えられる.その時,その区間のチケットを持ってないとcだけ罰金を払うことになる.
駅の数はn.(150000以下)
乗客が乗る部分の連続する一部区間のチケットを売らないで,儲かる利益は車長と乗客とで等しく分配する.
とかだが,問題文が曖昧で,問題背景も微妙なので,問題を定式化した後のものを書く.

n個の整数,x[i]が与えられる.(i = 1~n)
n-1個の整数,p[i]が与えられる.(0以上100以下)
n-1個の実数,g[i] = x[i+1] - x[i] - 2*c*p[i]/100 で定義する.
m個の整数のペア,a, bが与えられる.(1 ≤ a < b ≤ n)
各整数のペアに対して,
 a ≤ c ≤ d ≤ bなるc, dのうち,Σ[k=c..d-1] g[k]の最大値を求める.(c=dなら和は0)
その最大値の和 / 2を求める問題.

解法

つまりは,ある区間の連続する部分和の最大値を高速に求める問題になる.
segment treeを使う.
そのままやるなら,seg treeの各区間では,左端から連続する部分の最大値,右端から連続する部分の最大値,(端からじゃなくて良い) 連続する部分の最大値を計算する.
最初に,累積和 s[k] = g[1] + g[2] + ... + g[k] を計算しておいて,それを用いるなら,s[j] - s[i] (j ≥ i) の最大値を高速に求める問題になる.
その場合は,seg treeの各区間では,最小値,最大値,その区間でのs[j] - s[i] (j ≥ i)の最大値を計算すれば良い.

C言語のスパゲッティなコード (累積和を使う方)

続きを読む

Round #107 DIV1 B問題/DIV2 D問題 - Quantity of Strings (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 B問題 (500pt)
Codeforces Round #107 DIV2 D問題 (1500pt)
Problem description

問題概要

n, m, kはそれぞれ1以上2000以下.
文字の種類数はmで,n文字の文字列を作る.
ただし,任意の連続するk文字からなる部分文字列は回文になっていなければいけない.
何通り作り方があるか,mod 1000000007で求める問題.

解法

解法1:場合分け
kが1,または,kがnより大きければ,制限が無いのでm^n.
kがnに等しいなら,すべての回文が許されるので,m^(ceil(n/2)).
そうでなければ,色々試すとわかるが,自由度が少なくて,
 kが偶数ならすべて同じ文字でなければならなくて,m.
 kが奇数なら,2個置きに見ると同じ文字でなければならなくて(例えば,abababaみたいなの),m^2.
計算時間量はO(log n).

解法2:
制約が小さいので,union findでどことどこが同じ文字でなければいけないかをまとめて,m^グループ数.
計算時間量はlogとかアッカーマンの逆関数とか無視すればO(nk)ぐらい.

C言語のスパゲッティなコード (解法1)

続きを読む

Round #107 DIV1 A問題/DIV2 C問題 - Win or Freeze (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 A問題 (500pt)
Codeforces Round #107 DIV2 C問題 (1500pt)
Problem description

問題概要

2人でゲームを行う.行動できなくなったら勝ち.
先手必勝か後手必勝か判定し,もし先手必勝なら最初のターンの勝てる行動を1つ求める問題.
最初正整数 n (10^13以下) が書かれている.
各ターン,書かれている数字を,そのノントリビアルな約数 (1とその数字自体を除く約数) を1つ選んで書き換える.

解法

1または素数なら,すでに行動できないので勝ち.
nが2つの素数の積(同じ素数の積でも良い)なら,どちらかの素数しか選べなく,どっちにしろ負け.
nが3つ以上の素数の積なら,2つの素数の積にできるので勝てる.
1つのゲームで状態数は小さいので,DPしても良い.

C言語のスパゲッティなコード

(本番に書いたコードで多少方針は異なる,2つの素数の積の最小値を探し,そこに動こうとする)

続きを読む

SPOJ 10373 - Help Balaji! [ABA12A] (この記事を編集する[管理者用])

Source

SPOJ 10373 [ABA12A]

問題概要

この問題では1は素数とみなす.
A以上B以下の整数で素数の積でかけるもののうち最大値を求める問題.
A,Bは10^12以下,B-Aは10^6以下.

解法

任意の正整数は素因数分解できるので,Bが答え.

SPOJ 9921 - ABC Path [ABCPATH] (この記事を編集する[管理者用])

Source

FCIS Local Contest 2012
SPOJ 9921 [ABCPATH]

問題概要

50*50以下のグリッドが与えられ,各セルには,アルファベット大文字が一文字書かれている.
上下左右斜めに隣接しているとみなす.
Aの書かれているセルから始まるパスで,アルファベット順にA, B, C, ...と続くパスを考える.(ZからAには戻れない)
その中で最長のものの長さを求める問題.

解法

BFSやDPなどで,辿りつけるマスを求めておく.
後は,辿りつけるマスのうち最も大きいアルファベットのマスが答え.

SPOJ 9637 - Black and White [BANDW] (この記事を編集する[管理者用])

Source

Argentinian Programming Tournament 2011
SPOJ 9637 [BANDW]

問題概要

文字列SとTが与えられる.
各文字列は同じ長さ (500以下) で,アルファベットのWとBのみを含む.
以下の変換を行なって,SをTにしたい.最小の変換回数を求める問題.
 連続する区間を選び,それに含まれるWを全てBに変えて,Bを全てWに変える.

解法

各場所に対して,SとTが一致しているなら0,一致していないなら1として,全部0にするのと同じ事になる.
0が連続してる場所,1が連続してる場所を分断する必要はないので一文字だと思って良い.
101→001→000にするのも,101→010→000にするのも同じで,1回の変換で,どうやっても1を1つしか減らすことができないので,1の数が答え.
つまり,最初に一致していない場所の連続,の数が答えになる.

SPOJ 9510 - Ads Proposal [ADSPROP] (この記事を編集する[管理者用])

Source

Fudan University Local Contest #3
SPOJ 9510 [ADSPROP]

問題概要

N人 (100000以下) の人と,M個 (500000以下) の広告がある.
各広告は,N人のうちの誰かが広告主である.
各広告の,クリックされた回数と,長さが与えられる.クリックされた回数は全て異なる.それぞれ10^9以下.
Q個 (100000以下) のクエリが与えられるのでそれに答える問題.
各クエリでは,整数K (1以上10^9以下) が与えられるので,各広告主の最もクリックされた順番でK番目までの広告の長さの和を求める問題.
(広告主ごとに求めるのではなく,全ての広告主の広告の長さの和を求める.K個も広告を持っていない人に対してはすべての広告の長さの和)

解法

最初に,広告主ごとに,クリック回数で広告をソートしておくO(N + M log M).
そして,A[k]に各広告主のk番目の広告の長さの和を持っておき(O(M)),sum[k]でA[1]~A[k]の和をで計算しておく(O(M)).
後は,全てのクエリに対してO(1)で答えることができる.

SPOJ 9935 - Break the Chocolate [BC] (この記事を編集する[管理者用])

Source

ACM/ICPC Regional Contest, Chengdu 2011
SPOJ 9935 [BC]

問題概要

縦横高さがN*M*K (2000*2000*2000以下) のサイズのチョコレートがある.
これを1*1*1のチョコレートに切りたい.
方法1と方法2,それぞれで切るのに必要な最小回数を求める問題.
方法1は手で割る方法で,1回で1切れのチョコレートを好きな場所で2つに割ることができる.
方法2はナイフを使う方法で,1回で,好きな数のチョコレートの破片を一度に,それぞれ好きな場所で2つに切ることができる.

解法

手で割る場合,1回で一切れしか増えないので,答えはN*M*K-1.
ナイフを使う場合,2切れになったら,同じように同時に切れば良いので,二切れのうち大きい方のみになったと思えば良い.
大きい方のみに依存するから,できるだけ均等にしたほうが良いので,N, M, Kそれぞれに対して,N → ceil(N/2)という操作を1になるまでやる.

SPOJ 10286 - DOTA HEROES [DOTAA] (この記事を編集する[管理者用])

Source

SPOJ 10286 [DOTAA]

問題概要

n人 (500以下) の勇者がいて,それぞれの初期HP (20000以下) が与えられる.
ある場所からある場所まで移動したいのだけども,その道沿いにm個 (500以下) の塔がある.
勇者は何人かグループで移動する.グループに属す人数に制限はない.グループの先頭は自由に変えれる.
あるグループが塔の視界に入ると,塔から1回攻撃され,グループの先頭の人がDだけダメージを受ける.
全員が目的地に辿りつける戦略が存在するかどうかを判定する問題.

解法

全員1グループで移動すれば良い.
それぞれのHPから,ダメージを受けても大丈夫な回数が計算できて,それがm以上なら良い.

SPOJ 9533 - Kindergarten Counting Game [KINDJ] (この記事を編集する[管理者用])

Source

SPOJ 9533 [KINDJ]

問題概要

各行に単語が何個含まれているかを求める問題.
単語とは,連続するアルファベット(大文字・小文字)のこと.

解法

やるだけ.

SPOJ 10366 - Play with Dates [CODEIT03] (この記事を編集する[管理者用])

Source

SPOJ 10366 [CODEIT03]

問題概要

年月日が与えられるので曜日を求める問題.
入力の範囲は,大体2012年から3000年程度.

解法

やるだけ.

Appendix

Recent Articles

ブログ内検索

Ads


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