Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICFP Contest 2009 終わりました

ICFP Programing Contest 2009 が終わりました。
今回はじめて参加しましたが,3日間疲れながらも楽しめました。来年も,(なかなか難しいですが)時間を割けれたら参加したいと思います。
今回の結果は,いま一つの3問目までで最後の Clear Skies は Give up でした。

 こまかな話はまた後で書いてみたいと思います。参加されたみなさまお疲れ様でした。

スポンサーサイト

ICFP Contest 2日目

shinhさんのすさまじい早さを横目にマイペースで頑張ってます。
問題を一見したときには易しいように感じたのですが,実際始めてみると結構はまります。

自分の環境で CreateFile が使えないのは誤算でした・・・
VC++のExpress Editionでは,Platform SDKを入れないとダメなのですね。
仕方なく fopen を使うも第2引数で "b" を付けるの忘れて,理不尽な挙動に小1時間ほど悩まされました。"b"がないと文字以外のコードを全部読み捨ててくれるという,すばらしい仕様です。

"b"を付けるのは Microsoft の固有ルールなんでしょうかねぇ。
UNIXを使っていたときには,気にしたことがなかったのですが。

あとは,三角関数の使い方があいまいな記憶で,
第1象限以外ではどうなるの?ってかんじで試行錯誤が必要でした。
後で整理しておこうと思います。

これから楕円軌道に挑戦してきます。(最後の Clear Skies は遥か遠く・・・)

ICFP Programming Contest 2009 いよいよ

待ちに待ってた ICFP Programing Contest !いよいよ始まりますね。
Hack The Cellの勉強会(の後の飲み会)で教えてもらったこの大会,かなり楽しみに待ってました。

月曜は年休を取得し,3日間燃え尽きる準備は万端です。
それでは参加者の皆さん頑張っていきましょう!Good Luck !

#とりあえず今は明日に備え寝ておきます・・・

Hack The Cell 再び

shinhさんがHack The Cellのまとめ資料を書かれていました。
資料はコンパクトに纏まっていて,さっくりと読めます。楽しく読ませて頂きました。

この資料に感化されて,自分自身のまとめを書いておこうと思いました。たいしたことは書けないのですが,以前の勉強会で触れなかった部分を書いていきたい思います。(勉強会資料-pdf

命令の手動配置について
      手動配置作業ファイル

このファイルは,手作業で命令配置を行ったときのアウトプットです。
表の最初の状態は,左側に「mt行列の計算」,右側に「tempering処理」の命令が書かれていました。左右それぞれeven odd命令を分けて書いています。

「tempering処理」はほとんどがeven命令なので一旦置いておき,「mt行列の計算」から最適化を行います。「mt行列の計算」の命令群を変数の依存関係に注意しながら,できるだけevenとodd命令が重なるように配置していきます。表の色塗り部分が「mt行列の計算」を縮めた結果を示しています。

続いて,「mt行列の計算」の空いている部分に「tempering処理」の命令を入れ込んでいきます。
「tempering処理」の最後の方ではodd命令が現れるため,若干の調整を必要としました。

この表を5ループ分作成します。

配置の確認

表での 配置を終えたら,CSV形式で出力し,even-odd命令が互い違いになるよう1列に並べかえます。この状態で普通のCプログラムになります。ですので,これをコンパイルすることで実行結果を確認でき,配置の正しさを検証することができます。

アセンブラへの変換

実行結果がOKとなったら,続いてアセンブラコードへ変換します。
アセンブラへの変換はCプログラムの文字列を変換するコンバータを作成しました。

この辺り文字列操作に長けている言語を使えれば良いのですが,残念ながらマスターしている言語がないためCで書いています。
     アセンブラ・コンバータ

手抜きプログラムなので,変換元のCプログラムの書き方に色々な制約を課しています。(空白の入れ方等)

これで出力したコードには,まだC変数が書かれていますので,最後にsedでcellのレジスタ名に一括で置換します。これで最適化されたコードが完成です。

TopCoder SRM 442

初Div1。
目標としては「250点問題は何とか解く」でしたが,そこは何とか行けました。

素数を求める必要のある問題でしたが,いきなり言われても出てこないわけで・・・
ひょっとしてテーブルでも良いんじゃないのと邪悪な方向に走ってみましたが,あえなくsubmitで弾かれました(警告が表示されました)。

    「コードのうち30%以上が使われていない・・・なんたらかんたら」

そんなレギュレーションがあったんですね。まぁ,ズルはできないということで。
結局は時間をかけすぎてしまったため,Ratingは下がってしまいました。

やはりアルゴリズムの知識量が,まだまだ不足しています。

次のページ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。