つーさのくーかん

何気なくツイッターに流れてきたURLをクリックしたとき、その先に書かれているものが意図せずしてプロコン的問題だった場合、瞬間、突然、強制的に、脳内のストップウォッチをスタートさせられてしまう。えっ　えっ。これは、恐怖以外の何物でもない……！

— ルバン・ガイバンサ・サーツさん (@ttsuki) 10月 13, 2012

というわけで。

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

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

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

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

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

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

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

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

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

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

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

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

続きを読む

スーパーテンパズル http://shindanmaker.com/198886

今回はこれを解いてみたくなったんだ。

さて、どうやって解くか……。

注意：プロコン系の話です。

続きを読む

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

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

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

続きを読む

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

A 謎言語 Googlerese

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

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

続きを読む