12/27-1/5まで実家に帰ります.

via しかしSVMも最近は速いらしい - 射撃しつつ前転 改 上記の論文の3.1まで読んでL1-Linear SVMを実装してみた．Shrinkingの部分はまだ読んでいない． やっていることは双対問題 を各$\alpha_i$ごとに最小化していて，勾配方向が$w$を保存していると各成分…

ここ2連続ほど500を落としている． 250 Math.atan2を使うだけ，期待値なので各線分ごとに当たる確率をもとめて足すだけ． 500 15分ぐらい読んだけど，問題の意味が全く分からなかった 1000 ある点を左上にして右下方向に長方形を作ることを考えると極大なも…

バックアップのためのbuilt.xmlメモ．texファイルと図をtarで固めてgmailに送る． <project default="main"> <target name="main" depends="compress"> <mail mailhost="smtp.gmail.com" mailport="465" ssl = "on" subject="backup master thesis" user="${mail.username}" password="${mail.password}"> </mail></target></project>

250 個々のセルに対して何個の部分長方形に含まれているのかを数えればよい 500 全部の係数をかけた値をどれか一個の変数に代入して、一次式を解いていけばよい.

250 nextPermutationするだけ 500 解法は思いついたけど時間内にバグが取れなかった。まず高々k種類の文字列を用いて長さnまでの回文の合計を とおく。つぎにちょうどk種類だけ用いて作れる回文の数をg(k)とかくと となる。求める解は となる。 行列乗算でや…

250 いろいろと計算するとgcdをとればよいことが分かる． 600 実験するとdig(x)は循環する*1ことが分かるので、剰余をとるだけなんだけど初期化をミスしてSystem testで落ちる 900 Pでの余りの個数に注目してやると、残り個数の状態(個数に関してソートした…

250 シャッフルをシミュレーションして、出現頻度の高い順にK個とっていけばよい． 500 三分探索.最初EPSを1.0E-9にとってたけどよく考えると結果には×2000できいてくるのに気づいて、アドホックに1.0E-15に訂正して再提出.Challengeフェイズでだれも三分探…

前受けた奴の結果が今日ネットで開示されていた． Listening 450 Reading 360 で思ったよりよかった．

250 状態空間が4^14ありそうだけど,実際はループができない経路というのはそんなにはないのでdfsするだけ. 500 状態空間が25C5=53130通りしかないので幅優先で通るのだけど、なぜか終了状態を定めてそことの距離の最小のものを出すというアルゴリズムを書い…

DO++に紹介してあったleft-leaning red-black treeという赤黒木の一種で実装が簡単なものを実装してみた．get,put,deleteを実装したところ156行となった．アルゴリズムイントロダクションの実装が疑似コードで150行程度なので*1．また，JavaのTreeMapと挿入+…

600より900の方が簡単だったような気がする. 250 9から2まで順番に割っていくだけ. 900 x[i]の取りうる値は多くないので,区間の合計をFenwick木を使って問い合わせればよい.

250 二つの独立な事象A,Bのどちらかがおこる確率は 1-(1-事象Aがおこる確率)*(1-事象Bがおこる確率)で出る 500 まず最初に移動可能な集合とその移動にかかる時間を計算する。あとは入口にいる人の集合と地図がどちらにあるかの状態に関してダイクストラすれ…

250 二分探索。 500 異なる長さの n とりあえず、切るときは等分割にすればよいというのは分かったのだが、そこから最大の長さのピースの部分を固定してとか考えていたら50^2 * 10^5 = 25 * 10^7でJavaだと終わらないよなと思っていた。あとであっている人の…

250 やるだけのはず。実は最長のループがどの程度になるかは見積もれてなかったりするけど。 500 DP。ただし5000*5000の配列を確保しようとするとメモリの確保に失敗して落ちる。 1000 ある金額以上の払い方に関してはとりあえずは最大価値のもので減らして…

210問中200問解いた。レベルが4から5になりました。

250 undoが来たら現在の状態をいままでの状態の中でundoの指定時間より前の最も遅いものの状態に変更すればよい。 500 残りの石と現在のプレイヤーの状態に対して、このままだとどのプレイヤーたちが勝つかという値を返す。注意すべきこととしてゲームが強制…

http://mallet.cs.umass.edu/より class Digamma { public static final double EULER_MASCHERONI = -0.5772156649015328606065121; public static final double DIGAMMA_COEF_1 = 1.0 / 12; public static final double DIGAMMA_COEF_2 = 1.0 / 120; public…

行ってきた。Dのsmallしか解けず惨敗。 D 木が2つ与えられた時に、木Aが木Bに含まれているかどうか判定せよという問題。 smallはNが8個しかないので8!通りラベルづけを試せばよい。 largeはルートをそれぞれの木に対して決めた後、Aのそれぞれの部分木がそれ…

250 N個の数からM個選ぶくじを買ったときK個以上あたっている確率を求めよという問題。N 500 次数2以下のグラフの最大重み独立集合を求めよという問題。次数2以下のグラフは孤立点か直線か円しかなくて、孤立点は単に重みを足してやればよくて、円は適当な一…

250 文字列処理。トータルのスコアを更新するときにprefixのスコアを更新するのを忘れて落とされた。 500 与えられた平面図が立方体の展開図かどうか判定しろという問題。立方体の展開図の形は合同なものも含むと11通り(cf:http://www004.upp.so-net.ne.jp/s…

250 2進数Nが与えられた時にNと1のビットの数の個数が等しいNより大きい最小の数を返せという問題。 数字を配列に直してnextPermutationするだけ。 500 要約すると与えられた数M( 今6つの数を とおく、このとき総和は となり、 とおくと、s

Number MindをMCMCで解いてみた。 方針は与えられた数sに対して、評価関数c(s)を真の正解の数との二乗誤差とおく。今状態sから状態tへの遷移確率を とおいて遷移していく、これを繰り返していくと に従ってsをサンプリングすることができ、c(s)が低いものほ…

250 重い荷物から順にクレーンに割り当てるというのを繰り返せばよい 500 n( なるSを求めよという問題になり、これは になるため、ナップザック問題と等価になる。だから全探索するしかないんだが適当な枝刈りをしただけでは間に合わなくて、n個の集合を半分…

2週間ほど実家に帰っていました、今日戻ってきた。実家にいる間、研究の方を進めようかと思ってたけど、結局オリンピック観戦と小説を読んでただけだった。

500人通過中117位で通過。 D small 典型的DP C small N B small , large (現在地 * 扉1の配置 * 扉2の配置)の状態空間に関して幅優先する。扉の位置が一つの壁に関して4通りあるとか銃を撃つときにはターンを消費しないと色々と条件があり、実装にかなり手間…

250 各項の値からdが入る区間が求まるので、すべての区間の共通部分の左端の値を返す。 500 与えられたi , p , q , x , yに対して を計算しろという問題。ただし p >= 2 , q >= 2 , i そのまま計算するとp=q=2のときiに比例するだけの時間がかかるので sqrt(…

1000人通過中377位で通過。 D-small 最初はAを読んでたけどよくわからなかったのでsmallの点数が5ptだったこれを解いた。k A 各ゲートに対して0,1を取る時のそれぞれの最小回数を下から求めていく。 B-small 最初5重ループとかを書いてみたけど実行時間がか…

C-largeはソートされたリストに対してi番目の要素の検索と要素の削除が効率的に行えるデータ構造があればよい、一般的には赤黒木などの平衡二分木が必要になるんだけど今回の問題は挿入を考えなくてよいので単に子要素がどれだけあるかを保存した二分木をつ…

199位でRound 2に通過。 A 格子点上の点がn個与えられた時に重心が格子点にのるような異なる3点の取り方の数を出せという問題。とりあえずsmallに関してO(n^3)のコードを書いて通しておく。よくよく考えるとx,yに関しての3で割った余りのみ見ればいいことが…