2015年5月16日土曜日

ARC 39 B: 高橋幼稚園

問題

http://arc039.contest.atcoder.jp/tasks/arc039_b

解法

n<=kならなるべく均等に配れば良いので、n人にまずk/n個ずつ配ってその後残ったk%n個のアメをn人に配れば良いのでnC(k%n)通り

n>kならばどんなに頑張っても幸福度は0なのでどう配っても良い。この場合は
k個のアメにn-1個の「仕切り」を考えてそれの並べ方を考えれば良い。(仕切りiと仕切りi+1の間のアメの個数が子供iがもらうアメの個数となる)
ので、(k+n-1)!/k!/(n-1)! = (k+n-1)Ck 通りとなる。

ソースコード

https://gist.github.com/knewknowl/f275cbbf7cf65aa3b3ab

2015年5月9日土曜日

AOJ 2586 : 流れ星に願いを

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2586
空間上にn個の球がある。
それぞれの球は速度(vx,vy,vz)で移動し1秒でvrだけ半径が減少し、
二つの球が接触もしくは半径<=0になったらその球は消滅する。

それぞれの球が消滅するまでの時間を求めよ。

解法

まず二つの球が接触するかどうかを判定するために球iと球jのt秒後の距離をf(t)とおくと
f(t)は下に凸な関数になっているので三分探索を使って極小値を求める。この極小値が0以下ならば二つの球は接触するので、極小値を与えるtと0との間で二分探索をすれば良い。

こうすれば接触時間と消滅時間がわかるので、それらの時間をソートして最初に起こるイベントから順に処理していけば良い。

・・・よく考えたら接触時間は二次方程式になるので三分探索する必要はなかった。

ソースコード

https://gist.github.com/knewknowl/9913126a26b210230e4d

2015年5月7日木曜日

AOJ 2584 : Broken Cipher Generator

問題

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

解法

?がついてるところはAにすれば良い。あとは愚直に構文解析するだけ。
構文解析のやり方は
https://gist.github.com/draftcode/1357281
がすごくわかりやすくて良いと思います。

ソースコード

https://gist.github.com/knewknowl/98ba3331fc465b42416c#file-brokenciphergenerator-cpp

2015年5月6日水曜日

SRM 658 Div1 Med : Mutalisk

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13761
n個の箱があってそれぞれの箱にx[i]個の玉が入っている。
1ステップで3つの箱を選択し、
最初に選択した箱から9個以下
2番目に選択した箱から3個以下
最後に選択した箱から1個以下
の玉を取り出すことが出来る。( 例えば玉が6個しかなくても最初に選択して6個取り除いても良い)
全ての箱から玉を取り出すには最小で何ステップ必要かを求める問題。

解法(Div1)

(heekyuさんのコードを参考にしました。とてもシンプルで分かりやすいコードです)
二分探索+DP.
r回で全部なくすことが出来るかどうかをDPで判定する。
dp[f][i][j][k] = x[0]~x[f]までを1をi回,3をj回,9をk回使って全て0以下にすることが出来るかどうか
とすると、
仮に9をa個、3をb個使うとするとx[f]を0にするためには1は x[f] - 9*a - 3*b 個必要になる。この値をneedOneとしてdp[f+1][i-needOne][j-b][k-a]を調べれば良い。
このとき{60}みたいな入力に対しては1と3と9を同時に使おうとして実際の答えは60/9+1 = 7なのに60/(1+3+9)+1 = 5ってなっちゃうのでそこを注意する。
具体的には a+b+needOne <= rかどうかで判定すれば良い
たとえば{60}の例だと
1が5個、3が5個、9が5個で合計15個 > 5=r →はじかれる
1が0個、3が0個、9が7個で合計7個 <= 7=r   →はじかれない

解法(Div2 Med)

Div2Medだとn=3と固定されているので,
dp[i][j][k] = x[0]にi個、x[1]にj個、x[2]にk個入っているときの最小ステップ数
とすれば、1,3,9は3!=6通りの並べ方があるのでそれぞれに対してdp[i-1][j-3][k-9]+1みたいなことをすれば良い。

SRM 658 Div2Hard : OddEvenTreeHard

問題

http://lealgorithm.blogspot.jp/2015/05/srm-658-div1-easy-oddeventree.html
と同じだけど、x[i][j]='?'というのが許されている。(?だとOddとEvenどちらでも良い)

解法

Div1の方とほぼ同じ。
まず対称性の確認とかx[i][i]=='O'だったらはじくとかやって、ワーシャルフロイドでx[i][j]+x[j][k]の偶奇とx[i][k]の偶奇の確認(もしx[i][k]が?だったら埋める)というのをやり、
それでもどこかに?があった場合はまずそれをOにしてみて矛盾する箇所がないか確認して、もし矛盾したらEにする、というのを行うとxから?がなくなるので後はDiv1と同じ構成方法を用いて構成する。

ソースコード

https://gist.github.com/knewknowl/2b26f73992fb90439370

SRM 658 Div1 Easy : OddEvenTree

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13759&rd=16461

偶奇が二次配列で与えられるのでa[i][j]の偶奇とノードiからノードjへの距離の偶奇が一致すうりょうに木を構成する問題。条件を満たす木が存在しなければ存在しないと答える。

解法

まず対称行列になっているか、a[i][j]+a[j][k]の偶奇とa[i][k]の偶奇が一致するかを確かめる(木なのでdist[i][j]+dist[j][k]=dist[i][k]である)

次に,ノードiからノードjへの距離が奇数でありかつiとjが連結でないならば、iからjに枝を張って良い。そしてこの操作を繰り返して木になるならば、それが答えになる。
例えばノード0からスタートして、a[0][i]=Oddとなるようなiに対して0-iで全て枝を張り、張ったiに対してa[i][j]=Oddとなるようなjに対して枝を張り、...ということを繰り返せば良い。

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回、普通の辺は行きと帰りと撤去で3回、スタート地点とゴール地点によっては行きと撤去の2回、の3通りがある。
2回の辺をできるだけ多くしたいけどこれの最大値=木の直径*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通りくらいあるから全試しすれば良い。


解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...