2012/10/15(Mon)テトロミノ認識〜 横へな 2012.10.6 を解いた。

はてブ数 2012/10/15 23:38 計算機な日記::プロコン つーさ


というわけで。

テトロミノ認識〜 横へな 2012.10.6
http://nabetani.sakura.ne.jp/hena/ord4tetroid/

せっかく解いたし記事にしとけ的な。

10x10のグリッドスペースにぽつんとテトロミノ(かもしれないもの)が置かれるので、
それがなんであるか判定せよ! という問題。

答案とテスト結果。 http://ideone.com/ws2SB

コード量たいしたことない割に40分とか掛かった。

ぱっと見スマートな実装方法が思いつかないので、
なんとか実装したろうという気概が試されそうな問題ですね。

実装方法は色々ある気がしますが、
左上に持ってってパターンマッチングしちゃうのが楽かなーと思って採用してみました。
左上に持ってくループと、パターンマッチングに文字列を使ってるところとかは横着。

コーディングの40分のうち20分は、パターンデータベース()の生成と確認に費やした気がする。
これを生成するのにもうちょっと楽で間違いにくい方法とか思いつければ良かったなぁ。
この手のデータベースはバグの温床になるわけで生成には細心の注意が必要なんですけど。

2012/10/04(Thr)makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定 に挑む。

はてブ数 2012/10/06 0:29 計算機な日記::プロコン つーさ

ネットだらだらしてたら辿り着いたのでやってみた、系。

makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

モニター最速40分だと、競技プログラマーの血がさわぐぜー!

というわけで、回答した。

続きを読む

2012/05/27(Sun)Google code jam Round2

はてブ数 2012/05/27 2:01 計算機な日記::プロコン つーさ

参加した。14ptの1614位 泣いた。

Aは読むのが大変で、なんとか15分くらいかけて読み終わってDPすりゃ解けんのかなーと思ったけど、
いや、普通に一番遠くにたどってけば行けるかどうか判定できるのかって勘違いしてdijkstra書いた。
incorrectもらって、1分考えて反例に思い至って、多重化dijkstraに改造したら、当然ノード数爆発。
各つるで前に探索した時より遠くにreachできるなら続行みたいな改造したので、
Best First Searchじゃなくなっちゃった。largeの計算が終わらず……。辛抱して待つこと4分。
プロンプトに戻ってきた。提出。おお怖い怖い。通った。

Bが今までやったことないタイプの問題だった。
敷き詰める。5倍かー。結構広いんだなと思ったけど、コーナーケース考え出すとキリがない。
フィールドも広いからデータ構造作るのも大変だし。うー、どうしよう。
つーか、この広さなら貪欲でもたぶん大丈夫なんじゃねーの、自信ないけど。
3回出したがincorrectだった。smallだけでもほしい。N10ならモンテカルロで行けるんじゃね?
あと15分。今の貪欲をなんとか直すべきか、迷ったがデバッグの道を選択して、そのまま時間切れ。
一瞬脳裏をよぎった声に従って、乱択で行けばよかったのだが、SRM脳は乱数使う勇気がなかった。
ローカルで答えが合ってるかどうかわかるんだから、探索が終わるかおわんないかの運試し。
N<=10^3の方だってどっちにせよ運ゲーだった。
Aをもうちょっと早く解いて「この調子この調子」でBに取りかかれればまた違ったんだろう。

というか、こうやって振り返るとAもBも不正解じゃねーか。

Tシャツが欲しかった。可能性はあったと思う。つくづくTシャツには縁がないなぁ。

最近TopCoderのレーティングも立て続けに落としてるし、競技プログラミングがスランプ気味。
書くコードも汚くなった。僕のプログラマ人生はぼちぼち終わりかけてるのかもしれんとちょっと思う。

2012/04/29(Sun)Google Code Jam Round1A 参加記

はてブ数 2012/04/30 6:04 計算機な日記::プロコン つーさ

前回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でも出てた気がするし。
僕も貪欲法好きなので、貪欲法が使える問題はもっと出るといいですね。

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

続きを読む

2012/04/25(Wed)apache 2.4.1 に mod_mono 2.10 で error: 'unixd_config' undeclared

はてブ数 2012/04/25 1:50 計算機な日記::ボクと計算機 つーさ

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で困っている人が、
このページを見つければいいよということで残しておく。

続きを読む

2012/04/17(Tue)僕の .vimrc と .screenrc は、ここで進化していく(むしろgit使え

はてブ数 2012/04/18 23:57 計算機な日記::ボクと計算機 つーさ

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

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

# .bashrc # cygwin

## auto start screen
## if $STY is not set...
if [ -z "$STY" ]; then
    screen -dR
fi

## share history between screen sessions.
function share_history {
  history -a
  history -c
  history -r
}
PROMPT_COMMAND='share_history'
shopt -u histappend
export HISTSIZE=200000
export HISTFILESIZE=2000000
export HISTCONTROL=ignoredups
## exclude short command from history
export HISTIGNORE=?:??:???:exit:logout

export PS1="\[\e]0;\w\a\]\n[\[\e[36m\]\D{%m-%d %H:%M:%S}\[\e[0m\]] \[\e[32m\]\u@\h \[\e[33m\]\w\[\e[0m\]\n$ "
# .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