Le Algorithm

2015年4月30日木曜日

AOJ 1194:バンパイア

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

解法

二分探索。

ビルのx座標が整数値でしかも絶対値が20以下なので

H[i] = 区間[i,i+1]のビルの最大値

とおいてt秒あとの区間[a,a+1]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。

2015年4月28日火曜日

SRM Div2Med ProblemSetsEasy

div1easyと同じだった(div2の方が制約が簡単)

問題

easy用に使える問題がE個

easyもしくはmed用に使える問題がEM個

med用に使える問題がM個

medもしくはhard用に使える問題がMH個

hard用に使える問題がH個

ある。

これらからeasy問題、med問題、hard問題の問題セットをいくつ作ることができるか

解法

二分探索。なぜか落ちてて悲しかった。

2015年4月26日日曜日

TCO 15 1B Med The Tips

問題

n個の宝を探す宝探しゲームをする。
ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。

見つけられる宝の個数の期待値を求める問題。

解法

i番目の宝が見つかる確率をp[i]とおく。

G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。

この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。

2015年4月24日金曜日

yukicoder No168. ものさし

問題

http://yukicoder.me/problems/296
頂点1から頂点nまでの任意のパスに含まれる全ての辺の中での最小の長さを10単位で切り上げする問題。

解法

ダイクストラっぽくやりました。
精度が怖いのでlong longで距離をとって平方根は二分探索でとりました

2015年4月13日月曜日

http://codeforces.com/problemset/problem/534/D
n人の人がいて、適当な順番で部屋に入る。部屋に3人以上いたら、適当な3人組は部屋の外に出て行ってよい(出て行ったら二度と部屋に来ない)(出て行かなくても良い)
どの人も、部屋にx人いたらx人全員と握手をする。
さて、それぞれの人が「何人と握手したいか」という希望を入力として与えられるとき、全員の希望を満たすような部屋の入り方の順番はあるかどうか。あったらその順番を出力せよ。

解法

「希望人数が多い人」から握手させていけば良い。

CF 534C. Polycarpus' Dice

問題

http://codeforces.com/problemset/problem/534/C
n個のサイコロがあってサイコロiの目は1〜diのいずれかが出る。
このn個のサイコロをふって出た目の総和がAだとする。
このとき、各iに対して「サイコロiの出た目の数としてあり得ない目の数」の種類数を求める問題。
例えば、普通の6面のサイコロを2個ふってその目の和が8だったら、どちらのサイコロも1の目が出ることはあり得ないため、答えは{1,1}となる。

解法

各サイコロiに対してその目の出うる目の数の下限と上限を考える。
「サイコロiがxを出して他のサイコロが全部本気出してもAには届かないよなぁ」
というxのうち最大のもの+1が下限で、これをx1
「サイコロiが本気出してyの目が出たとき他のサイコロが全部1の目になってもAより大きいなぁ」
というyのうち最小のもの-1が上限(の候補の一つ)で、これをy1
とおくと、
サイコロiのでうる目の値は
[max(1,x1) , min(y1,di)]
となる。あとはdiからこの区間内の整数の個数を引けば良い。

ただしn=1の時はA=出たサイコロの目のはずなので、di-1を出力すれば良い。

GCJ Qualification Round 2015 Problem C. Dijkstra

問題

i,j,kのみで構成されたL文字の文字列sをX個連結した文字列を適当に3つに分割して、
「分割した部分文字列の各要素を四元数として見て積をとると順にi,j,kとすることが出来るかどうか」
を判定する問題。
例えば、
L=2,X=6,s="ji"のとき、連結して出来た文字列は
jijijijijiji
であるが、これを
jij | iji | jijiji
と分割することによってそれぞれの積をとるとi,j,kになるので答えはYESとなる。

制限

テストケース数<=100

L<=10000
L*X<=10000(small)
L*X<=10^16(large) , X<=10^12(large)

解法(small)

以下の性質を利用する。
・a,b,cが四元数のとき(a*b)*c=a*(b*c) (四元数の結合則)
連結して出来た文字列をtとしたとき、
t = ○ | △ | □
と分割してそれぞれの積が順にi,j,kとなっているならば
○*△=(○の積)*(△の積)=i*j=k
○*△*□ = (○*△)*(□の積) = k*k = -1
となるはず.
よって、連結して出来た文字列を順に掛けて行って途中でi,kが出てかつ全部掛けたら-1になっていれば良いのでO(L*X)で出来る。

解法(large)

以下の性質を利用する。
・四元数の要素である1,-1,i,-i,j,-j,k,-kはどれも4乗すると1になる。
sをX個連結した後に3分割するので、各分割の中にはsがそれぞれ幾つか含まれていなければならない。その個数をそれぞれa,b,cとする。また、sの文字を全て掛けたものをhとおく。この時、
・最初の分割の積=h^a * (sの途中までの積) = i
・真ん中の分割の積=h^b * (sの途中から別のsの途中までの積) = j
・最後の分割の積=h^c * (sの途中からsの最後までの積) = k
みたいな感じになる(厳密にはa+b+c=X-2やa+b+c=X-1の場合等がありえる)
そしてh^4=1なので、a,b,cは4で剰余をとってよかったりする。
そう考えると考えるべき状態数は
a,b,cが0,1,2,3のそれぞれの場合について考えれば良いのだから、
X = min(X, 12+X%12)
として良い。こうするとX<24だから十分間に合う。