Le Algorithm

2015年5月5日火曜日

HackerRank : clique

問題

ノード数がNでエッジ数がMのグラフの中で最大クリークの最初サイズを求める問題。

https://www.hackerrank.com/challenges/clique

解法

Turán's theoremというのを使えば、ノード数Nでクリークサイズr+1となるようなグラフのエッジ数の最大値は

で求められるので二分探索。

このようなグラフをTuránグラフと言うらしい。完全r部グラフの形をしている。

2015年5月4日月曜日

VK Cup 2015 - Round 3 : C. Idempotent functions

Problem:

http://codeforces.com/problemset/problem/542/C

Algorithm:

Given some x and do below for many times:
x <- f(x)
Observe the transition of x and find out that there is loop.(the shape is like "ρ")
For example, suppose n=6 and f is
f : i -> i+1 (i=1,2,3,4,5)
6 -> 3
and when x=1, then
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ...
and the loop is 3->4->5->6 -> ...
also, if we start with x=5, then
5 -> 6 -> 3 -> 4 -> ...

when x is in the loop, then x moves only in the loop. So, let k is the length of loop(in this example, k=4) and m is some multiples of k, f^m(x) moves x to x(if x is in the loop).
For x that is not in the loop will go to loop for big k. Let s is minimum number of step that is needed to go to loop for all x.(in this example, 2 steps needed to go loop and s=2), then f^(m+s)(x) moves all points to loop. and this is Idempotent.

And we must be carefull that there is some "ρ".
So, we need s to be the longest "stick" and m to be the LCM of length of loops.

2015年5月3日日曜日

Hacker Rank : Even Tree

問題

https://www.hackerrank.com/challenges/even-tree
木が与えられるので、エッジを取り除いてノード数が偶数であるような木幾つかに分解したいので最も多くエッジを取り除くためにはどうすれば良いかを求める問題。

解法

各エッジに対して「このエッジを取り除いて二つに木を分割した時に双方の木に含まれるノード数がどちらも偶数である」ならば、そのエッジを取り除く。そうでなければ取り除かない
とすれば良い。ノード数が800なので十分間に合う。

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の分を足す必要はないので注意。

(こんな感じ)

2015年5月2日土曜日

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.

2015年5月1日金曜日

AOJ 1195:暗号化システム

問題

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

解法

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