Time Limit Exceeded 2011
今年はパッと見問題が粒揃いで，去年のようにスコア設定も不自然に高いものも無く，総じてとてもいい問題セットだったと思う．多少英文が意味不明というか曖昧なものもあったが，途中で加筆されるなどで特に問題無し．去年13位だったこともあり当初の目標はランキング1ケタだったが全体的に"いけそう"な問題セットであることが判明したのでアドレナリンどっぱどぱでヤリコミ確定．1位を狙うヤル気勢に．
結果は残念ながら2位．1位はいつもお世話になってますanarghy golfのオーナーshinhさん．書きながら歯軋りしてますがおめでとうございます．ぐぎぎ．
当初は例年通り2日間開催だったのが3日間開催に期間延長が入った．わからん殺しの代表格Quine系問題のおかげもあり，2日目までの1位キープ率はかなりのものだった(というかほぼずっと1位だった)のだが，3日目で各問がヨセに入った途端Cゴルフ的な黒魔術のバリエーションの無さが露呈してしまったカタチといえる．なさけない．正直Cなんてクソ言語どうでもいいけどCゴルフは別．なさけない．
Haskell Golfer でも楽しめるコンテストなんだよってところ見せるのも目的のひとつだったんだけどどうだろうか？
他の人の記事
以下各問について．
COUNTI
コードの指定番目の文字が全コード中に何個出るかを出力する問題．いわゆる変形Quine．今回のQuine系問題ひとつめ．
普通の"%d\n"の数字エンコードをつかったエスケープ回避によるQuineコードを投げるとどうもスコアが低いので，kinabaさん同様固定数を出力するコードに変更．後に計算式が変更されてからはdefineマクロ型のQuineに方針変更し投稿したコードになった．去年MAX400点配点のブッ壊れ問題をFancyMouseさんにdefineマクロ型Quineで殺された反省からこれはすぐに書けた．
HASH
入力各行を全部連結し半分で前後に分割した両方の文字列のハッシュ値が一致するかを判定する問題．ただし，コード自身を入力として食わせたときに一致判定されなければならない．
やはり最初は末尾に自身をコピペで済ませていて，後に変数名とかバッファサイズを変更する方法に変更．Cで大本のコードを縮めたものをHaskellに食わせて，自動的にハッシュ一致コードに変換していた．このへんのサポート言語を何使うかはシュミだね．
LETTER
8x13のAAによるAtoZ文字データが与えられており，入力の8x13のAAがそのどれかに一致するならその文字を，どれにも一致しないなら?を出力する問題．実はHASHが伏線．このへんも今回の問題セットのよいところ．
ハッシュ値を使うことはすぐにわかったのだが，投稿コードからは血迷いが見える．血迷いスケッチである．うまくないしキレもゴロも悪い．これもHaskellで式とデータ生成しているが大本が血迷っているので全然ダメ．
KD
K次元の格子点データの指定点値更新と指定範囲内総和の2種のクエリを連続で処理する問題．いわゆる領域探索．
投稿したコードはとても愚直に書かれており，Cゴルフ的な短縮の他は特筆すべき点が本当に何もない．素直な記述の場合，計算量が非常にギリギリで，まさにTimeLimitExceededとの戦いになる．このギリギリさ加減に，今回の問題がよく練られていることを感じた．ただ，一度通ったコードが終盤は全く通らなかったりしてサーバ側の御機嫌伺いになることもあった．shinhさんも同じ現象になったみたい．もしかすると出題側は2分探索とかして欲しかったのかもしれない．
ARRNG
入力された数列をソートする．それを1つずつ左ローテートした列をそれぞれ作る，各列を構成する数字について1つ飛ばしになるように再配置したものを作る．列単位で同様に1つ飛ばしになるように再配置する．という作業をした表を出力させる問題．ふう．これだけでもめんどくさそうなのに，コード中の#;空白にペナルティありでかつdefine,for,while禁止と至れり付くせり．
当初サンプル入出力が偶数個パターンひとつしかなく，問題の意味がよくわからない状態だった．奇数個パターンの追加後，問題の意味がわかったので，序盤は1列毎に入れ替えを処理するように書いていた．元よりHaskell使いにとって再帰のみで書くなど制約でも何でもない．むしろ再帰でスタックが枯渇しないことを問題が保証してくれており，ありがたいくらいであろう．この時点でmainを含め再帰関数が5つ．
が，どうも他の人は格段に短いようだったので，表の(i,j)番目がi,jから直接求められるように式を組んで実装．この際のビット演算はHacker's Delight様々．結果的にテストケース単位再帰のmainと，入力ソート表出力を行う再帰関数の2つとなった．
HEART
与えられたハートのAAを出力する．完全に一緒である必要は無いが，差異分はペナルティが付く．短くそしてできるだけ差異が少なくエンコードしておき，展開して出力する問題．lossy
最初はMove To Frontをかけて，圧倒的多数である0に関しては連続出現個数で，それ以外の1から7についてはそのまま"それが出た"とエンコードしておくようなRun Length Encodingをテキトーにかけて提出た．が，とてもスコアが低かった．
ハテどうしよう．HuffmanとかArithmeticとかのエントロピー符号化でもかけてみるか？でもなー．とか考え，でもロス分のペナルティって案外小さくね？と思って上手くロスさせる方針に変更．
まずはパラメトリックに形状を作る方向を試す．が，あまりおいしくない．ハート型自体のカバー率はそこそこだったのだが，ハート内部は適当なパラメータ調整と関数選択ではロスが大きすぎた．
あきらめて，全体を5x5のブロックに区切って，各領域内で最大出現数の文字を取り出して小さなハートを作った．コイツに対して，3ビットで出現文字，5ビットで出現個数を表わすRLEをかけて提出でそこそこのスコアになった．これも非常に大雑把．まぁ，文字とはいえ絵なんだからそう思ってエンコードすべきだったねという話．
今さら思ったのだが，改行無視でデータを一直線に並べたものがすごいキレイな波形になってて，2次元のデータとして扱わなくてもそのままFourier変換とかするとキレイな周波数領域のデータになったりしないだろうか？
ODDEVEN
入力が偶数だったら自身のコードの偶数番目の文字，奇数だったらコードの奇数番目の文字を出力する問題．いわゆる変形Quine．今回のQuine系問題ふたつめ．
COUNT1に同じ．putcharしたまま停止させるためコード末尾に0を2つ付けてるのがミソか．
COUNT1でもそうだが，最終的にshinhさんのCゴルフ力に押し切られた．バッファをどこかに取ってcharポインタが欲しいなーと思っていたのだが，適当に使えるバッファがどこにあるのか見つけられないという状態だった．
OPTI
デカい行列の冪乗計算．
目算ではっきり言ってムリな計算量だったのでコードも書かずシカトしていた．結果的に誰も通さなかったので実質問題セットに無いも同然の問題だった．あのヒントを一体どう使うと計算が減るのか出題側(or識者)の解説求む．
まとめ
Quine系の問題を得点源に他の問題をそこそこ詰めておけばいけるかなーと思っていたが，それらを3日目にCゴルフ勝負に持ち込まれた時点で「あ，コレはダメだ」と思えた．当初の予定通り2日開催で，細かいCゴルフ勝負に持ち込む時間的猶予が生まれなければまた少し違う結果だったかもしれない．まぁ，その場合他の人も戦略変えてくるだろうからifの話にすぎないけど．
今年の問題セットで個人的に最も良かったと思っているのは，過去に連続で出ていた「与えられたクソコードが何をやってるか解釈した上で短くする」問題が無くなったことだ．「短くする」のはともかく「クソコードが何をやってるか解釈する」なんてゲームでもやりたくない．
COUNTIとODDEVENは冗長だったかな．どっちかだけでよかった．ODDEVENは去年のQuine系と比べて簡単過ぎたので，似たようなもんだけどどっちか残すとしたらCOUNTIかな．計算式が初めから練れてなかったのは定数出力への想定が出題者側に無かったのだろう．
今回の問題セットで一番TLEらしさを持ってたのは個人的にはARRNGだと思う．次がHASH．LETTERと続く．
shinhさんも言ってたけど本職でヤル気勢なC Golferがあまり出てこないのが救い．
