Entries

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

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

SPOJ 16282 - Horace and his primes [TAP2013H] (この記事を編集する[管理者用])

Source

SPOJ 16282 [TAP2013H]
Argentinian Programming Tournament 2013

問題概要

正整数 $n$ に対して,$f(n)$ を $n$ を割り切る素数の和で定義する.
$n$ を $f(n)$ に置き換えていく手順を繰り返すといずれ $n$ は素数になる.
$n$ から始めた時,素数になるまでに必要な手順の数 $+1$ を $g(n)$ とする.
$P$ 個のテストケースが与えられる.
各テストケースでは $A \leq n \leq B$ かつ $g(n) = K$ を満たす $n$ の個数を求める.
$1 \leq P \leq 10^5$
$2 \leq A \leq B \leq 10^6$
$1 \leq K \leq 10^6$

解法

$g(n)$ の最大値は $12$ 程度なので,$1\leq K \leq 12$ に対して,$g(n)=K$ となる $x$ 以下の $n$ の数を前計算しておく.
$f(n)$ の値は篩っぽく求めて,$n > f(n)$ なので,$g(n)$ の値はDPで計算できる.

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年程度.

解法

やるだけ.

SPOJ 9861 - Hotels Along the Croatian Coast [HOTELS] (この記事を編集する[管理者用])

Source

SPOJ 9861 [HOTELS]

問題概要

N個 (300000以下) の正整数が与えられる.各正整数は1以上10^6以下.
その連続する部分列の和でM (2^31未満) を超えないもののうち,和の最大値を求める問題.

解法

尺取メソッド.オーバーフローに注意.

SPOJ 10355 - Coin Tosses [COINTOSS] (この記事を編集する[管理者用])

Source

CodeSprint 2 - InterviewStreet Contest
SPOJ 10355 [COINTOSS]

問題概要

表裏がそれぞれ1/2の確率で出るコインを,表がN回 (1000以下) 連続で出るまで投げる.
今,M回連続で表が出ているとする.
終了までに投げるコインの回数の期待値を小数点以下2ケタまで求める問題.

解法

多倍長整数.
収束するまで適当にループを回して規則を探す.

SPOJ 9948 - Will it ever stop [WILLITST] (この記事を編集する[管理者用])

Source

AMPPZ 2011
SPOJ 9948 [WILLITST]

問題概要

初期値n (10^14以下) が与えられた時,以下の操作を繰り返した時がいづれ終了するかどうかを判定する問題.
 nが1以下なら終了する.
 nが2以上の偶数ならnをn/2にする.
 nが2以上の奇数ならnを3n+3にする.

解法

実際にためしてみると,2の冪の時のみ止まることがわかる.

SPOJ 8422 - Maximum Profit [BTCODE_D] (この記事を編集する[管理者用])

Source

Bytecode 2011
SPOJ 8422 [BTCODE_D]

問題概要

M個 (100以下) のレストランがあります.N個 (100以下) のタイムスロットがあります.
各レストランは1個のタイムスロットしかオープンすることができません.
各レストランの,各タイムスロットの,
 ウェイターの数 A[i,j] (5000以下)
 客の数 B[i,j] (5000以下)
 客1人あたりが支払う金額 C[i,j] (10^9以下)
が与えられる.
ウェイター1人あたり1人までしか客をさばくことができない.
レストランに入る合計収入額の最大値を求める問題.

解法

レストランごとに独立に計算するだけ.オーバーフローに注意.

SPOJ 3477 - Baby [BABY] (この記事を編集する[管理者用])

Source

ACM Kanpur 2007
SPOJ 3477 [BABY]

問題概要

N*N (Nは4以上16以下) のチェス盤の2つの盤面が与えられる.
それぞれの盤面にはN個のクイーンが,同じ行,同じ列に高々1個のみ含まれる.
2つ目の盤面はNクイーン問題の解になっている.
さて,1回の手順で,1つのクイーンを上下左右のマスに移動できるとき,1個目の盤面を2個目の盤面に変換するための最小手順数を求める問題.

解法

最小費用流.
問題サイズ的にビットDPでも可能なんだと思う.

SPOJ 402 - Hike on a Graph [HIKE] (この記事を編集する[管理者用])

Source

University of Ulm Local Contest 2000
SPOJ 402 [HIKE]

問題概要

ノード数50以下の無向グラフが与えられる.
全ノード間と,各ノード自分自身との間に枝があり,枝には色が塗られている.
3人の人の初期位置のノードが与えられるので,全員が同じノードに辿りつくまでの最小ステップ数を求める問題.
1ステップでは1人の人が移動でき,その際,移動できる枝の色は,他の2人の位置の間にある枝の色と同じ色しか通れない.

解法

3人がどこにいるか最大50^3の状態数でBFSする.

SPOJ 381 - 106 miles to Chicago [CHICAGO] (この記事を編集する[管理者用])

Source

University of Ulm Local Contest 2005
SPOJ 381 [CHICAGO]

問題概要

ノード数100以下の無向グラフが与えられる.
枝にはその枝を安全に通ることの出来る確率が与えられている.
あるノードからあるノードまで,
1回も危険に晒されずに無事にたどり着くことのできる確率の最大値を求める問題.

解法

ダイクストラ.
各ノードまで安全に行ける確率を求めるとして,確率の最も高いノードから処理していく形.
ノード数が100しかないので,ワーシャルフロイドなどでも可能.

SPOJ 7881 - Ljutnja [C1LJUTNJ] (この記事を編集する[管理者用])

Source

COCI 2010-2011 1-st Round
SPOJ 7881 [C1LJUTNJ]

問題概要

N人 (100000以下) の子どもが欲しがっているキャンディの数が与えられる.
また,キャンディの在庫の総数M (2000000000以下) も与えられる.
得られるキャンディの数が,欲しがってる数よりkだけ小さければk^2だけ怒る.
怒りの総和の最小値を求める問題.
答えは2^64未満となることが保証されている.
在庫は足りてない.

解法

Adhoc.
足りない数をできるだけ均等に割り当てればよいが,欲しがってる数が少ない人は割り当てることができる上限が定まっている.
欲しがっている数が少ない人から,全員に均等に割り当てた時の値,もしくはそれができないなら,割り当てれる上限を割り当てていく.

SPOJ 7805 - Kitchen Robot [KITROB] (この記事を編集する[管理者用])

Source

ACM ICPC 2010, NEERC, Northern Subregional Contest
SPOJ 7805 [KITROB]

問題概要

2次元のx軸,y軸に平行な長方形のテーブルの上に,18個以下の瓶が置いてある.
ロボットは高々1個までしか同時に瓶を運べないとして,ビンを持ってテーブルの端に移動するとテーブルから瓶を落とせる.
全てのビンを落とすまでのロボットの移動経路の最小距離を求める問題.

解法

巡回セールスマン問題っぽくビットDPする.
予め,各ビン間の移動距離は計算しておく.
移動距離の計算は,テーブルの端を経由しなければいけないので,
それぞれのテーブルの辺に対して1点を対称に移動させて距離を計算すれば良い.

SPOJ 7804 - Defense of a Kingdom [DEFKIN] (この記事を編集する[管理者用])

Source

ACM ICPC 2010, NEERC, Northern Subregional Contest
SPOJ 7804 [DEFKIN]

問題概要

w*hの盤面の上に,飛車が何枚か置かれている.
飛車は同じ列,行には高々1枚しか置かれていない.
飛車をおいてる場所,とある飛車から1手で移動できる場所を含まないような,最大の長方形の領域のサイズを求める問題.
wとhは40000以下.

解法

縦横別々に最大の長さを求めてかける.

SPOJ 7775 - Explicit Formula [EXFOR] (この記事を編集する[管理者用])

Source

ACM ICPC 2010, NEERC, Northern Subregional Contest
SPOJ 7775 [EXFOR]

問題概要

0,1の変数が10個与えられるので,全ての2つの変数の組と3つの変数の組のORのXORを求める問題.
陽に書いた式(C言語やJavaに対応した形式)は問題文で与えられている.

解法

問題文の関数をコピーしてサブミットする.

SPOJ 7753 - Happy Numbers II [HPYNOSII] (この記事を編集する[管理者用])

Source

Egyptian Olympiad in Informatics (EOI) 2009, modified ver.
SPOJ 7753 [HPYNOSII]

問題概要

 H(k) = Nの各桁の二乗和
でH(k)を定義する.
2以上2^32未満の整数Nが与えられたとき,Hを何回Nに作用させると1になるか求める問題.
永久に1にならないならそれを指摘する.
テストケースの数は1080000以下.

解法

1回作用させると小さくなるので,小さい値のときだけメモ化しておく.
scanfをgetsにしたら通った.

SPOJ 7733 - Happy Numbers I [HPYNOS] (この記事を編集する[管理者用])

Source

Egyptian Olympiad in Informatics (EOI) 2009
SPOJ 7733 [HPYNOS]

問題概要

 H(k) = Nの各桁の二乗和
でH(k)を定義する.
2以上2^32未満の整数Nが与えられたとき,Hを何回Nに作用させると1になるか求める問題.
永久に1にならないならそれを指摘する.

解法

1回作用させると小さくなるので,一度訪れた数字を全部覚えながら,実際に作用させる.

SPOJ 7718 - Number of common divisors [COMDIV] (この記事を編集する[管理者用])

Source

UODA TST
SPOJ 7718 [COMDIV]

問題概要

2つの整数A,B (それぞれ1000000以下) が与えられるので,両方に共通する約数の数を求める問題.
テストケースの数が1000000個以下.

解法

GCD(A,B)の約数の数が答え.
先にすべての数の約数の数をエラトステネス風に計算しておく.
(scanfをgetcharに書き換えたら通った)

SPOJ 7676 - Sum of Digits [CPCRC1C] (この記事を編集する[管理者用])

Source

http://cs.ikiu.ac.ir/cms/icpc/training/7-contest/86-contest1
SPOJ 7676 [CPCRC1C]

問題概要

a以上b以下の整数を10進数で表記したとき,出てくる数字の和を求める問題.
aとbは10億以下.

解法

各桁ごとに規則性を利用して,どの数字が何回出てくるかを求める.

SPOJ 7380 - Factorial challenge [FUNFACT] (この記事を編集する[管理者用])

Source

SPOJ 7380 [FUNFACT]

問題概要

n!がx桁を超えない最大のnを求める問題.
xは10^9以下.

解法

2分探索する.
階乗の桁数を求めるのは,nが大きい時はスターリングの近似公式を使う.

SPOJ 7210 - Draw Mountains [DRAWM] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2009
SPOJ 7210 [DRAWM]

問題概要

各点の山の標高が与えられるので,点と点の間を結ぶ線を書く事で,山のアスキーアートを書く問題.
高さ0の点は少なくても1個あること,隣り合う標高の差は高々1であることは保証されている.
問題のサンプル参照.

解法

頑張る.

SPOJ 7208 - Black or White [BORW] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2009
SPOJ 7208 [BORW]

問題概要

200要素以下の数列が与えられるので,厳密に増加列になるように黒く塗り,厳密に減少列になるように白く塗る.
(黒く塗られた数字だけ見ると増加列になっている)
塗られていない数字の数を最小にしたとき,最小値を求める問題.

解法

DP.状態は,最後に黒く塗った数字と最後に白く塗った数字で,その後の塗れないものの数の最小値を記憶する.O(n^3).

SPOJ 7191 - Hexagonal Board [HEXBOARD] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2008
SPOJ 7191 [HEXBOARD]

問題概要

サイズnの六角格子のアスキーアートを出力する問題.
問題のサンプル参照.

解法

頑張る.

SPOJ 4303 - Dice [AE2A] (この記事を編集する[管理者用])

Source

Algorithmic Engagements 2009
SPOJ 4303 [AE2A]

問題概要

6面ダイスをn回振って,合計がkになる確率を求める問題.
nとkは10^6以下.
答えは,%表示で,小数部は切り捨てる.

解法

DPする.
そんなに多くの回数を振らないうちに,最頻値ですら1%を切るはずなので,切ったら即座に0%と返す.

SPOJ 7603 - Fibonacci Factor [FIBFACT] (この記事を編集する[管理者用])

Source

ZCon 2006
SPOJ 7603 [FIBFACT]

問題概要

f[k]をフィボナッチ数とする.
f[n]の素因数で,f[1]~f[n-1]までのどの素因数でもないもののうちで,最小のものを求める問題.
存在しないならそれを指摘する.
nの最大値は,答えが2^64を超える入力の最小値未満.
ソースコードの制限は700バイト以下.

解法

nの最大値はそんなに大きくないので,適当に高速な因数分解を使えば答えは求まる.
ただし,ソースコードの制限が厳しいので,答えが変わらないように,適当な方法に切り替える.

Appendix

Recent Articles

ブログ内検索

Ads


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