2005-12-01から1ヶ月間の記事一覧
最短コード250B 270byteあたりからは、ロベールさんと私でじわりじわりと削り合い。ちなみに、前回までで紹介しているコードは、はてな用に私が新しく書きなおしたものなので当時のコードとは違う部分もある。どんなインプットでも通るコードというのは、実…
意外と読める超短いコード 昨日のコードをさらに短くすると以下のようなコードになる。ここまでくると変数名を一文字にした方が逆に読みやすい。え?読みにくい?そうですか..(´ω`) int L,F,*I;c(n,l,p,j){ --I[p]; F=n?F:0;for(l-=p,j=l
準備 コードを短縮するには、通常のプログラミングで「だめ!」と言われていることをやっていかなければならない。ここからはプログラミングというよりパズルの問題。いかに少ない文字数で、同等の処理をさせられるか。
計算量を減らす ちょっとした演算でも数十万回呼ばれる可能性があるのであれば、それなりに時間がかかってしまう。演算回数を減らす努力は、再帰の仕組みを真面目に考えるきっかけになり、コードはスマートになっていく。そして、最終的にはコード短縮につな…
とりあえず変数を減らしていく inputの値は最大64個、それにあわせてlabelも64個。さらにinputはソートしなければならないとなれば、最短コードを目指すには無駄が多すぎる。簡単な方法はlabelを使わないことだが、inputを0で潰す方法は再帰コードで書くとba…
サンプルコード とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデー…
探索イメージ
等差数列・等比数列の判別と言えば、 任意の3項(a,b,c)について 等差:b+b=a+c 等比:b*b=a*cが成り立つことは一般的に知られているので、当然のようにこれを使う。当然のようにというより、この関係式があまりに一般的過ぎてこれしか思いつかないというのが…
ロベールさんと同じ問題をやると必ず1byteは負ける。 頭脳の差ももちろんのことだが、なんというか最初に手をつける段階でロベールさんの方が数段上を行っている気がする。数学的な問題で大事なのは、最初の取っ掛かりでどれだけ核心をつけるかだ。いわゆる…
id:RiSKさんとid:kurimuraさんが1658番で激しくコードを削り合っていました。私も多少考えてはいましたが、2人のペースについて行けず脳内コーディングを繰り返す日々。しかし朝ご飯を食べているときにピピーンと閃いたので、冬のお供iBookにて実験したとこ…
ラベリング
基本アルゴリズム
同じ長さの棒を出来るだけたくさん作るには、
「コレはどー考えても正しいでしょう!」というコードを送信したのに何故かWA。何度確認してもおかしい部分は見つからない。3時間悩んだ。何気なくstatusリストからWAになったソースをブラウザで見てみると、「\」の部分が「¥」に( ̄□ ̄;) そうい…
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011 長さがバラバラの棒の切れ端をつなぎ合わせて、同じ長さの棒を作る問題。つなぎ合わせた棒の長さは考えられる答えの中で最小でなければならない。なるべく短くするということは、同じ長さの…
グラフ理論がらみで何かネタになりそうな問題はないかと探していたら、1011番の問題を見つけた。本当はもっと単純な問題がいいのだけど問題量が多すぎてなかなか見つからない。良さげな問題があったら誰か教えてください。
1145祭りで、いわゆる“非正攻法”として有名になってしまったInput解析であるが、PKUの問題をざざっとみてみたところ、最短コードを書くためにInput解析が使えそうな問題というのは、以外に少ないんじゃないかという気がしてきた。答えが分かったところで、テ…
off-axisの計算
ステレオグラフィックスに関しては、あまり突っ込んだネタもなさそうなのでこれで一旦終わりにしておく。もちょっと情報が欲しい人はメールでもください。リアルタイムホログラフィとか、ちょっと興味のあることもあるがそれはまたの機会に.. それから、今ま…
とんでもない結末になってしまったPKU1145祭り。やねさんは多忙だし、私もちょっと責任も感じちゃったりして、PKU OnlineJudgeの主催者にセキュリティホールのレポートと、記録・アカウントの削除依頼をすることにした。
大変なところまで来てしまったので、これ以上は危なくて書けない。個人的にはまだまだ調べたいこと(消費メモリについて)があるので色々遊ぶけど、コードを削って云々はもう本当におしまい。これからは普通にチャレンジしていきます。これを機会に新しいア…
なるべくしてというか、またまた豪快な記録がでた。
60byteを切ることは出来るのか。
clock()を使う time(0)は100回に一度くらい通るわけだが、id:kurimuraさんが最初に実証したgetpid()を使う方法から比べると、そうとう確率は低くなる。同じ文字数でもっと確率の高い方法は無いのか調べていたところ、clock()はどうかと思った。これは、実行…
time(0)を使ってみる time(0)を使ったコードを送信する場合、Acceptされる可能性について考えてみる。私の書いたコードを使いたいところなのだが、文字リテラルが図形文字でないので、説明には向いていない。というわけで、wajさんが昨日の日記にコメントし…
63byte以下はおそらく核戦争並みなので、さすがにもう手を出すのはやめようと思うのだが、さっきPKUに繋ごうをしたらサーバに接続できない。もしかして、誰かやっちゃった? まあ、それはさておき。