前回Qualに通過したので、Google Code Jam Round1Aに参加。

問題 http://code.google.com/codejam/contest/1645485/dashboard
スコア http://code.google.com/codejam/contest/1645485/scoreboard

問題文はCreative Commons Attribution Licenseらしいので、
概要を日本語に超訳したものを、続きを読む以下に書いた。*1

ラウンドの結果から言うと、A, Bのlargeまで正解。Cは出せず。
oooo-- 53点 849位 でR2へはギリギリ通過という感じ。
Bのlargeは正直不安だったけど、通ってよかったね、という感じ。
個人的には、この問題内容なら、もうちょっとがんばれてもいいよなーと思う順位。
ooo-o- の52点ではR2進出にならないのが怖いところ。うん、R2もがんばるし。

なんか、Googleは貪欲法好きですね。前のGCJJでも出てた気がするし。
僕も貪欲法好きなので、貪欲法が使える問題はもっと出るといいですね。

以下、参加記録。
今回はコード貼り付けはなしで……。だって恥ずかしい//
どうせ誰も読まないし、僕も誰かに読んでもらおうと思って書いてないし。
ここにあるしね。

続きを読む

■A

10時スタートなのに、9時55分まで寝てた。
紙と鉛筆の準備をして、コーラの準備をして、座ったのが30秒前、落ち着く暇なくスタートです！

続きを読む

■B

うひー。Aに結構時間掛かっちゃったなぁ。もう1200人以上提出してるよー。これじゃあ通過できないかも。
いや、Bで追い抜けばいいんだ。がんばろがんばろ。

続きを読む

■C

ラウンドっていつまでだっけ？　2時間半か。ってことは後40分しかないのか。うーん、行けるかなー。
Bも1000人近く出してるし、2回wrong出してるから抜かれちゃうかなー。
ううー、C-smallまで取っとけば安心かなぁ？*2
ってゆか、前のGCJJ決勝って、largeまで取ろうとして失敗したんだよ。
smallだけ取るつもりでいってみよ。

続きを読む

■終わり

なんか、結果もう出てる。早い。
これ確定？　確定らしい。849位。AもB通ってた。安堵。

SRMでもCfでも、何かしらプロコンが終われば、その途端にそれまで静かだった僕のTLが加速する。
みんな思い思いに感想をつぶやくので、TLは賑わうだけど、ほとんど＠がなくて、
あっても、 上位入賞おめでとうございます！ とかそんなんがちらほら散見される程度。
コミュニケーションらしいものはほとんどないのに、それでも、
ただ眺めてて面白いTLになることは間違いなくて、結構その時間が好きだったりする。

続きを読む

makeできなかった。

apache 2.4 から .h 側の定義が変わったらしい。
mod_mono.c を何カ所かいじってmakeできた。

参考にさせていただいた！
http://www.yazin.info/blog/archives/2012/0406_171642.html

unixd_config を ap_unixd_config にかえて、
conn_rec::remote_addr を conn_rec::client_addr にかえて
conn_rec::remote_ip を conn_rec::client_ip にかえた。

あと他にも変わってるかもしれないけどとりあえずmakeできたので見てない。

次のmonoでしれっと直るのはたぶんそうなのだろうが、
さしあたり、mod_ なんとかのmakeで困っている人が、
このページを見つければいいよということで残しておく。

続きを読む

こういうのが便利とかあったら教えてください！

直接関係ないけど、コピペしたときに行番号がつかないようにするのってどうやるんだろう。
数字を画像で用意する！　なるほど。そうじゃなくて。

# .vimrc
syntax on
set smartindent
set number
set backspace=2
set laststatus=2
set mouse=a
set tabstop=8
set shiftwidth=4
set expandtab
set wildmenu
set ruler
set statusline=%<%f\ %m%r%h%w%{'['.(&fenc!=''?&fenc:&enc).']['.&ff.']'}%=%l,%c%V%8P
set showcmd
set incsearch
set hlsearch
set timeoutlen=250
inoremap ;; <ESC>

# .screenrc

autodetach on

startup_message off

defbce "on"

term xterm-color
shelltitle 'bash'

defscrollback 3000
hardstatus on
hardstatus string "%?%h%:%t (screen #%n on %H)%?"
caption always "%{= wb}[%02c] %-Lw%40L>%{=b bw}%n%f %t %{= wb}%+Lw %{= wb}%=@%H[$LANG] (%l)"

altscreen on

vbell off

問題: http://code.google.com/codejam/contest/1460488/dashboard

■A 謎言語 Googlerese

Googlerese は、アルファベットを1対1で置き換えた新言語です。
たとえば、"a zoo"は"y qee"になります。
Gppglerese 表現が与えられるので元に戻してください。
この置換表はテストケースごとに変わったりしません。

謎問題というか斬新というか。
問題文中のヒントとサンプルインプットから推測すればよいのね。
q->z だけわからなかったので加えた。

続きを読む

■B 10点！10点！10点！

3人の審判がダンスに対する点を付ける。最低0点から10点満点。
3人の審判の点のうち1番高いものを最高点、1番低いものを最低点、3人の審判の点を合計したものを合計点としよう。
3人の審判はだいたいおんなじ評価基準に沿ってるので 7点7点8点 とか、最高点と最低点が1点しか違わないのがほとんど。
最高点と最低点の差が2点(6点7点8点とか)になることは稀で「びっくり」だし、
まして、最高点と最低点の差が3点以上(6点7点9点とか)になることは絶対にありません。
今N人のダンサーが踊った。N個の合計点と「びっくり」点がついたダンサーがS人いる。
さて、最高点がp点以上のダンサーは最大で何人いると考えられるか答えよう。 N <= 100だよ。

問題の読解がちょっと大変だった。
p = 0 や p = 1 のときに気をつけないといけない。

続きを読む

■C 数字リサイクル

たとえば(12345, 34512) みたいな、ある整数nと、それを途中の桁でちょん切って前後を入れ替えたものmとでペア(n, m)を作ります。
指定された整数A, Bの間に A <= n < m <= B を満たす (n, m) はいくつあるでしょうか。 A <= B <= 2000000だよ。

問題原文のテレビが再放送(？)ばかりでつまらないという書き出しからだが何のつながりもない。
nが最大7桁の整数だから、1つの数字について試すのが7種類x200万。
まぁ、 121212 とかで同じのができるから、そのチェックでx7。
49x200万 1億。　愚直にやるだけ？　愚直にやるだけか。

続きを読む

■D 反射する私

全面鏡張り、マス目に区切られた最高30x30の部屋があるよ。
マス(x,y)の真ん中に自分がいるよ。鏡に反射した自分の姿はいくつ見えるかな。
部屋は霧ってて距離D <= 50以上の光は届かないよ。部屋は最大30x30、最外周は必ず鏡だよ。

光系の幾何問題はなんか難しい。
光線が1本出るタイプのはレイトレすればいいんだけど、
こうやって放射状に光がどばーっと出てるタイプの問題はいまいちどう考えればいいのかわかんない。

続きを読む

■

ちょっとインデントぐちゃぐちゃ。
昔はこんなに汚いコード書かなかったんだけど、
仕事によっていろんなルールを強制されたりで色々やってたら、
なんか自分が普段使ってるルールが曲がったりしてて、
もちっと、ちゃんとルール決めてちゃんとしないとなー、と思う。

とりあえず10進数で2300桁ぐらい扱える全然BigじゃないBigInt。負の値は扱えない。
256のとこを大きくしたら扱える桁数が増える。

割り算と剰余演算子作るのめんどくさくて作ってないけど、
たいてい必要になるのってその辺なんだよなー。もじゅろ10億7とかさー。
というわけで、longのもじゅろだけはとれるよーにしといた。

実戦で使える速度が出るかどうかは未検証。
まぁでもそういう問題は、たぶん、計算量的に無理なようにできてるでしょうね。

続きを読む

■ C# で 桁ごとに進数が違うインクリメントする機械

たとえば、素因数分解したときに 2^0 * 3^1 * 5^4 * 7^2 とかってなったときに、全部の約数を列挙したい時用。

続きを読む

わざわざこういうものを再生産しないといけないところにC#の不便さを感じる。
今日の250が落ちたのはこいつがバグってたせい……ぐぅ。

続きを読む

■素数表を得る

class PrimeTable {
    public List<int> Primes = new List<int>();
    public bool[] IsPrime;
    public PrimeTable(int max) {
        IsPrime = new bool[max + 1];
        for (int i = 2; i <= max; i++) IsPrime[i] = true;
        for (int i = 2; i <= max; i++)
            if (IsPrime[i]) {
                Primes.Add(i);
                for (int j = i * 2; j <= max; j += i)
                    IsPrime[j] = false;
            }
    }
}

public class Program {
    static void Main() {
        foreach (var p in new PrimeTable(100).Primes)
            Console.WriteLine(p);
    }
}