AOJ埋め19

去年のUTPCの分を4問ほど埋めましたが風邪で眠いので書きません.
あみだくじもDPでできそうな気がしたけど実装が難しくて未着手.
→書いた

2190 Angel Stairs

普通にboolでDPしてやると50000^2でどう考えてもTLEなんだけど,boolじゃなくてunsigned long longの各ビットを使うようにすれば1/64の定数項が付くし,それぞれの処理はけっこう軽いから間に合うんじゃね? と思って書いたら間に合ってしまった.
ちょっと嘘解法くさいけどACが出たのでまぁよし.

2191 A Book Shop With a Frequent Greetings

復唱が鳴り止まないときの判定がよくわからんかったけど,N*Y回くらいやっても鳴り止まなかったらYou're always welcome! ってことにしてしまえばいいのでは? と思って書いたらあたった.

2193 The Door into Summer

レノンの扉は,ゴールの扉付近のものと,レノンが最初いる部屋からつながっているもの以外には使っても意味がない(途中でレノンの扉を使っていっても,それはなつめの開けた扉からいくことができるから) .
なので,レノンは「レノンの扉 → なつめがあけた扉 → ゴールにつながるレノンの扉」というルートをたどる.
そこで,なつめの扉のみからなるグラフを作ってBFSで 「ゴールからの各点への最短距離」「レノンからの最短距離」「なつめからの最短距離」をそれぞれ保持しておいて,それらの和が最小になる点(もっとも効率のいい合流ポイント)を探せばいい.これらはO(N)でできる.
コーナーケースとして,レノンが夏の扉のすぐ横にいるケースに注意.

2195 Cat Numbers!

数論.数式をこねこねするとなんか見えてくる.
考えている最中紙出すのがめんどうくさくてずっとノートPCの上で考えていたので,そのメモでも貼っておく.誰得.

A:a桁 B:b桁
(A+B)(B-A+1)/2 = A*10^b+B


A+B=:X
B-A+1=:Y

A=(X-Y+1)/2
B=(X+Y-1)/2

XY=(X-Y+1)*10^b+(X+Y-1)
=X*(10^b+1)+Y*(1-10^b)+10^b-1


XY+bX+cY+d=0 ...?
⇔ (X-u)(Y-v)=z とできるか?<=>XY-vX-uY+uv=z
このようなu,v,zがわかればX,Yがわかる→条件を満たすA,Bのみを吐けばいいことに.

M=10^bとおく

v=M+1
u=1-M
z-uv=M-1

∴z=-M^2+1+M-1
=M(1-M)

zの約数を全部列挙する.
z=fg という分解に対しては

X-u=f
Y-v=g

より,X=f+u,Y=g+v という解が得られる.これよりA,Bを復元し,条件を満たせているかを確認するとよい.


…問題はzの約数の個数だが,これはとてもたくさんになるかもしれない(ので工夫しとかないとしぬかも)
素因数分解は,Mは自明,M-1は,分からないけど10^7までのふるいでなんとかならんだろうか.なるよね,というかなんとかなれや. => (10^16-1),(10^15-1) が問題.でもなんか大丈夫じゃね? => 大丈夫でした.


☆ で,これあってんの?
a=b=1のとき:(X+9)(Y-11)=-10*9
A,B=1,5 のとき X=6,Y=5 15*(-6) はい
A,B=2,7 のとき X=9,Y=6 18*(-5) はい
よさそう….


めんどいところ:約数がオーバーフローする.(オーバーフローするようなものは解になりえないので列挙しない.)
sとtをかけてオーバーフローするかどうかの判定はむずいけど,適当でもいいんなら最高位のビット(対数)をとって判定すると楽そう.対数が足して63を超えるなら確実にオーバーフローするのでやらない,とかで.
が,それを除けばM(1-M)の約数を全部列挙すればいいだけなので割と楽ではあるかも.