k.inabaさんがちょちょいと解いてらっしゃるので、ここから教えてビームを発信するとしておいて・・・。 今までどうやって確かめてたかというと、 ①適当にN=1000のテストケースを複数作る。 ②O(n^3)でもちゃんと動きそうなコードを書く。 ③で、正しい答えを…

Moo Universityは3問あるみたいなので、タイトルを少し変更。さて、昨日の日記にhinoeさんがコードを提供してくれたわけだが、形としては私が目標にしているものに近い。が、探索が不十分だ。 if(w[j]

ウシが持っているデータはh,wという2要素なので、最低2重のループが必要になる。しかもその中でチームに入れるかどうか判定するとなるとどうしても3回ループしなければならない。h,wのループが必ず昇順であれば、無駄な探索をスキップできるのだが、2つの要…

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2008 うしさんチームを作る問題。簡単じゃーん！と思って手を出したが、めっちゃくちゃ難しいことに気付いた。 A*(H-h) + B*(W-w) A,B,Cはインプットとして与えられる。 H,Wはうしさんのサイズで…

Javaなんて普段全く使わないし、良いところもゼンゼンわからない。しかしPKUの問題をやっていて一つだけ良いところに気付いた。BigInteger(要するに多倍長演算)は便利だなってこと。そーいや、D言語(phobos)には多倍長のクラスって無いんかな？C#には無いん…

今度は量に走ろうかという気がしてきた。問題選ぶの面倒だし、順番に解いていくか・・・。

気付いたら２８問も解いていた。。。というわけで、RiSKさんのように忙しくて遊ぶ時間が少ない方々のために、問題の難易度とお手軽さを紹介しておこうと思う。

問題を解くペースと日記を書くペースが全然違うので、バランスがとっても悪い。（一つの問題をネタに1週間くらい書くとその間数問解く時間があるから、待ち行列に入ったままの問題がたくさん。。。）あと、今でもPKU JudgeOnlineで遊んでるのって私くらいし…

最短コード66B

最短コードが狙えるアルゴリズム(下) 超単純な探索方法を発見したものの、巨大なインプットに対してこの方法が必ず成り立つのだろうか。

最短コードが狙えるアルゴリズム(中) 2を因数に持っていても解の個数には何も影響しない・・・とすると、その他の因数が解に関わっているわけだ。因数が関係あるということは・・・

最短コードが狙えるアルゴリズム(上) 前回説明したアルゴリズムはすばらしい。しかし私は満足しない。この問題は、組み合わせの個数を答えるだけの問題なのだから、もっと単純な方法があるのではないか。

一番良いアルゴリズム(下)

一番良いアルゴリズム(上)

とりあえず通るコードを まず、単純でもいいからコードを書いてみよう。

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2140 たとえば 15 7+8 6+5+4 5+4+3+2+1のように、連続する値を足して15にできるのは15も含めて4通りある。 9なら、 9 5+4 4+3+2のように3通り。 この問題は、合計が与えられた自然数N(1 自然数が…

意外と長くなったので、一通りまとめておく 第0回: 求む！最短コード！！ 第1回: 超絶テクニック(その1) 第2回: とっても短い113Bコード 第3回: 超絶テクニック(その2) 第4回: 超絶テクニック(その3) 第5回: 最短コード101B 第6回: まとめ id:RiSKさんがなに…

超絶テクニックをモノにしてしまえば、最短コードにはすんなりたどり着けるはずだ。

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2140&orderby=clen&language=-1 holeさんとロベールさんが脅威の67byteをたたき出しているわけだが、私はそれを超えるべく禁断のインプット解析に手を出してみた。インプットの種類が5種類程で…

超絶テクニック(その3) 最後は超絶テクニック1と2を融合させる。 前回のテクニック2で書いたコードをもう一度見てみると、

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2105 要するに2進数を10進数に変換するだけのプログラムなのだが、イマイチうまく短縮できない。いつもならのんびり湯に浸かっていてばピコーンとひらめくのにT_T どなたかヒントプリーズ！ b,c,s…

超絶テクニック(その2) まず、このコードを見てほしい。

とっても短い113Bコード 前回のテクニックを利用すると、かなりコードを短縮することが出来る。

ロベールさんが参戦したおかげで、あっという間にコードは短縮された。おそらく101byteが最短ではないかと思われる。参加している人はよくわかると思うが、この問題は120byteくらいでも相当難しい。ここでは、120byteを切るために必要なテクニックを、惜しげ…

10桁のISBNコード。

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1003 テーブルの上に、カードを少しずつずらして重ねていく。カードが崩れないようにするには、枚数が増えるごとにずらす長さを短くしなければならない。