Hatena::ブログ(Diary)

菊やんの雑記帳

2011-02-14 TLE

[] TLEだった 00:53  TLEだった - 菊やんの雑記帳 を含むブックマーク

COUNTI: がんばった3位

HASH: がんばったのに8位

LETTER: やる時間なかった

KD: がんばった3位

ARRNG: 通しただけ8位

HEART: 遊びすぎた

ODDEVEN: がんばった3位

OPTI: ひょろっと書いたモンゴメリ乗算だけでは30倍遅い

f:id:kikx:20110215003013p:image

こんなもん作ってないで真面目に実装しろよって感じだ。

COUTIはsprintfの返り値を使うのか。まったく考えてなかった……

HASHはなんかみんな違いすぎだろ……

やり方ははまじさんと同じだなあ。詰め切れてなかった感がある。

よくみたら違いすぎるのは僕とはまじさんだけだった

LETTERはHEARTが終わったらやる予定だった。埋め込み系苦手

KDは適当に実装したら時間が間に合わなかったので、SIMD化してみたんだけど……

なんでみんな普通の実装で間に合ってるわけ?

ていうかSIMD化してこの順位はすごくね?

ARRNGは適当に実装してそのまま放置。

ODDEVENはなんか詰めきれてない感じ。みんなquineの書き方は全く同じだなあ。よく訓練されてる

char *の代わりにshort*にすれば+=2を++にできてはっぴーだったのに向こうのサーバでは動かなかった。

2009-06-04 Gray Code(2)

[] 00:53 Gray Code(2) - 菊やんの雑記帳 を含むブックマーク

95Bきたー!

ていうかハノイの塔重要じゃん

2009-06-02 Gray Code

[] 00:21 Gray Code - 菊やんの雑記帳 を含むブックマーク

昨日少し考えてみたんだがさっぱり分からない>C

10xバイトにもたどり着けない

じっと眺めてたら、これハノイの塔じゃん!って気づいたんだけど

すでにうぃきぺに書いてあってしょぼんぬ

2008-12-05

[] もうさっぱり縮む気がしない 01:36  もうさっぱり縮む気がしない - 菊やんの雑記帳 を含むブックマーク

Rubyしか使ってないので、Rubyだけ。

99-bottles-of-beer

1st flagitious 173 Ruby 10,000 (v23) 
2nd eban 177 Ruby 9,774 (v13) 
6th yowa 181 Ruby 9,558 (v5) 
7th ozy4dm 182 Ruby 9,505 (v15) 
8th shinh 182 Ruby 9,505 (v18) 
10th kik 183 Ruby 9,453 (v7)   <-- 今ここ!

ぶっちゃけ、これは真面目にやってない。

いや最初は真面目にやったんだが、その後の技術の向上をフィードバックしてない。

たぶん2Bぐらいはすぐ縮むんじゃないかな…

Numeric Diamonds

1st shinh 102 Ruby 10,000 (v17)  
18th kik 122 Ruby 8,360 (v2) 

このコードは今見たら、いくらでも縮みそうだ。beerよりさらに真面目にやってない

Home On The Range

1st flagitious 67 Ruby 10,000 (v58) 
2nd leonid 67 Ruby 10,000 (v100) 
3rd tal 69 Ruby 9,710 (v21) 
---- 越えられない壁 ----
4th jojo 77 Ruby 8,701 (v14) 
5th carldr 77 Ruby 8,701 (v41) 
6th mame 78 Ruby 8,589 (v4) 
7th shinh 78 Ruby 8,589 (v23) 
8th primo 78 Ruby 8,589 (v36) 
9th kik 82 Ruby 8,170 (v2)  <-- 今ここ!

頑張って考えたような気がするが、全然縮まなかった。

上のほうはたまにしか通らないんじゃなかろうか?回数的に考えて

コードを見たら、これはやりこみが足りてない。

Calendar

興味なし12位

Pascal's Triangle

あと2バイトが分からん45B

まめっちがループの最奥を全探索で探していた問題。

SHA-256 Hashing

1st flagitious 338 Ruby 10,000 (v35) 
2nd jojo 386 Ruby 8,756 (v59) 
3rd shinh 420 Ruby 8,047 (v22) 
4th mame 436 Ruby 7,752 (v10) 
5th carldr 437 Ruby 7,734 (v31) 
6th kik 447 Ruby 7,561 (v4)  <-- 今ここ!

今見ても、さっぱり分からんコード。わけわからんが、意外に上位だ。

Total Triangles

1st flagitious 63 Ruby 10,000 (v15) 
2nd leonid 64 Ruby 9,843 (v5) 
3rd jix 65 Ruby 9,692 (v11) 
4th kinaba 65 Ruby 9,692 (v2) 
5th kik 65 Ruby 9,692 (v1) 

これ以上縮むとは思えないが、試行錯誤したとは思えないコミット回数。

Prime Factors

1st shinh 82 Ruby 10,000 (v32) 
2nd kik 83 Ruby 9,879 (v23) 
3rd mame 83 Ruby 9,879 (v14) 
4th leonid 84 Ruby 9,761 (v25) 

これは頑張った問題。あと1バイトがどうやっても縮まない。

Vigenere Cipher

1st leonid 49 Ruby 10,000 (v42) 
2nd jojo 50 Ruby 9,800 (v7) 
3rd primo 50 Ruby 9,800 (v23) 
4th shinh 50 Ruby 9,800 (v17) 
5th yvl 50 Ruby 9,800 (v7) 
6th queball 51 Ruby 9,607 (v3) 
7th kik 51 Ruby 9,607 (v5) 

このコードの汚さは異常。stderrが酷いことに…

1,000 Digits Of Pi

真面目にやってない

Oblongular Number Spirals

1st flagitious 112 Ruby 10,000 (v27) 
2nd kik 117 Ruby 9,572 (v20) 
3rd mame 117 Ruby 9,572 (v13) 

これは頑張った。ふらたんは異常。

Switchboard

1st primo 68 Ruby 10,000 (v9) 
2nd flagitious 69 Ruby 9,855 (v18) 
3rd kik 70 Ruby 9,714 (v8) 
4th kinaba 71 Ruby 9,577 (v8) 
5th shinh 71 Ruby 9,577 (v14) 

これは超頑張った。これ以上縮む余地がない…はず…

Conway's Game of Life

わりと頑張った。

2008-09-14 Quine.grassネタバレ

[][] さすがにもう縮まないのでネタバレ 22:23  さすがにもう縮まないのでネタバレ - 菊やんの雑記帳 を含むブックマーク

最終的に1525バイトになった。劇的に縮められる新機軸はもうなさそうなのでネタバレ

データは以下のようにひとつの関数にエンコードする。すなわち「w → Ww」「W→WWw」「v→WWWw」になる。

  let.dat = abs o1 do
    let.o2 = o1(o1) # w
    let.o3 = o1(o2) # W
    let.o4 = o1(o3) # v
    let.o5 = o4(o4) # w
    let.o6 = o4(o5) # W
    let.o7 = o4(o6) # v
  end

スタックの少し前にある関数にスタックのトップを適用すると、スタック位置の差によって「wWv」のいずれかが出力される。

よって、oN は次のように動作しないといけない。

o3(o3) -> (out w); o4   |    (out Ww);   o4
o2(o3) -> (out W); o4   |    (out WWw);  o4
o1(o3) -> (out v); o4   |    (out WWWw); o4

エンコード前のデータを出力するときは左の結果、エンコード後のデータなら右。

ふたつの動作はほとんど同じなので、各々トリプルを作ってdatをスキャンする関数に渡せばよい

ラムダ計算ではトリプルはこうやって作る。

  let.triplet = abs a, b, c, f do
    f(a, b, c)
  end
  let.tr1 = triplet(out_w, out_W, out_v)
  let.tr2 = triplet(out_Ww, out_WWw, out_WWWw)

  scan_dat(tr1)  # エンコード前のデータが出力される
  scan_dat(tr2)  # エンコード後のデータが出力される

あとはscan_datをどう作るかである。

oNはoMを受け取ったら、(M-N)%3を計算して、o(M+1)を返さないといけないので、

とりあえずは

  let.oN = abs my, tr, n, oM do
    ... 
    (exec_tr tr (m_n_mod3 (get_m oM) n)))
    ...
    (my my tr (succ (get_m oM)))
  end

こういう感じになると思う。

ここで、問題になるのは

o3 == (oN oN tr 3)
o2 == (oN oN tr 2)

という感じに、oNとoMの中身は同じ関数なので、oMからMをとってくる機能もこの関数の中にいれないといけないのである。

これが今回一番難しいところだ。