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
Sticks(4) - カメヲラボ
探索イメージ 探索方法がイマイチ掴み難いという人もいるかもしれないので、ちょっと図を描いてみた。 ポイントを整理しておくと、 (1)データを降順にソートしておく。 (2)値の大きい順(=配列の前から順)に、stickの長さ(=length)から0になるまで値を引いていく。同時に、使用した値にはラベリングしておく。 (3)長さ0になったら、lengthを元の長さにセットしなおして(2)を再実行 (4)失敗したらバックトラック (5)長さがlengthのstickがsum/length本できれば成功。 DFSの肝は、 最も新しくラベリングされた点に隣接する点を探索するというところだ。つまり図の中では、探索を左側から順に行うことになる。一旦15-4-...と探索を始めたら、「どうやってもムリ！」というところまで探索してからバックトラックしていく。今回の解は15-3-2-...なので、図の①〜③は
Sticks(3) - カメヲラボ
ラベリング 前回のような数字のリストを作るために、inputの各値にlabelをつけることにする。たとえば、入力値input配列を input={ 15, 11, 8, 8, 8, 4, 3, 2, 1 };とすれば、ラベルは label={ 0, 0, 0, 0, 0, 0, 0, 0, 0 };と、最初はゼロにセットしておく。 もし、15-4-1とリストを作れば、15,4,1に対応するラベルを1に書き換える。 input: 15 11 8 8 8 4 3 2 1 label: 1 0 0 0 0 1 0 0 1 このようにして、すべてのlabelを1にすることができれば成功だ。 ラベリングの手順は前回の通り、降順にソートされたinputを、先頭から順に調べる、目標とするstickの長さより短ければラベルリング。stickが完成したらまた先頭に戻り、ラベリングされていない値で同じようにラ
Sticks(2) - カメヲラボ
基本アルゴリズム 前回のような簡単なInputであれば、少々無駄な探索アルゴリズムでも解を求めることが出来る。しかし、PKU1011のテストケースはそこそこ厳しいので、下手なアルゴリズムだとTLE(Time Limit Exceed)要するにタイムオーバーとなる。 とりあえずプログラムを作ってみるのも良いかもしれないが、この手の探索にはDFS(Depth First Search)というものがある。inputの各値を頂点と考えて、最初の点から順番につなぎ木(リスト)を作っていく。 前回までの例は簡単すぎて説明にならないので、次のようなinputを用意する。 8 3 8 15 2 11 4 8 1この9つの値の合計(sum)は60。最大値(max)は15だから、60の約数から15未満の数を省いた、15,20,30,60(=length)について順に調べればよい。 まず、lengthが15にな
Sticks(1) - カメヲラボ
同じ長さの棒を出来るだけたくさん作るには、 ①まず入力値(input)の合計(sum)を求める。 ②sumの約数で、かつinputの最大値(max)以上のもの(=length)を、小さい順から順番に調べていく。 ③すべてのinputを使用して長さlengthの棒ができれば、lengthを出力して終了。これだけでできることはすぐに分かる。 たとえば、前回の入力例 4 3 2 1なら、合計値が10になる。約数は、1,2,5,10このうち入力の最大値4よりも大きいのは5,10だから、最初はたして5になるような組み合わせを見つければよい。 もし入力が5 3 2 1なら合計値が11(素数)なので11がそのまま答えになる。 実際にコードを書いてみると、 001 int input[64]; 002 int length,n; 003 004 main() 005 { 006 int a,b,sum;
2005-12-13
グラフ理論がらみで何かネタになりそうな問題はないかと探していたら、1011番の問題を見つけた。本当はもっと単純な問題がいいのだけど問題量が多すぎてなかなか見つからない。良さげな問題があったら誰か教えてください。 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011 長さがバラバラの棒の切れ端をつなぎ合わせて、同じ長さの棒を作る問題。つなぎ合わせた棒の長さは考えられる答えの中で最小でなければならない。なるべく短くするということは、同じ長さの棒をできるだけたくさん作れば良いということだ。 たとえば、 このように長さの違う4本の棒なら、 という風に同じ長さの棒を2本作ることが出来る。 入力は 1行目：棒の切れ端の数(最大64) 2行目：切れ端の長さ(スペース区切り) 3行目以降は上記2行の繰り返しになっていて、最後の行が0(切
アルゴリズム講座/実践編/バックトラック
バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約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
Re: 文字列の繰り返しと計算量 - まめめも
ref: http://blog.livedoor.jp/dankogai/archives/51172176.html ref: http://d.hatena.ne.jp/odz/20090203/1233676468 問題1 C で Dan さんが挙げられた 2 つのアルゴリズムと同様のものを実装せよ。 問題2 n を変化させながら、計算時間がどのように変化するか観察せよ。 問題3 2 つのアルゴリズムについて計算量はどうなるか。 文字列の繰り返しと計算量 - odz buffer これはなかなか難問ですね。JavaScript の文字列の実装で使われているデータ構造と、加算の最適化の有無によって変わってくると思います。軟弱なので実装や実験はしませんが、問題 3 だけ考えてみます。 フラットなメモリ＋最適化なし 文字列を malloc で確保したようなベタなメモリで実装していて *1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
1011 Tree Summing
http://www.4dm.org/PKU/