Entries

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

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

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%と返す.

Beta Round #41 D問題 - Strange town (この記事を編集する[管理者用])

Source

Codeforces Beta Round #41 D問題
Problem description
Beta Round #41の自分の参加記録

問題概要

Nノードの完全無向グラフがある.
各枝の重みは1以上1000以下.
Nノードを1回ずつ通る全てのサイクルの重みは等しい.
Nが与えられたとき,そのような重みを1つ求める問題.
Nは20以下.

解法

各ノードに重みnode[i]をつけて,ノードiとノードjの間にはnode[i]+node[j]の重みの枝をはれば良い.
すると,1周すると,各ノードは入って出ていくので,重みの和はΣ2node[i]となる.
後は,全ての枝が異なる重みになり,全ての重みが1000以下となるnode[i]を見つけるだけだけど,適当に小さいほうから探していくと見つかる.(プログラムに探索させる)

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

続きを読む

Beta Round #41 C問題 - Safe cracking (この記事を編集する[管理者用])

Source

Codeforces Beta Round #41 C問題
Problem description
Beta Round #41の自分の参加記録

問題概要

4つの10億以下の正整数が円状に並んでいる.
隣り合う2つの要素を選んで以下の2つの操作のどちらかができる.
 両方に1を足す
 両方とも偶数なら,両方を2で割る
全部1にする手順を1つ求める問題.最小手順である必要はないが1000手以下でなければならない.
できないならそれを指摘する.

解法

Adhoc.不可能な場合はない.
偶数同士を見つけたら割る.奇数同士(両方1でない)なら1を足して割る.
そういうペアがないなら,2回足して,+1 +2 +1という風にするなど.

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

続きを読む

Beta Round #41 B問題 - Game of chess unfinished (この記事を編集する[管理者用])

Source

Codeforces Beta Round #41 B問題
Problem description
Beta Round #41の自分の参加記録

問題概要

白い駒がキング1個,ルーク2個,黒い駒がキング1個与えられる.
キングは8方向で接してる関係にはない.
白がチェックメイトしている状態かどうかを判定する問題.
チェックメイトとは,
 現在白が1ターン動くと黒が取られる状況 かつ
 黒がどこに移動しようが,次のターンに白が黒を取れる
という場合.

解法

要するに,黒い駒が,1マス動くor動かない場合,全部白に取られるならばチェックメイトと出力する.

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

続きを読む

Beta Round #41 A問題 - Guilty - to the kitchen! (この記事を編集する[管理者用])

Source

Codeforces Beta Round #41 A問題
Problem description
Beta Round #41の自分の参加記録

問題概要

N種類の材料を混ぜて何かを作る.
作るのに必要なN種類の材料の比と,在庫が与えられるので,作れる最大量を求める問題.
フライパンの容量も与えられて,それ以上は作れないという制約もある.
Nは100以下.

解法

在庫量/使う比率の最も小さいものが最初になくなるので,それがなくなるまで作る.
それがフライパンの容量を超えていたら,フライパンの容量にする.

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

続きを読む

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

SPOJ 764 - Delay-noise Analysis [MIS] (この記事を編集する[管理者用])

Source

ZCon 2006
SPOJ 764 [MIS]

問題概要

ノード数250以下の無向グラフが与えられる.ノードには重みが付けられている.
いくつかのノードを選び,そのノードからなる部分グラフには枝が含まれないようにしたい.
そのようなノードの選び方のうち,ノードの重みの和の最大値を求める問題.

解法

枝刈り+全探索する.

SPOJ 244 - Internally Stable Sets [INTSS] (この記事を編集する[管理者用])

Source

ZCon
SPOJ 244 [INTSS]

問題概要

ノード数200以下の無向グラフが与えられる.ノードには重みが付けられている.
いくつかのノードを選び,そのノードからなる部分グラフには枝が含まれないようにしたい.
そのようなノードの選び方のうち,ノードの重みの和の最大値を求める問題.

解法

枝刈り+全探索する.

LiveArchive 4951 - Stock Prices (この記事を編集する[管理者用])

Source

Europe - Northwestern (Nuremberg, Germany) - 2010/2011
UVa: NWERC Regional Semilive (2010-11-21) (blog)
LiveArchive 4951

問題概要

ある品物に対して,何円で何個売りたい,何円で何個買いたい,というオーダーが時系列順に与えられる.
買いたい額の最大値が,売りたい額の最小値以上であれば,売りたい額の最小値で取引が成立する.
各段階で,書いたい額の最大値,売りたい額の最小値,最後に成立した売買の価格を出力する問題.

解法

シミュレーションする.

LiveArchive 4949 - Risk (この記事を編集する[管理者用])

Source

Europe - Northwestern (Nuremberg, Germany) - 2010/2011
UVa: NWERC Regional Semilive (2010-11-21) (blog)
LiveArchive 4949

問題概要

100ノード以下の無向グラフが与えられる.
各ノードは自分が占拠してるか,相手に占拠されてるかで,自分が占拠してるノードは,自兵の人数が与えられる.
各兵士は,どういう順番でもいいので,隣り合うノードに移動するか,今のノードに留まることができる.
敵が占拠してるノードに隣接するノードの兵士の数の最小値を最大化する問題.

解法

2分探索+最大流.

LiveArchive 4948 - Rankings (この記事を編集する[管理者用])

Source

Europe - Northwestern (Nuremberg, Germany) - 2010/2011
UVa: NWERC Regional Semilive (2010-11-21) (blog)
LiveArchive 4948

問題概要

n人 (500以下) の人がいて,強さが完全に順序つけられている.
つまり,DAGで,枝数n(n-1)/2のグラフが与えられる.
そのグラフ上で,いくつかの枝をひっくり返す操作が与えられる.
その後で,順位を順序付けようとすると,順序つけれるならその順序が確定する範囲で求める.
矛盾が発生するならそれを指摘する問題.

解法

枝数がn(n-1)/2なので,順序つけれるなら全て確定.
トポロジカルソートする.

LiveArchive 4946 - High Score (この記事を編集する[管理者用])

Source

Europe - Northwestern (Nuremberg, Germany) - 2010/2011
UVa: NWERC Regional Semilive (2010-11-21) (blog)
LiveArchive 4946

問題概要

1000文字以下のアルファベット大文字の名前が与えられるので,名前入力に必要なキー操作の数の最小値を求める問題.
最初は,全部Aからなる,名前と同じ長さの文字列が入力されていて,カーソルは最初の文字にあっている.
上下キーを1つ押すと,アルファベットが1つ増える(A→B,G→H,Z→A)か1減らす(T→S,A→Z)ことができる.
左右キーを1つ押すと,カーソルが1つ右か左に行ける.一番右から一番左へ,一番左から一番右へも行ける.

解法

最初右にどれだけいって,その後左にどれだけいくかを全探索する.(カーソルがいかない部分が全部Aなら端折れる)
後は,各文字は1文字ずつ上か下か近い方に動かす.

LiveArchive 4944 - Fair Division (この記事を編集する[管理者用])

Source

Europe - Northwestern (Nuremberg, Germany) - 2010/2011
UVa: NWERC Regional Semilive (2010-11-21) (blog)
LiveArchive 4944

問題概要

n人 (100以下) で合計p円 (1000000以下) を支払いたい.
各人が支払える上限額が与えられるので,最も公平に各人支払うお金の額を求める問題.不可能ならそれを指摘する.
各人が支払うお金は正の整数で,公平の基準は以下の通り.
 最も支払う額の大きい人の額を最小化する.
 その中で,1番目に多く支払う額と,最も支払う額の少ない人との比を最小化する
 その中で,2番目に多く支払う額と,最も支払う額の少ない人との比を最小化する,以下同様にn-1番目まで.
 その中で,リストの最初の方にいる人が,できるだけ多く支払う.

解法

最も多く支払う額を2分探索で求める.
後は,適当に順番付けて,最も多く支払っている人のを1ずつ引いていく.

LiveArchive 4961 - Assembly line (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4961

問題概要

200文字以下のアルファベット小文字からなる文字列Xが与えられる.
隣り合う2文字を別の文字に置き換えるコストが与えられる.
(任意の2文字に対して1つの規則が与えられ,置き換わる文字とコストが指定される)
Xを1文字にするまでに必要なコストと,最終的な文字を求める問題.
コスト最小の最終的な文字の候補がいくつもあるなら,与えられた順番で一番早いのを返す.

解法

どの区間をどの1文字にするのに必要な最小コストをメモしてDPする.

LiveArchive 4959 - Jumping monkey (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4959

問題概要

ノード数21以下の無向グラフが与えられる.
最初,どこかに猿がいる.
毎ターン,ノードを1つ指定して,そこに猿が入れば終了.
そうでなければ,猿が隣接する何処かのノードに移動する.
最悪ケースで,最も早く猿のいる場所が当たるような選ぶノードの列を求める問題.
永久に猿に逃げられる場合があるならそれを指摘する.

解法

どこに猿がいる可能性があるか2^21個のノードを作って,そのグラフ上でBFSする.

LiveArchive 4957 - Fake scoreboard (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4957

問題概要

nチームでm問題のプログラミングコンテストが行われた.
各チームが解いた問題数,各問題が解かれたチーム数が与えられるので,どのチームがどの問題を解いたかという表を求める問題.
答えが存在しないならそれを指摘し,複数存在するなら辞書順で最小のものを求める.
nとmは80以下.

解法

答えが存在するかどうかは最大流で判定できる.
後は,1つ1つ決めつけて,最大流を流して,それでも可能かどうかを判定することで辞書順最小のものを復元する.
毎回最初から最大流を流すとTLEなので,前流した結果を修正して次に使う.

LiveArchive 4956 - Comparing answers (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4956

問題概要

意訳して書く.nは1000以下.
各要素が0以上10以下のn*nの行列A, Bが与えられるので,A^2=Bかどうかを判定する問題.

解法

行列積を計算するとO(n^3)でTLE.
乱数のベクトルxを用意して,A(Ax)=Bxかどうかを判定する.

LiveArchive 4954 - Lawn mower (この記事を編集する[管理者用])

Source

Europe - Southwestern (Madrid, Spain) - 2010/2011
UVa: SWERC Contest (2010-11-27) (blog)
LiveArchive 4954

問題概要

長さ75×100のフィールドに,辺に平行に,幅wの線を引く.
線の向き,線の中心のx座標かy座標が与えられる.
フィールド内の全ての場所が,縦方向,横方向の両方向に線が引かれているかどうか,を判定する問題.

解法

やるだけ.

Appendix

Recent Articles

ブログ内検索

Ads


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