AOJ 1196 : 橋の撤去

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196
簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。

解法

どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で３回、スタート地点とゴール地点によっては行きと撤去の２回、の３通りがある。
２回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。

GCJ 1B: A. Counter Culture

問題

自然数xに対して
・1増やす
・10進表示を逆順にする
という操作を任意に行うことが出来る。
1からスタートして入力nまでたどり着くまでに最小で何ステップ必要か。

解法

nが1桁だったらそのままnを出力すれば良い。
逆順にしても桁数が減るわけではないので一桁ずつ減らして行くことを目標に考える。
つまり入力nがm桁だとすると、n を 10^(m-1) -1 に持って行くまでに最小で何ステップ必要かを考える。そのためにはデクリメントを出来るだけ少ない回数適用すれば良いが、色々考えてみるとnの10 進表示を2等分して、後ろの方を00…01の形にした後にreverseして前者を00…1にすれば最終的にnは100…001の形になって2回デクリメントすて1桁減らすことが出来る。
つまり、nを二等分して前半をreverseして得られる数字、後半の数字をそれぞれ求めてそれらを00…01にするまでに必要なステップ数(求めた数字-1) + 1(reverseの分) + 2(99..99にするのに必要な分)
を求めた後に99…99をまた再帰的に求めれば良い。
しかしnが例えばn=100321とかだとreverseの分を足す必要はないので注意。

(こんな感じ)

Hacker Rank : Wet Shark and Two Subsequences

問題

https://www.hackerrank.com/challenges/wet-shark-and-two-subsequences
n項の数列{x_i}とrとsが与えられるので、
以下の条件を満たす数列の部分集合A,Bがいくつ存在するかを求める問題
・|A|=|B|
・sum(A)+sum(B)=r
・sum(A)-sum(B)=s

解法

sum(A)=(r+s)/2

sum(B)=(r-s)/2

となるのでdp[i][j][k]=i番目までの和がjとなるようなサイズkの部分列の個数

してdp.

AOJ 1195:暗号化システム

問題

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

解法

インクリメントするのは2^n通りくらいあるから全試しすれば良い。

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]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。

SRM Div2Med ProblemSetsEasy

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

問題

easy用に使える問題がE個

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

med用に使える問題がM個

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

hard用に使える問題がH個

ある。

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

解法

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

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がどれも見つからない)」なので余事象で簡単に計算できる。