d.y.d. 初Bitsの出：解答編
17:35 11/02/14 TLE '11 変則コードゴルフ大会 TLE に参加していました。 7位でした。無念…。終了１時間前には3位だったんですよ！（言い訳） 問題はこちら です。 自分のソースコードは sub/TLE11 こんな感じでした。 以下、ネタバレ感想など。 短いコードが知りたい方は 優勝者の解説 をご覧あれ。 COUNTI 自然数 i が入力されたら、「自分のソースコードの i バイト目に出てくる文字は、 自分のソースコードの中に、何回出現するか」を出力しよう。できるだけ短いコードで。 基本的にゴルフ大会なので、どの問題も短く書ければ短いほど点数が高いです。 main(){...いつでも4を表示するコード...}//どの文字も4文字ずつになるよう足りない字をここで補充 というのを即座に思いついて、submit 開始直後に投入。 したら、主催者さんがこれでは面白くないなーと
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
行列と項書換 - d.y.d.
21:54 10/06/30 行列と項書換 "Termination of String Rewriting with Matrix Interpretations" という論文を読みました。 これは何かというとつまり、 ICFPコンテストの元ネタとして 紹介 されていた論文です。 れ い 年、 冗談９割で、主催者の専門分野にちなんだ問題が出るに違いない！と叫んでいるのですが、 本当に来るとは思わなかった…。 さて。項書き換え (term rewriting) と呼ばれる研究分野がありまして、 例えばこんな問題を調べています。 文字列に対して、「以下の操作のどれかを好きに選ぶ ＆ 実行する」を繰り返します。 abc という部分文字列を de に書き換える （abc ⇒ de と書きます） ef ⇒ g fgh ⇒ ij どんな文字列からスタートしても、最後には、どの規則も使えない状態 （つ
d.y.d. Bowling
21:11 07/02/26 俺定義で書けたら via この辺。 それをネタ元にして一人用パズルゲームが作れたらNP完全ぽい。 二人用対戦ゲームが作れたらPSPACE完全ぽい、というのを時々聞きます。 NP完全の一番基本的な問題が SAT: bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。 さあ、あなたは、変数 x1 ～ xn の値をうまく決めて式全体の値を true にすることができますか？？ という答えを見つけましょう系なのに対して、PSPACE完全の一番基本的な問題が QBF: bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。 x1 をうまく決めて、「例えx2 がtrueでもfalseでも、そこですかさず x3 をうまく決めたら、 x4 がtrueになってもfalseになっても (以下繰り返し
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
