No Such Blog or Diary

なにやら国際天文学連合（ＩＡＵ）というところが惑星の定義をちゃんとして太陽系の惑星の数を増やしたそうで．いっそのこと冥王星を格下げしたほうがいろいろとらくだと思うのだが．とりあえず新しい惑星に日本名が付くのかどうかが気になるところ．

レポートを書くために実時間ＧＣに関する論文を読まねばならない．んで，Citeseer で引っかかった比較的新しい論文が POPL の論文だったのでそれを読むことにした．なれない分野の論文なのでよく分からないテクニカルタームに苦しみつつ現在読み途中．Ａ４２枚程度のレポートなのであまり細かく読まなくてもいい気がしてきたが…

どうやら東京で大規模な停電があったらしいのでビデオの予約が吹っ飛んでないか微妙に心配．電車も止まったみたいだし，昨日の内に実家に帰ってきてたのは正解だったようだ．とりあえず，もう少し頑丈に出来ないものかねぇ．一箇所にまとまってる電線切っただけで長時間落ちるとは情けない．

G：最小包含円を求めよ．

凸法を使って平均的な実行オーダーの良い実装をしてもらったけど間に合わず．３点に接する円の半径とかその円に対する点の内外判定が良くわからず…　残念でした．

とりあえず見事に最下位取得．初日にA問題をちゃんと実装していれば上位に食い込めたが…　ま，今回は順位はどうでも良いとしてたのでよしとしよう．そして，Haskellで平衡木を実装するのが非常に面倒だと思う今日この頃．

C：円周上の点を４つつないで出来る四角形の面積を最大化．

とりあえず２次オーダのアルゴリズムで実装してもらったが…．対角線を一つずらしたときの残りの頂点の変更方をちゃんと理解してもらえていなかった模様．

D：最大１５０００個の宝物があるので定められたサイズの長方形でなるべく多くの宝物を囲め．

O(n^2) のアルゴリズムを実装して正解．y軸値ごとに宝ものリストをｘ軸でソートして，それを使うことで長方形の移動による囲まれた宝物数の変化をO(1)で求める形にした．とりあえず出題者の求める平衡木を利用した回答は絶対に２時間では実装できません．

E：リング状に和が１である様な数字が並んでいる．一つの数字を選んで左右の数字にその数字を足しこみ自身は符号を反転させるという操作を繰り替えすとき，すべてを正の数に出来る最小の手数を求めよ．

ここからメンバーが３人に．残りの二人に考えてもらって正しいものが出来上がる．ただ，真の正解にたどり着くには数学的に式を弄り回す必要があり…　ちと時間内には無理ですよと．

F：コンビネータで書かれた式を評価するインタプリタを書け．

Haskell でパターンマッチで頑張る．簡約自体をHaskellにやらせたかったけど型の扱いが良くわからなくなり断念．とりあえず正解．

うーん，自分の書いたところは点が取れたが…　微妙な結果に．とりあえずAlgoは４人のペアプレイで２回とも勝利．

A：円柱が立ってるので光源の方向を変えたときの影の幅の最大と最小を求めよ．

やり方はわかっていても実装する時間なし．去年に引き続きサンプル入力だけ正しいプログラムを書いて逃げる．

B：辞書順最小となるように重複要素を取り除け．

アルゴリズムを考えてもらってそれの実装を手伝う，というか隣でタイプすべき文字をしゃべり続ける．結局間違ったアルゴリズムの実装を２回行い時間切れ．

うーん，各セッションで一人一問しか書けないという縛りの上，二人しかチームにいない状況で一人がプログラムを組めないって…　当然のごとく最下位．