yukicoder No168. ものさし

問題

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

解法

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

yukicoder 158 奇妙なお使い

問題

http://yukicoder.me/problems/125

解法

DP.

f(i,j,k) : 1000円をi枚 100円をj個 1円をk個持ってるときにいける回数とする.

1000円を沢山持ってると後々で困ったりするので、Db円やDc円を払うときは1000円、100円を出来るだけ使うようにする必要がある。つまり払うときの枚数は貪欲にすれば良い。なので、(i,j,k)持ってるときに

・Bさんのとこに行った後の枚数(ib,jb,kb)

・Cさんのとこに行った後の枚数(ic,jc,kc)

を求めると

f(i,j,k) = max(f(ib,jb,kb),f(ic,jc,kc))+1

とすれば求まる。

yukicoder 150 "良問"(良問とは言っていない

問題

http://yukicoder.me/problems/344

要するに入力された文字列sを、

先頭から見たときに"good","problem"がこの順に見つかるようにするためには何文字変更するべきかを求める問題。

100個の100字以内の文字列に対して探さなければならない。

解法

tbl1[i] = str[0~i]の中で"good"とのハミング最小距離

tbl2[i] = str[i~n-1]の中で"problem"とのハミング最小距離

とすると,tbl1[i]+tbl2[i+1]で求めることが出来る。

tbl1[i] = min(tbl[i-1], haming("good", str[i-3~i])

で求められるのでO(4・n) = O(n)

tbl2も同様にして求めることが出来る。

なので全体としてO(n)で求めることが出来る。

yukicoder 134 走れ！サブロー君

問題

http://yukicoder.me/problems/273

解法

bitDP.
解法は問題見てすぐ分かって紙にプログラム書いてバカみたいにたくさんメモリとってたけどまぁなんとかなった。
状態を規定するのは訪問済みノードのbitと今いるノードで十分だけどdfsするときに引数として今の重さを持ってると余計な計算しなくて良いから楽だと気づいた。

yukicoder 106 素数が嫌い！2

問題

http://yukicoder.me/problems/158

解法

エラトステネスっぽくやって各数字の異なる素因数の数を足してく。
布団で問題読んですぐ思いついてすぐ解けた。

yukicoder 64 XORフィボナッチ数列

問題

http://yukicoder.me/problems/119

解法

さすがにすぐ解けた

yukicoder 130 XOR Minimax

問題

http://yukicoder.me/problems/282

解法

最小値を上のビットから求める。

再帰で分割統治法ができる。

yukicoder 136 Yet Another GCD Problem

問題

http://yukicoder.me/problems/254

解法

k個に分割せよって勘違いしてたけどよく見たら2以上k個以下に分割せよだった。
最終的によく考えると入力kは関係ないね

yukicoder 139 交差点

問題

http://yukicoder.me/problems/250

解法

場合分けがんばる

yukicoder 144 エラトステネスのざる

問題

http://yukicoder.me/problems/242

解法

2~Nの間の各数字iに対してPr{iが生き残る}を計算する.

E{残った数字の個数} = Σ( E{1{iが生き残る}}) = ΣPr{iが生き残る}

となるので計算したものの総和でおk.

Pr{iが生き残る}はエラトステネスで倍数のやつに1-p倍するみたいなことをする.

こういう問題をぱっと解けるようになりたい