Sticks(10) - カメヲラボ
最短コード250B 270byteあたりからは、ロベールさんと私でじわりじわりと削り合い。ちなみに、前回までで紹介しているコードは、はてな用に私が新しく書きなおしたものなので当時のコードとは違う部分もある。どんなインプットでも通るコードというのは、実は260byteくらいまでしか短縮することが出来ない。それ以上縮めるには探索時間やメモリを犠牲にしていかなければならないのだ。 260byte程まで縮んだところで、ロベールさんがTLE(Time Limit Exceed)に掛からない程度に探索ループを書き換え254byte。そして私がそこからさらに短縮して251byte。 L,F,*I; c(n,l,p,j){ --I[p]; for(j=l-=p;F*j;--j)I[j]&&c(n,l,j); for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j); ++I[p]; }
Sticks(9) - カメヲラボ
意外と読める超短いコード 昨日のコードをさらに短くすると以下のようなコードになる。ここまでくると変数名を一文字にした方が逆に読みやすい。え？読みにくい？そうですか..(´ω｀) int L,F,*I; c(n,l,p,j){ --I[p]; F=n?F:0;for(l-=p,j=l<p?l:p;j;--j)F*I[j]&&c(n,l,j); for(j=50;!I[j];)--j;l||c(n-1,L,j); ++I[p]; } main(s){ for(;s;L&&printf("%d\n",L-1)){ int w[51]={s=F}; scanf("%d",I=w); for(;w[0]--;++w[L],s+=F<L?F=L:L)scanf("%d",&L); for(L=F;F;++L)s%L||c(s/L,L,F); } } if文の代わりに&&や||を使うのはコード短縮の常套
Sticks(8) - カメヲラボ
準備 コードを短縮するには、通常のプログラミングで「だめ！」と言われていることをやっていかなければならない。ここからはプログラミングというよりパズルの問題。いかに少ない文字数で、同等の処理をさせられるか。 まず、手始めにシンボル名をすべて一文字にする。 また、配列の初期化はどうしても文字数が増えてしまうため初期化の代わりに新しく宣言しなおすことにする*1 改行コード・空白を省くと330byte程度。まだまだ短縮可能だ。 int L,F,*I; c(n,l,p,j){ --I[p]; if(n==0)F=1; if(!F){ if(l-=p){ for(j=l<p?l:p;j>0;--j) if(I[j])c(n,l,j); } else { for(j=50;!I[j];)--j; c(n-1,L,j); } } ++I[p]; } main(s,b,m){ for(;s;printf("
Sticks(7) - カメヲラボ
計算量を減らす ちょっとした演算でも数十万回呼ばれる可能性があるのであれば、それなりに時間がかかってしまう。演算回数を減らす努力は、再帰の仕組みを真面目に考えるきっかけになり、コードはスマートになっていく。そして、最終的にはコード短縮につながる。 昨日のコードで無駄な部分は、in[n]のデクリメント・インクリメントを2箇所で行っている点。再帰なら一度ずつで済むはずだ。 ということを考えて修正すると、700byte弱になった。シンボル名を一文字にして改行コードを除けば半分程度になるだろうから、これを短縮すればおそらく300byteくらいにできるだろう。 int length,finish,in[51]; check(count, len, plen) { int j; --in[plen]; if(count==0)finish=1; if(!finish){ if(len-=plen){
ラベルは無駄やの - Cozy Ozy
とりあえず変数を減らしていく inputの値は最大64個、それにあわせてlabelも64個。さらにinputはソートしなければならないとなれば、最短コードを目指すには無駄が多すぎる。簡単な方法はlabelを使わないことだが、inputを0で潰す方法は再帰コードで書くとbacktrackし辛い(一つ余分に変数が必要になる)。 この問題のテストケースは、inputの値が最大でも50と問題に書かれている。ということは、inputの値を配列番号にしてその数のカウントをデータにしてしまえばスッキリする。たとえばこれまでの例で使用したinput 15 11 8 8 8 4 3 2 1は、新しい配列(in[51])を使えば in[15]=1, in[11]=1, in[8]=3, in[4]=1, in[3]=1, in[2]=1, in[1]=1 それ以外のin[n]はすべて0再帰する場合1引いて、b
Sticks(5) - カメヲラボ
サンプルコード とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデータ構造をシンプルにしなければならない。 以下はソースコードベタ貼りなので、興味ない人はスルー 001 int input[64],label[64],length; 002 int n;//inputの個数 003 004 int check(int count) 005 { 006 int i=0; 007 if(count!=0) 008 { 009 while(label[i])i++;label[i]=1; 010 if(!search(length-input[i],i+1,count))label[i]=0; 011 } 012
アルゴリズム講座/実践編/バックトラック
バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約90％はバックトラックを使っていると思います。 １．バックトラックの考え 人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は 広範です。もちろん不得意分野もあります。 複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」 というように仮定から仮定へと強引に突き進みます。 そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング) 仮定を立て直して、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定 を立て直して同様に進行すれば、やがては解に到達することに
ＫＯＮＡＭＩ、「METAL GEAR SOLID 4」関連セッションレポート
「METAL GEAR SOLID 4」関連セッションレポート その2 次世代機という“理想”と、PS3という“現実”の狭間でもがくエンジニア達 9月9日～9月11日開催 会場：昭和女子大学 「METAL GEAR SOLID 4」関連セッションレポートのその2では、「MGS4」の最大の魅力であるプレイステーション 3のコンピューティングパワーをフル活用して生まれたグラフィックステクノロジーに関連したセッションの模様をお届けする。 「MGS4」の歴史は、2005年の東京ゲームショウで衝撃的なデビューを遂げた実機デモ「TGS-2005 TRAILER」に端を発する。しかし、この時期から追っていたメディアや熱心なファンなら誰でも知っていることだが、「TGS-2005 TRAILER」の映像と、2008年6月12日に発売された製品版の映像は、そのクオリティに明確な差異がある。「TGS-2005
ＫＯＮＡＭＩ、「METAL GEAR SOLID 4」関連セッションレポート
「METAL GEAR SOLID 4」関連セッションレポート その1 戸島サウンドディレクターが明かす“戦場ストリーム”とは何か!? 9月9日～9月11日開催 会場：昭和女子大学 米国西海岸で年に1度開催される世界最大規模のゲーム開発者向けカンファレンスGDC(Game Developers Conference)では、毎年、旬のタイトルが入れ替わる。開発者のニーズに合わせて、1タイトルで多い場合は5つも6つものセッションが開催される。GDC 2008では、「Halo 3」が旬のタイトルとしてもっとも多いセッションが組まれた。CEDEC 2007では、セガの「バーチャファイター V」、カプコンの「ロストプラネット」あたりだろうか。 ただ、CEDECの場合、日程もセッション数も限られているため、1タイトルで複数のセッションが開かれること自体が希だが、CEDEC 2008では、なんと3つもの
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(後編)
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(後編) 10月24日 収録 会場：ＫＯＮＡＭＩ東京本社 2008年最大のPS3キラーソフトとなった「METAL GEAR SOLID 4(MGS4)」。そのグラフィックスの秘密に迫る3Dグラフィックス講座「MGS4」編の後編は、影生成の話や特殊エフェクト、シェーダーの話題を取り上げていく。また、「PS3専用」として開発されただけに気になる、「MGS4」におけるCELLプロセッサの活用状況についても話を伺った。 ■ 「MGS4」における影生成は? 今世代のゲームらしく「MGS4」は、歴代の「MGS」シリーズと比較すると高度な動的影生成メソッドを実装している。影生成技法としてはデプスシャドウ技法(シャドウマップ技法)の改良形を採用
EventuallyConsistent - 結果整合性
EventuallyConsistent - 結果整合性 目次 この文書について 結果整合性 歴史の話 クライアント側の整合性 サーバ側の整合性 まとめ 結果整合性 この文書について Werner Vogels "Eventually Consistent" の日本語訳です. http://www.allthingsdistributed.com/2007/12/eventually_consistent.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 近年, データ複製の文脈で 結果整合性(eventual consistency) に関する議論が盛んだ. この記事では大規模データの複製における原則や抽象, 高可用性とデータ整合性のトレードオフに関する話題をいくつか集めてみたいと思う. 現在進行中の分野であり, 全ての定義が最初から明快であるとは思わないでほ
blog.katsuma.tv
greeさんで開催されたKey Value Store勉強会に行ってきました。 時間にして4時間超え、内容も国内のKey-Value Storeなソフトウェアの最前線の話ばかりで相当なボリューム。以下、メモってたのを残しておきたいと思います。（誤字、脱字、内容に誤りを含むものなどありましたらお伝えください）また、発表者の方やプロダクトについて、ざっくり調べてURL見つけられたものについてはリンク張っています。 森さん / 末永さん groonga Sennaの後継エンジン 融通が効かないのがSennaのデメリット スコア算出式のカスタマイズなど Sennaの転置索引 索引の構成部品を自由に組み合わせて使える APIもいろいろ QL DB Low Level memcached互換のkey-value store バイナリのみ対応 計測 クライアント memstorm-0.6.8 mem
Robust PageRank and Locally Computable Spam Detection Features - 日々の勉強の航跡
R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain, V. Mirrokni, S. Teng Robust PageRank and Locally Computable Spam Detection Features Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web 2008. Apr. 論文の在処 概要 Webのspamに関連した論文。 局所的に計算できるcontribution vector*1の近似を用いて、前半ではspamの発見方法の提案、後半ではRobust PageRankという文字通りPageRankをspamに対してrobustにしたランキングシステムの提案をしている。 cont
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
HatebuFriends の仕組み - もしかして: blog.iron’s.jp
学生時代に研究・卒論からの現実逃避の一環で作り、去年の10月頃公開（1度移転）した HatebuFriends について今更書いてみたいと思います。 HatebuFriends とは はてなブックマークのブックマーク情報を利用して、好みが似ているユーザや、興味がありそうなページを推薦します。 棒グラフをクリックすると共通のブックマーク一覧が表示されます。同じページをブックマークしたユーザをハイライトすることもできます。 興味がありそうなページを推薦してくれる機能もあります。 人によって精度の差はあると思いますが、自分ではいい感じに推薦されてきていると思っています。 ユーザ間の関連度計算 同じページをブックマークしていることが多いユーザ同士は、似た嗜好を持っていると考えられます。 特に、ブックマークユーザ数が少ないページのほうが、誰もがブックマークするようなページよりも、ブックマークが
西川善司の3Dゲームファンのためのゲームグラフィックス講座 - 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(前編)
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(前編) 10月24日 収録 会場：ＫＯＮＡＭＩ東京本社 2008年のプレイステーション 3のゲームシーンにおいて、最大の話題をもたらしたのは「METAL GEAR SOLID 4(MGS4)」だ。これは間違いないだろう。 「メタルギア ソリッド(MGS)」シリーズは海外でも人気の高い作品であり、「MGS4」はこの世界の期待に応えるべく世界同時発売を果たしている。その意味では、世界のゲームシーンにおいても、2008年の話題の中心には「MGS4」があったように思う。 そんな、いわばPS3のベンチマーク的作品である「MGS4」にまつわる様々な開発秘話を、小島プロダクションはゲーム開発者会議の「CEDEC2008」において積極的な情報
しかしSVMも最近は速いらしい - 射撃しつつ前転 改
Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。 liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。） liblinearにはL1-SVM, L
『【DiGRA公開講座】モンテカルロ木探索とは何か？』
将棋と比べて囲碁の評価関数を難しくしているのは、 ・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。 ・リバーシにおける角のように、明らかな特徴を持った場所が少ない。 ・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。 ・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。 などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。 ・石の厚い薄い 石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。 ・形の良し悪し 複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。 「代表的な悪い形」 ┼┼┼┼┼┼ ┼┼●┼┼┼ ┼┼●●┼┼ アキ三角 ┼┼┼┼┼┼ ┼┼●
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
文字列の繰り返しと計算量 - odz buffer
scale out の技術 〜 consistent hashing 編 (cloud 研究会, December 19, 2008)