Entries

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

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

LiveArchive 5002 - The Queue (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5002

問題概要

N (1000以下) 人の上下関係が木で与えられる.
N人の人が一列に並ぶとき,自分の親より前に並ぶことはできない.
並び方は何通りあるか mod 1000000007で求める問題.

解法

N! / 1の子孫の数 / 2の子孫の数 / …

LiveArchive 5001 - Making Quadrilaterals (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5001

問題概要

N (4以上60以下) が与えられる.
N本の正整数の長さの棒の組で,どの4つを取ってきてもその長さの辺を持つ四角形を作れないようにしたい.
そのような集合の中で,最も長い長さの最小値を求める問題.

解法

Greedy.
N=3なら全部1で良くて,N=4からは前の結果の最も長い方から3つの長さの和のものを追加していく.

LiveArchive 5000 - Underwater Snipers (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5000

問題概要

2次元世界で y=k (kは-10^8以上10^8以下) より上(y座標の大きいほう)が陸地で,下が海.
陸地の整数座標にN (10000以下) 人の敵がいる.
射程D (10^9以下) のスナイパーを海の整数座標に配置し,スナイパーを移動することなく敵を全部倒せるように配置したい.
最も上にいるスナイパーのy座標を最小化したい.最小値を求める問題.
全部倒せないならそれを指摘する.

解法

二分探索 + Greedy.
最も上のスナイパーのy座標で2分探索し,スナイパーは全部そのy座標に置けば良い.
後は,スナイパーのx座標をgreedyに決めていく.

LiveArchive 4997 - ABCD Tiles (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4997

問題概要

15*15以下の升目が与えられて,いくつかにAのタイルが敷き詰められている.
問題文の頭の形のタイルB, C, Dが無数に使用できるので,タイルが敷かれてない場所にB, C, Dのいずれかのタイルを敷いて埋める.
タイルは重なってはいけないし,しかれていないマスがあってもいけない.
また,Bのタイル同士,Cのタイル同士,Dのタイル同士が上下左右斜め9マスで接していてはいけない.
敷き詰め方のうち,辞書順で最小のものを求める問題.
不可能ならそれを指摘する.

解法

5マスのタイルの領域に分け,グラフの彩色問題に落とす.
後は全探索しても大丈夫.

LiveArchive 4996 - Scientefic Experiment (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4996

問題概要

0階から卵を落とすと割れない,n (1000以下) 階から卵を落とす問われることを知っている.
また,k階から卵を落として割れるなら,k+1階から卵を落として割れることを知っている.
卵を落とすと割れる最小の階数を求めるために必要な最小コストを求める問題.
卵は1個までしか運ぶことができず,ビルの中で卵はx円で売っている.
結果を見るために落とすとビルから外に出なければいけない.卵が割れずに残っていたら拾わなければいけない.
卵を持たずにビルに入るにはy円かかり,卵を持った状態でビルに入るにはz円かかる.
最終的に,結果が判明したとき,卵が割れずに残っていたらx/2円で売ることができる.(ビルに入ることなしで)

解法

割れるかどうか不確定な階数の幅を状態としてDPする.

LiveArchive 4995 - Language Detection (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4995

問題概要

挨拶が与えられるので,それが何語なのか判定する問題.
何が与えられたら何を返すかという表が問題文で与えられており,それ以外が入力されたらUNKNOWNと返す.

解法

やるだけ.

LiveArchive 4994 - Overlapping Scenes (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4994

問題概要

10文字以下の文字列が6個以下与えられる.
最初は空の文字列で,与えられた文字列を自由な順番でそれに追加していった際に,最終的な文字列の最小の長さを求める問題.
追加する際は,最後に追加するのだけど,サフィックスと追加する文字列のプレフィックスが一致するならそれを重ねて追加する.
追加する際は,最も重なる部分が多くなるように追加する.

解法

実際に6!通りの追加方法を全部試す.
賢くやろうとすると逆に間違えやすいので注意.

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座標が与えられる.
フィールド内の全ての場所が,縦方向,横方向の両方向に線が引かれているかどうか,を判定する問題.

解法

やるだけ.

LiveArchive 4859 - Knockout Tournaments (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4859

問題概要

1回のトーナメントに出場したとき,可能性があるのは以下のとおり
 Round kで敗れた : Round kまで進出とみなす : 勝数k-1 負数1 (k=1,2,3,4,5,6,7,8)
 Round 8に勝った : Round 8まで進出とみなす : 勝数8 負数0
合計の勝数と負数が与えられる.
何回戦まで進出したかの値の平均値を知りたいのだけど,何回トーナメントに出たかわからないので,
何回トーナメントに出たかは,ありうる値を等確率で取るとする.
何回戦まで進出したかの平均値を求める問題.
また,そのような勝数,負数になることがないならそれを指摘する.
勝数と負数は2000000000以下.

解法

結局答えは
 (W+L) * ( H[A]-H[B] ) / (A-B)
の形で書ける.
Wが勝数,Lは負数,Aはあり得るトーナメント出場回数の最大値,Bはトーナメント出場回数の最小値-1,Hは調和級数
 H(k) = 1 + 1/2 + 1/3 + … + 1/k
L=0でWが8の倍数じゃないときのみ不可能.
調和級数は大きい時は近似公式を使う.

LiveArchive 4858 - Digital Matrix (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4858

問題概要

1~Kまでの数字が書かれた正方行列A,Bがそれぞれ与えられる.
1回の操作でAの1つの要素を選び,自由に1~Kの数字に書き換えることができる.
ただし,その操作の後,Aが対称行列になるような操作は認められない.
最小で何回の操作で行列Bと一致させることができるかを求める問題.できないならそれを指摘する.
行列のサイズは100以下.

解法

超adhoc.
まず,A=Bなら0.
Bが対称行列なら不可能.
基本的には,答えは,異なってる要素数だけど,
(i,j)要素と(j,i)要素を入れ替える操作のみ必要で,どれを先にやっても一時的に対称行列になっちゃうなら答えに+1.
また,1個しか入れ替えるものがなく,K=2なら,別のところで対称性を崩して戻さないといけないから+2.
また,サイズが2*2とかで,K=2なら,対称性を崩せないので不可能.
とか色々場合分けする.

LiveArchive 4857 - Halloween Costumes (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4857

問題概要

何枚でも重ねて着ることはできるが,一度脱いだコスチュームをまた着ることはできない.
順番に,いちばん外側に来ている状態にしたい出したいコスチュームの番号が与えられたとき,最小で何着コスチュームが必要かを求める問題.
与えられる番号の数列の要素は100要素以下.

解法

DP.
状態は考える範囲と,その範囲のすぐ外で一番外側に来ているコスチュームの番号.
一見状態数がO(n^3)に見えるが実質O(n^2)しか考える必要がなく,合計の計算量もO(n^3)になる.

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

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4856

問題概要

8*8の障害物のあるフィールドに2*2の物体が4つ置いてある.
上下左右に重力をかけて,障害物かフィールドの端にぶつかるまで物体を動かすことができる.
1回以上,何度でもその操作ができるとき,出来る盤面の種類は何通りあるかを求める問題.

解法

大してできる状態数は大きくないので全パターン試して作ってみる.

LiveArchive 4855 - Hyper Box (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4855

問題概要

与えられたn次元の直方体を,重なりなく,隙間なく,使える直方体で埋め尽くすには直方体が何個必要かを求める問題.
使える直方体は,1辺の長さがフィボナッチ数のもののみ.
与えられる直方体の1辺の長さは2000000000以下で,次元nは15以下.

解法

全部同じサイズの直方体を使う.
次元ごとに分けて考えて,あとでかけ算する.

LiveArchive 4854 - A Digital Satire of Digital Age (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4854

問題概要

天秤のアスキーアートが与えられる.錘はアルファベット大文字.
おもりの重さは,アスキーコードを2進数で表したとき,
 0の出てくる回数×250 + 1の出てくる回数×500.
天秤の釣り合い具合が矛盾がないならそう指摘し,矛盾があるなら正しいアスキーアートを出力する問題.

解法

頑張ってやるだけ.

LiveArchive 4853 - Emoogle Balance (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4853

問題概要

1000要素以下の数列が与えられるので
 正の要素の数 - 0の要素の数
を求める問題.
数列の要素は0以上99以下.

解法

やるだけ.

LiveArchive 4815 - Kids' Wishes (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4815
SPOJ 7760 [MKLAR10] (2010-11-08 3:11追加)

問題概要

N人 (10^9以下) の人が円形に並ぶ.
K個 (10^5以下) の要望があって,それはある人とある人は隣に並びたいというもの.
すべての要望を叶える並び方が存在するかどうかを判定する問題.

解法

連結成分ごとに分けて,次数を調べる.
次数が3以上の人がいたら不可能.
すべての人が同じ連結成分になっておらず,次数が2の人ばかりでも不可能,など.

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

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4814
SPOJ 7761 [MJLAR10] (2010-11-09 04:15追加)

問題概要

2人の人がそれぞれ3つのカードを持っていて,それぞれ1枚ずつ同時に出して,大きい数字の勝ち.
2回勝つと勝利.
1人の人のカード3枚,もう1人の人カード2枚が与えられるので,後者の人がどうやっても勝つようになるために付け加える最小のカードを求める問題.
カードは1以上52以下の整数で,同じカードは1枚しかない.
不可能ならそれを指摘する.

解法

付け加えるカードを全部試して,勝負の際のカードを出す順番も全部試す.

LiveArchive 4813 - Ingenious Metro (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4813
SPOJ 7763 [MILAR10] (2010-11-07 20:21追加)

問題概要

1次元平面上の整数座標の場所に,ワープスポットが100000個以下ある.
ワープスポットを1個選んで,現在位置から,ワープスポットに対して対称な位置に移動できる.
何度でも移動して良いとして,与えられた初期位置から終了位置まで移動できるかどうかを判定する問題.

解法

2つのワープスポットを使うことで,2つのワープスポットの距離*2だけ移動できる.
なので,スタート地点と終了地点の距離が,ワープスポット間の距離のGCDの2倍の倍数であれば移動可能.
また1回の移動で可能な場合も忘れず判定する.

LiveArchive 4812 - Hyperactive Girl (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4812
SPOJ 7759 [MHLAR10] (2010-11-07 20:16追加)

問題概要

[s,t]という形の区間が100個以下与えられる.
[0,M]を埋め尽くすような区間の極小集合の数をmod 10^8で求める問題.
埋め尽くすというのは,0以上M以下の点は選んだ区間のどれか少なくても1個に属している.
極小というのは,選ばれた区間のうち,どの1つを取り除いても,埋め尽くすという条件を満たさなくなること.

解法

終了時間でソートしてあげて,前に使った区間と2個前に使った区間を状態としてDPする.

LiveArchive 4810 - Flowers Flourish from France (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4810
SPOJ 7757 [MFLAR10] (2010-11-07 20:13追加)

問題概要

2個以上の単語からなる文が与えられるので,全部の単語の頭文字が等しいかどうかを判定する問題.
大文字と小文字は区別しない.

解法

やるだけ.

LiveArchive 4808 - Digits Count (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4808
SPOJ 7747 [MDIGIT3] (2010-11-07 20:12追加)

問題概要

A以上B以下の整数を10進数表示したとき,0~9までの数字の現れる回数をそれぞれ求める問題.

解法

桁ごとに見ると出てくる数字に周期性があるのでそれを利用して計算する.

Appendix

Recent Articles

ブログ内検索

Ads


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