Search on the blog

2013年4月29日月曜日

ボタン風横並びリストの幅を調整する

VPSで借りてるサーバーのトップページのボタンがいまいちイケてなかったので微調整しました。

どうイケてなかったかというと、
iPhoneで見ると下のように表示されてました。


横並びボタンが2列になっています。
原因は、スタイルシートでwidth=250;と決め打ちしていたからで、幅が狭いウィンドウで見ると2列になってしまっていました。

jQueryをつかって、初期表示時とウィンドウのリサイズ時に、ウィンドウ幅を取得してボタンの幅と一番左のボタンの位置を動的に変えるようにしてみました。

具体的に言うと、
  • ボタンの幅 = ウィンドウ幅 / (ボタンの数 + 1)   
  • 左端ボタンの位置 = (ウィンドウ幅 - ボタンの幅 * ボタンの数) / 2
という処理を$(document).ready()と$window.resize()内で行うようにしました。

結果は、以下のとおり。ボタンが1列に並んでいます。
PCで見る場合もwindowのサイズに応じてボタンの配置を調整してくれるようになりました。



非減少列の数

この前のCode Jamの問題で、非減少列の数って意外と少ないんだなと思ったので、どれくらいあるのか調べてみた。

せっかくなので、問題を設定して解いてみることにする。

{0,1,...,9}からなる長さNの列Aのうち、Ai <= Ai+1となるものの個数を求めよ。

まあ普通に考えると、DPだよね。

import java.util.Scanner;

public class Main {
 Scanner sc = new Scanner(System.in);
 
 public static void main(String[] args) {
  new Main().solve();
 }
 
 public void solve() {
  int N = sc.nextInt();
  
  long[][] dp = new long[N+1][10];
  dp[0][0] = 1;
  
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < 10; j++)
    for (int k = j; k < 10; k++)
     dp[i+1][k] += dp[i][j];
  }
  
  long ret = 0;
  for (int i = 0; i < 10; i++)
   ret += dp[N][i];
  
  System.out.println(ret);
  
 }
}

しかしよくよく考えると、組み合わせ論を使って解けるな。ということで以下の式を導き出した。

これを実装すると、以下のようになる。(多倍長整数が面倒いのでPythonで。)

def fact(x):
    if x < 2:
        return 1
    return x * fact(x-1)

def comb(x, y):
    return fact(x) / fact(x-y) / fact(y)

def homog(x, y):
    return comb(x+y-1, y)

def solve(n):
    return sum ([comb(10, x) * homog(x, n - x) for x in range(1, min(10, n)+1)])

if __name__ == "__main__":
    n = int(raw_input())
    print solve(n)

DP解を使って検算したので、多分導いた式は正しいと思う。(追記: いや何やってんだ。これ。10Hnでおしまいじゃん!)

で、以下が長さNの非減少列の個数。非減少じゃないものも合わせた列の個数は10Nだけど、それに比べるとずっと小さい数におさまっている。

N 個数
5 2002
10 92378
15 1307504
20 10015005
25 52451256
30 211915132
うーん、なんか感覚的にすっきりしないな。
今見ている要素より上にいく確率を1/2、下にいく確率を1/2とすると、ずっと上に行きつづける確率は(1/2)Nで、これだとパターン数がおよそ5Nだけど、実際はこれよりもっと小さい。
いや違う、上に行きつづけるからどんどん数字が大きくなってきて最終的には、上に行く確率が(1/10)に近づくわけか。そう考えると納得できる気がする。

Cayley’s Formula

「頂点の数がn個あるラベル付き木の種類は、nn-2個」らしい。

この公式は、Cayley’s Formulaと呼ばれている。

証明は、木の集合Tとprufer sequenceの集合の間にbijectiveな関数が存在することを使って、prufer sequenceの要素数を数えればいい。

ここに分かりやすい証明がある。

自分で証明したときは、関数fがbijectiveであることを示すために、fがinjectiveであることとsurjectiveであることを示したけど、上のpdfにあるように、ある関数fとfの逆関数が存在するって示せば十分なのか。逆関数があるってことはfはinjectiveじゃないといけないし、f: x -> yとして任意のy'に対してx' = f-1(y')がf(x') = y'を満たすからfはsurjective。

最後に(というかこれがこの公式を知るきっかけとなったのですが)、Cayley’s Formulaを使うとエレガントに解ける問題を紹介します。

Codeforces #177 Polo the Penguin and Houses


Javaで配列の初期化、配列のコピー

C/C++のmemset、memcpyに相当するものは、Javaでどう書くか。

まず、配列の初期化。

import java.util.Arrays;

public class Sample {
 public static void main(String[] args) {
  int[] a = new int[5];
  
  Arrays.fill(a, 7777);
  
  System.out.println(Arrays.toString(a));   // [7777, 7777, 7777, 7777, 7777]
 }
}

次に、配列のコピー。
import java.util.Arrays;

public class Sample {
 public static void main(String[] args) {
  int[] a = {1, 2, 3};
  
  int[] b = Arrays.copyOf(a, a.length);
    
  System.out.println(Arrays.toString(b));   // [1, 2, 3]
 }
}

なるほど。

2013年4月27日土曜日

Google Code Jam 2013 Round 1A

Round 1Aがありました。
上位陣のソースを見て復習しました。

Problem A. Bullseye
二分探索の問題。 i番目(i=1,2,...)の黒い円の面積は、Si = (2 * r + (4 * i - 3))πと表すことが出きるので、円をN個塗った場合の面積の合計値は、ΣSi = (2 * N2 + (2 * r - 1) * N)πとなる。 Nが決まれば面積が決まり、塗料が足りているのかどうかはO(1)で判定できる。よってNを二分探索で決めればいい。



Problem B. Manage your Energy
動的計画法で解く。今i番目までのタスクが最適にこなされているとする。
そこに(i+1)番目のタスクを加えたときに、i番目までの解を後ろから走査していきより(i+1)番目のタスクに多くのエネルギーを使った方がいいのかどうかを見ていけばいい。



Problem C. Good Luck
確率の問題。観測される積の列がprとなる確率をp(pr)とおく。選ばれたカードの集合がxとなる確率をp(x)とおく。事後確率p(x | pr) = p(pr ∧ x) / p (pr)が最大となるようなxを出力すればいい。p(pr)はxによらず一意なので、p(pr ∧ x)が最大となるようなxを計算する。計算量を減らすためにxのpermutationは考えずに、xが非減少列となるようなものだけを考えて、確率を計算するときにpermutationを数えてあげるといい。

2013年4月21日日曜日

1/xの和とlog x

とある問題をといているとき、計算量の見積りに



を使う場面があった。

log(x)は1/xの原始関数なのでまあそうなるのは分かるけど、xがどれくらい大きいと上式がどれくらいの正確さで成り立つのか実験してみた。

x log(x) sum(1/x)
1 0 1
10 2.303 2.929
100 4.605 5.187
1,000 6.908 7.485
10,000 9.210 9.788
100,000 11.51 12.09
1,000,000 13.82 14.39
10,000,000 16.12 16.70
100,000,000 18.42 19.00
1,000,000,000 20.72 21.30

そうか、いや、まあそうなるよね。。logだからね。
計算量の見積りという観点では、誤差とか気にするようなレベルではないか。

2013年4月20日土曜日

Kindle Paperwhite買いました

本棚がいっぱいになってきたので、そろそろ電子書籍に乗り換えようと思いKindle Paperwhiteを買いました。
予想以上のクオリティの高さと、予想以上のお得感を感じられたので、軽く宣伝します。


ディスプレイがきれいすぎる
Kindleを箱から取り出すと、何やらディスプレイにフィルターみたいなのがはってあります。
注意書き的なことが書いてます。 とりあえずフィルター外すかと思って剥がそうとしても剥がれない。。

「何だこれ。」

って思ってとりあえず電源を入れてみると、・・・・・

 えっ。。 えっ。。。。。 

てな感じになります。 こんなにも綺麗に文字が表示されるのかと衝撃を受けました。

無料で読める
Amazonのkindleストアに行くと、無料で読める書籍が見つかります。青空文庫みたいなかんじです。とりあえず、
  • こころ
  • 変身
  • 檸檬
  • 人間失格
  • 蟹工船
あたりをダウンロードしました。なんかもうこの時点で、もとは取ったなみたいな感じになりました。

伊坂幸太郎の作品が読める
日本だとKindle版のコンテンツは少ないかなと思っていましたが、伊坂幸太郎の作品はほぼすべてKindle版で揃ってます。とりあえず大人買いして全作品コンプリートでしょ。

辞書が入っている
英語の辞書が2つ入ってました。OxfordとNew Oxford。 iPhoneに英英辞書を入れようかなと思っていましたが、買う手間が省けました。ディスプレイサイズ的にも辞書系はiPhoneよりKindleの方がいいかな、と思います。

どこまで読んだかすぐ分かる
すごい高級機能というわけではないですが、前回読み終わったところをすぐ表示してくれるのはうれしいです。あと全体の何パーセントまで読んだかも表示されます。これも使ってみると地味にうれしい機能。

2013年4月14日日曜日

Google Code Jam 2013 Qualification Round

Code Jamの予選がありました。通過できました。
今年の目標はRound3進出です。

Small Large Large(2)
A AC AC N/A
B AC AC N/A
C AC AC WA
D AC WA N/A
という感じでした。簡単に各問題を振り返ってみます。

A. Tic-Tac-Toe-Tomek
4*4のマス上で四目並べみたいなことをやります。ある局面におけるマスの状態が与えられるので、
  • プレイヤーXの勝ち
  • プレイヤーOの勝ち
  • 引き分け
  • ゲーム続行中
のいずれかを判定せよ。

実装するだけです。


B. Lawnmower
芝刈り機で芝生を刈る。芝刈り機は直線にしか進めない。
芝生の状態が与えられるので、芝刈り機を使ってその状態をえることができるかどうか判定せよ。

まず、同じ直線上を何度も刈るのは意味がない。(一番深く刈る設定で1回刈ったのと同じだから)
次に、各ラインを刈る順番に意味があるかどうか考える。互いに平行するラインはどの順序で刈っても結果に影響ないのは自明。互いに交わるラインの順序についても、交差するセルの芝生の高さはがより小さい高さ設定のものになることを考えると、結果に影響がないことが分かる。

よって、まずhorizontalなラインを上から下に矛盾の無いように走査して、そのあとverticalなラインを左から右にかけて矛盾の無いように走査して、それが目的のパターンと合致するかどうか調べればよい。


C. Fair and Square
閉区間[A, B]において、回文数であり、かつ回文数の平方であるような数の個数を求めよ。

SmallとLargeは、あらかじめsqrt(Bのとりうる最大値)までループを回して、回文数の二乗を配列に格納しておけば解けました。

問題は、large-2。よく分からん。Largeでできた配列の中身をprintfしてみると、各桁で使える数は0,1,2と限られてそう。あと二乗したときに桁で繰り上がりがおこるようなものは回文数にはならないので、このあたりをうまく使えば解けそうか・・と思ったけど結局解けませんでした。


D. Treasure
宝箱とそれを開けるために必要な鍵、および、宝箱の中に入っている鍵の情報が与えられる。すべての宝箱を開けるためにはどの順番で開ければよいか求めよ。

初見は、グラフに帰着させてマッチングっぽいことをやるのかなという感じだった。しかしうまく問題をグラフに落とし込むことができず断念。

とりあえずSmallは単純なビットDPで解けそうだったので、解いてみた。
Largeは、もしかしたら、うまく枝刈りすればDFSで解けそうな気がするのではと思ったけど多分無理そうだったので、諦める。

2013年4月2日火曜日

Facebook Hacker Cup 問題集

探すの面倒くさいので、リンクをまとめておく。

Hacker Cup 2011


Hacker Cup 2012


Hacker Cup 2013