Hatena::ブログ(Diary)

kurimuraの日記

2010-01-19 boost::anyを車輪の再発明しよー

[]俺俺any 00:56

C++boostにあるboost::anyってご存知でしょうか?

なんでも放りこめる便利な型です(詳細はこの辺でも)

しかし、boost::anyを使っててたまーに困るのが共変の型でも変換できないということがあります。

具体的には

struct X{int value;};
struct Y:X{};
boost::any a = Y();         //aにはY型が入っている
X x = boost::any_cast<X>(a);//Y型はX型ではないので変換できない!

このようにY型とX型が継承の関係にあっても違う型なので変換できません。

とっても悔しいです。あきらかにY型からX型への変換は問題はないというのに!

なんとか解決したくなったので超適当本質部分だけ実装してany_cast<X>(a)が出来るようなanyをでっち上げてみました。

#include<iostream>
#include<boost/any.hpp>
struct any_e{
	struct any_handler{virtual ~any_handler(){}virtual void exec()=0;};
	template<typename T>
	struct any_impl : any_handler{T value;
		void exec(){throw value;} any_impl(const T&value):value(value){}
	};
	any_handler*handler;
	template<typename T>
	any_e(T value):handler(new any_impl<T>(value)){}
};
template<typename T>
T any_cast(any_e&e){
	try{
		e.handler->exec();
	}catch(const T&r){
		return r;
	}
	throw "BAD CAST";
}
int main(){
	struct X{int value;};
	struct Y:X{};
	try{
		any_e a((Y()));
		X x = any_cast<X>(a);
		std::cout << "OK any_e\n";
	}catch(...){
		std::cout << "NG any_e\n";
	}
	try{
		boost::any a((Y()));
		X x = boost::any_cast<X>(a);
		std::cout << "OK any\n";
	}catch(...){
		std::cout << "NG any\n";
	}
}

これで共変の型ならany_castが出来たー。

継承を捉えるのに例外を使って補足しました。上の実装はあくまでコンセプトだけなので実装は超絶手抜きですが。

ところでこれとっても重いんで誰かもっとスマートな実装あったら教えてください

k.inabak.inaba 2010/01/20 15:15 dynamic_any ( http://cpp-experiment.sourceforge.net/ ) では、
 template<typename T>
 struct any_impl : any_handler, T { any_impl(const T&value):T(value){} };
こうして any_handler* から dynamic_cast で T* (もしくはその基底*) を
取れるようにしてますね。

kurimurakurimura 2010/01/20 20:10 なるほど! 継承してdynamic_castで引っかけたらいいのか。ありがとうございます。
any_handle,any_impl相当の部分で継承使うだけじゃなくて値の保持にも継承を使えるのかー。
盲点でした。

というか普通に面白そうなライブラリですね。
他にも何かいろいろ楽しそうな感じだしあるし適当に読んでみます。

2009-12-29

[]lexical_castの話 14:36

id:DigitalGhost:20091228

ポリシーもそうだけど、そもそも型自体書きたくないよとか言ってみる。

というわけで

int n1 = lexical_cast("123");

boost::optional<int> n1 = lexical_cast("456");

と書けるようにしてみました。

問題点を解決するのではなくてよりヒドイ方向にシフトしてみました

#include <typeinfo>
#include <sstream>
#include <string>
#include <boost/optional.hpp>
#include <boost/lexical_cast.hpp>
namespace detail {
    template<typename Source>
    struct lcast_auto_error_handling {
        Source const & src;
        lcast_auto_error_handling(Source const & src) : src(src) {}
        template<typename Target>
        operator boost::optional<Target>() const {
            return cast<Target>();
        }
        template<typename Target>
        operator Target() const {
            return throw_if_none(cast<Target>());
        }
    private:
        template<typename Target>
        boost::optional<Target> cast() const {
            std::stringstream ss;
            if ((ss << src).fail()) {
                return boost::optional<Target>();
            }
            Target res;
            if (!(ss >> res) || ss.get() != std::stringstream::traits_type::eof()) {
                return boost::optional<Target>();
            }
            return boost::optional<Target>(res);
        }
        template<typename Target>
        static Target throw_if_none(boost::optional<Target> const & value) {
            if (!value) {
                throw boost::bad_lexical_cast(typeid(Source), typeid(Target));
            }
            return value.get();
        }
    };
}

template<typename Source>
detail::lcast_auto_error_handling<Source> lexical_cast(Source const & src) {
    return detail::lcast_auto_error_handling<Source>(src);
}
#include<iostream>
int main() // テストコードは http://d.hatena.ne.jp/faith_and_brave/20091225/1261734967 から拝借
{
    try {
        int n1 = lexical_cast("123");
        std::cout << n1 << std::endl;

        int n2 = lexical_cast("xyz");
        static_cast<void>(n2); // no use
    }
    catch (boost::bad_lexical_cast&) {
        std::cout << "bad_lexical_cast" << std::endl;
    }

    boost::optional<int> n1 = lexical_cast("456");
    std::cout << n1.get() << std::endl;

    if (boost::optional<int> n2 = lexical_cast("xyz")) {
        std::cout << n2.get() << std::endl;
    }
    else {
        std::cout << "lexical_cast error" << std::endl;
    }
}
トラックバック - http://d.hatena.ne.jp/kurimura/20091229

2009-11-11 おもひで

[]ICPCの思い出 03:56

全ておわったので適当自分の中の思いを適当につづる。


来年からは参加資格を失うので今年が最後のICPCでした。

そんなわけで、現在感想は例年と違うことを思いつくかなと思っていました変わりませんでした。

それは、いつも感じている自分無力感です。

上位陣と比べると非常に手が遅くて絶望的な実力の差を感じる4年間でした。


別に絶望的な差を感じることは悪いことではありません、むしろ絶望的な感覚が非常に楽しい

うちの大学は正直プログラムをまともに書ける人間が非常に少なくて自分ですら出来る子な部類に入ります。

そのせいで自分プログラム出来る子じゃないだろうかという勘違いをしがちです。この大会はそれを打ち砕き自分の身の程を知るいい機会になります。


さて、4年間通して参加してきて、自分の足りない能力が色々と見えてきました。一番大きいのは英語力と実装速度のなさです。


英語に関しては、まぁ中学のころから駄目人間でした。これに関して言い訳をすると......言い訳が特に出来ません、ごめんなさいごめんなさいごめんなさい。

というわけで、大会中の英語は基本的にチームメイトに完全に依存していました。

そのせいで問題の細かい条件などを聞き落とすなどのミスが頻発するなど明らかに問題が出ていました。


もう一つの実装速度に関してですが、僕はとにかく手が遅い。大会中の最初の1問が遅いなんかは英語が読めないからスタート遅いだけなので大したことではないですが、

中盤以降のコーディングするスピードが上位陣と比べて圧倒的に遅いです。

この速度の差が生まれる要因は簡単でとにかく練習時間の少なさが原因と思われます。

自分は基本的にICPC向けの勉強会ライブラリなどを一切準備せずにその場で大会受けるだけというスタイルなわけで絶望的に練習が足りません。というか0です。

そのため、この手のプログラミングコンテスト向けに最適化されたコーディングスタイルが出来てない点が一点。

もうひとつlinux系への習熟度の低さ。正直大会中はgnome-terminalとvimg++とPC^2しか使ってません。この辺linuxもっとまともに使えるようにならんとなぁがもう一点です。


まぁこの辺大会終わったのでもうどうでも良いという話もありますが、基本的に大会関係なくプログラム書くのが好きなのでダメなところはこれからも直していこうと思う。


最後にICPCありがとう。僕の大学生活において自分能力のなさを指摘し続けてくれたこの大会は非常に有意義でした。

僕にとっては適当大学生活の中で数少ない目標でした。この大会がなければ僕は自分のところの大学で一番プログラミングが出来るという非常に低いレベルで満足していたと思います。

トラックバック - http://d.hatena.ne.jp/kurimura/20091111

2009-11-10 ICPCアジア予選

[]というわけで2009年アジア予選 10:35

参加してきました。

一日目

東京新幹線でいつものように移動。

新宿駅あたりで昼飯を適当に食ってたら時間がやばいことになったのでタクシーで現地に向かう。

しょっぱなから遅刻して申し訳ないなぁとか思いながら会場に入る。

とりあえず練習問題をいつものようにやる。

適当

#include<iostream>
#include<fstream>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;
...

みたいな感じのinclude書きまくる練習をしつつサブミットする。

その次にJavaチャレンジをする。

問題は陣取りゲームボンバーマン

爆風の爆破範囲が自分の領土になるので多くの領土を制圧したら勝ち。

特定のアイテムの四方を先に自分の領土で囲むとボーナスあったりなかったり。


とりあえず、適当に実装を始める。

サンプルとして適当に走り回って爆弾を置けるときに置く奴とボーナスアイテムを狙い撃ちに爆弾を置くふたつのコードがある。

狙い撃ちにするコードを基本にして目標アイテムなくなったら適当に走り回るコードスイッチするように実装。


自分独自の実相としては

相手の領土を探したりするコード書くのが面倒なので相手がとったボーナスアイテム付近に爆弾をしかけるコードの作成。

相手がボーナスアイテム取ってるなら,

その付近は相手領土のはずなのでそこに爆弾をおいておけばいいだろうという適当実装*1

次にデッドロックの回避、このゲームなのですがひとつ問題があります。

相手と自分が同じ座標に居るときにお互いに爆弾を置こうとしてデッドロック状態になります。

それが起こるとゲーム時間切れになるまで動けないという現象(というかバグ?)があります

仕方がないのでお互いに同じ座標で相手が爆弾を置いた場合は相手に場所を譲る紳士的な機能を実装しました。

この実装は実はデバッグ版の機能で本戦用では勝ってる時はロック意図的に維持する機能も搭載してましたが

試験用にコメントアウトしていたのを戻し忘れていました。

このミスJavaチャレンジ終了のお知らせが来た直後に気付きました。

Javaチャレンジ終了後にソースコードEclipseで開いてコメントアウトしてるのを確認しましたが、

時間切れだったので涙をのんでそのまま放置


その後Welcomeぱーてーでチーム紹介をした。

今年のチーム紹介は「○○は俺の嫁!」と主張する人が多数いて噴いた。

僕らのチーム名は「auto main =-277;」というチーム名だったので0xのautoについて適当に与太話をするだけの紹介にする。


夜。

宿泊棟に行く、なぜか私の鞄にLANケーブルと電源タップが存在していたので、他チームのなぜか存在していた無線ルータと組み合わせて談話室に無線LANを設置。

適当に談話室で色んなチームとだべりながらいんたーねっこ。

ついでに適当twitterICPC参加者っぽい人をフォロー

自分の居た談話室以外でも同じようなことしてるところがあった模様。


二日目

本戦開始。

今回は正面と側面の高さマップ、2つの点集合を直線で切り分けれるか、水泳のやつ、20個のドア(だっけ?)、あと何か忘れたけど1個の5問をといた。


結果発表早稲田らしいので早稲田に移動。

移動中になんかよくわからん団体がわめきながら行進してた。

憲法9条」「最低賃金」「靖国」「派遣」「消費税」「普天間」あたりを何か言ってたけど、

主張の是非は置いといて、もう少し主張範囲を絞って活動したほうがいいんじゃないのかとおもった。


とりあえず会場についたらJavaチャレンジスタート


基本的には同系のアルゴリズムの人との対戦が多かったので相手のボーナスアイテム付近に爆弾設置した分の領土で勝利パターンで4位まで進む。

で今回の大会で3部門を制覇したHITORI#のチームと戦って惨敗して終了。

最終順位は3位になった。とりあえずJAVAカレーもらた


とりあえず結果は10位でした。もう少し上の順位にいきたかった無念。難度的には解ける問題あったので時間配分ミス

その後適当に酒のみ会場に行ってみて適当に酒飲んで適当にふらふらになって適当に騒いで部屋にもどって睡眠

三日目

書く気力がなくなってきたので略。

2社ほど会社見学。基本的に専門分野外の話は聞いていてたのしーなーという感じでした。

その後てけとーに新幹線帰宅

*1:なお最初ルール勘違いして最後に四方囲んだ方がアイテムを獲得すると勘違いして実装したけど先の理由で悪くはなかったのでそのまま放置

トラックバック - http://d.hatena.ne.jp/kurimura/20091110

2009-10-12 yasasii free

[] 18:38

stack_ni_yasasii_free_tree

treeを回転させて回転しきれなくなったら削除だと割と簡単にかける気がする。

void stack_ni_yasasii_free_tree(tree* t) {
	while(t){
		tree*tmp;
		while(t->r){
			tmp = t->r;
			t->r = tmp->l;
			tmp->l = t;
			t = tmp;
		}
		tmp = t;
		t = t->l;
		wrap_free(tmp);
	}
}
トラックバック - http://d.hatena.ne.jp/kurimura/20091012

2009-09-29 Hello,world!

[][]rubyで14BでHello, world! 05:58

何となく要求があったりなかったりした気がするので紹介。

現在anarchy golf - hello worldRubyの最高記録は12Bなのですが頑張っても分かりませんでした。

悔しいので自分の14Bのコードネタばれします!

続きを読む

leonidleonid 2009/12/27 00:22 12Bの年は”サーバーにファイル保存すること”を使った理由で削除されたといいます。 私たちの勝利です!!

leonidleonid 2009/12/27 00:24 ”年”でない”解”です。 翻訳機使うことに上手ではありません。

トラックバック - http://d.hatena.ne.jp/kurimura/20090929

2009-08-14 おなかすいた

[]あすんでれネタばれ 14:51

というわけで時間が来たのでネタばれです。

s[];main(f){
	for(;s[getchar()]++%f?:s[++f]?printf("%c:%3d\n",f,s[f]):f<99;);
}

基本的な方針としてはsに出現回数を入れるのですが入力の終端をどうやって取るのかが問題です。

適当配列の値の余りが0のときというふうにしました。正確にいえば終端じゃないですけど気にしない

入力終了後にはs[-1]が延々と増え続けているので、いずれ条件を満たします。


あと,s['\n']が0のうちにs[++f]を素早く実行してfを10以上にしましょう。

そうしないとprintfで改行文字も表示してしまいます。

カウントが早すぎるとs['A']のときに入力が終わっていないので後半は遅くなるようにs[getchar()]++%fという条件にしました。


入力が終了したら次は出力です。ようするにカウントした値を出力していくだけです。

まぁとくに工夫する点もありませんね。


終了条件は正直適当

たぶん、?:演算子というgcc拡張使う以外はごくごく普通コードです

トラックバック - http://d.hatena.ne.jp/kurimura/20090814

2009-08-04 アスンデレってツンデレの仲間?

[]asunder 17:05

anarchy golf - asunder

とりあえず、id:RiSKさんがやっていたので全力で参戦。

問題内容は文字の出現回数のカウントです。

規格なにそれ?おいしいのって感じでCで76Bで通してみました。

ネタバレタイムまで10日あるのでみんなのんびり頑張ろう

トラックバック - http://d.hatena.ne.jp/kurimura/20090804

2009-07-04 ICPC

ACM/ICPC国内予選。

今年は解き方がぐだぐだすぎた。

A->Bと順調に解いたけどCがなぜかうまくいかなくて諦めてDに移行するのが遅かったのが敗因。

Dを速攻で終わらせて、Eをとっても遅いコードで書いて大会終了2分前(だいたいテストケースあたり20分)にようやく通したという駄目っぷり。

Cを解けなかったのが心残り。

各問題感想

A

普通に書くだけ

B

再帰で書くだけ

C

とりあえず糞遅くてもいいから間違いのないコードを書こうとしたけど

それすら正しく動作しなくてあきらめた。たぶん問題文から見落としがあったんだろうなぁ。

D

恒例のダイクストラだけで終わる問題。

何も考えず速度+場所をノードダイクストラでおわた。

E

Eで最大マッチングが出るのはさすがに予想してなかった。

あとでやろうと放置してたからよくわからんままライブラリコピペで終わったのが悲しい。

自分で通したアルゴリズムの動作原理意味もよくわかっていないという悲しさ

たぶん前にどこかのチームのライブラリ適当に写してただけだから

使い方すらよくわからんかったけど勘で動かした。

紙から打つときに1個間違いがあって最初それに気づかずに30分くらいロスした。

ちゃんと打ててるか確認することは大事だね。

F

ごめん問題文。最初から最後まで読んでなかった

トラックバック - http://d.hatena.ne.jp/kurimura/20090704

2009-05-16 スキルチャージ(2)

[]さらにスキルチャージ! 20:08

前回リモートデスクトップを有効にしたので次はIISです。

とりあえずWebサーバーとして使えるようにするためにIISを有効にします。

これは役割から追加でWebサーバーを選ぶだけで簡単にできます。

面倒なのは大嫌いなので楽なのは素晴らしいです。

f:id:kurimura:20090516195748p:image

次は家の自宅鯖との共存です。

家に既にサーバーが置いてあって個人用に色々既に活用しているので、

家鯖と今回のサーバーの共存が必須です。

まず、大学においてあるサーバに家からアクセス出来るようにする必要があります。


ここで大きな問題があってうちの大学ネットワークは外には直接繋がってないんです。

プロキシサーバを経由してネットに繋げることしかできません。

このままだと大学サーバーを置いても公開できません。

そこで(以下、下手すると怒られそうなので略

それっぽいなんやかんやがあって、大学から家にsshを通す隙間を作れました。

f:id:kurimura:20090516195754p:image

これで大学ネットワーク越しに家にアクセス出来る環境が整いました。

とりあえず、httpを共存するために家のapacheのVirtualDomainに追加しました。

[]適当コンテンツを作る 20:08

あとは適当コンテンツを置いていくだけです。

ただ、コンテンツとか置くネタなにもないなーと気づいたので考え中です。

とりあえず、過去ハテナで書いたコードを再利用してお茶を濁してみました。

RubyコードをRubyで等価に実行可能な記号だけに変換する プログラム の記事

の変換プログラムJavaScriptで書いてWebっぽい気分にだけ浸ってみた。

404 Not Found

javascript初めて書いたけどよくわからん。まぁOperaで動いたからいいやという超投げやり。

トラックバック - http://d.hatena.ne.jp/kurimura/20090516

2009-05-14 そうだ。スキルをチャージしよう

[]Microsoftスキルチャージ 17:59

少し古い話ですがTech Fielders Activities ? IT エンジニア向け技術資料まとめ | TechNetWebサーバー導入キットに応募していました。

それで応募していたWindowsサーバ一式が届きました。

正確にはだいぶ前に届いてた気もしますが、時間が取れなくて放置していました。

で、そろそろ時間取れそうなのでサーバーを構築する気力がわいてきました。

そんなわけなので適当に構築までの流れを書くですよ。

なんでこれに申しこんだかって理由を書くと、id:tmytさんが知り合いが申し込んでたので申し込んだと聞いたので申し込みました。

よくわからん連鎖です。そういうわけで、さくっと申し込んだらさくっと届きました。

届いた箱はこんな感じ

f:id:kurimura:20090514172042j:image

箱を開けてそこの中に入ってた今回届いたサーバーがこれ。

f:id:kurimura:20090514172040j:image

ええと、NEC Express5800/110Geですね

Webページには申し込みだと届くのはML110G5と書いてある。

けど、予告なく変わる場合があるぜって書いてたので予告なく変わっていたようです。

最初、違う機種が届いたのでかなり驚いたのは秘密

で、家だと場所がないので大学においちゃえ大作戦を実施します。

他にも今回のに応募していた知り合いが何人かいたので悲惨な状態になっております。

f:id:kurimura:20090514172039j:image

とりあえず、こいつにWindows Web Serverをインストールします。

インストール自体は適当クリックしていくだけでできます。

最近OSは楽に入れれてほんといいなぁ。

で、サーバーの各種設定をこれからするわけですが、その前にVGAの画質が最悪です。

この110GeのオンボードVGAの性能は非常に残念なようです。

そこで、ローカルの別のマシンから操作するようにしましょう。

linuxとかだとsshだけ入れれば幸せなのですが、ここはWindowsなのでリモートデスクトップを有効にしましょう。

有効にする作業はWindows XPやらVistaと同じなので眠りながらやってたらできました。

これで最低限使えることができる環境ができました。

f:id:kurimura:20090514172036j:image

次くらいに残りの作業をする

トラックバック - http://d.hatena.ne.jp/kurimura/20090514

2009-03-27

自分の無能さの確認をしてみる。 11:45

http://www.kmonos.net/wlog/95.html#_2107090326

論文読まずに適当コード書いてみて後で論文を読んで自分のセンスの無さに絶望する遊びをしてみる。

z = Prelude.map
s x = \f a b -> x (uncurry f) (zip a b)

myZipWith = id

map     = myZipWith zero
zipWith = myZipWith one
zero = z
one  = s z
main = do
        print $ Main.map id [1..10]
        print $ Main.zipWith (,) [1..10] [2..11]

無能の確認完了 13:53

論文読んでみた。うーんコード見ると簡潔すぎて自分の頭の悪さがよくわかるなぁ。

関数型言語は他人の頭の良さに絶望する言語だから楽しいなっと。

(C++は他人の変態っぷりにゲラゲラ笑う言語)

トラックバック - http://d.hatena.ne.jp/kurimura/20090327

2008-10-04 ねむい

トラックバック - http://d.hatena.ne.jp/kurimura/20081004

2008-08-24

http://shinh.skr.jp/m/?date=20080823#p01

>RubyコードRuby等価に実行可能な記号だけに変換する プログラムは書けるだろうか。

eval"実行したいコード"

を記号だけで表現すればいんじゃね?

適当に変換プログラム書いてみた。

def _(_)
	r="''<<"+_.split("").map{|_|
		_=_.ord;
		return "~-_" if _==0
		(["_"]*(_&3)+["__"]*(_>>2&3)+["___"]*(_>>4&3)+["____"]*(_>>6&3))*"+"
	}*"<<"
	"->{_=-~($$-$$);__=_<<_+_;___=_<<__;____=__<<__;%s}[]"%r
end
puts"->&_{_}[&:\"\#{#{_"method"}}\"][$$,:\"\#{#{_"eval"}}\"][#{_([*$<]*"")}]"

標準入力Rubyコードを渡すとあら不思議。記号だけのRubyコードが。

手持ちのRuby1.9処理系だと動いたけどなぜ動くのか自分でもいまいち理解していない。

適当に書いたらたぶんうまく動いている気分になった。

ToDo:

エンコーディングが冗長。

shinichiro_hshinichiro_h 2008/08/24 22:43 おおおすごい。 eval を作れれば良いと思って考えてたんですけど、 &:”#{}” は思いつきませんでした…

ku-ma-meku-ma-me 2008/08/24 23:02 おおおすごい。ぼくも思いつきませんでした。

2008-08-09

[]v2.018 18:27

配列演算びみょー

というか役にたたなすぎ。

a[] = a[] + b[]

も出来ないなんて悲しすぎる。

おいおい配列同士で演算できないなんてゴミやん?

あと

a[] = a[] * 2 + 3

もできないのが悲しい。

何が悲しくて

a[] = (a[] * 2)[] + 3 

とか書かなあかんねん。

とか文句言いながら実行するとAccess Violation。うがー。

まぁ文句書いてるけど、

たぶんこの辺はそのうちサポートされるでしょ。

というかこの辺サポートして効率よく実行してくれるなら割と素で嬉しいよ。

うぉるたー君を信じてあげよう。

kurimurakurimura 2008/08/09 18:35 自分で書いておいてなんだけど、最初の例は動いてた。
a = a[] + b[];
こう書くとエラーメッセージが出てるのをみて勘違いしてたようだ。

kurimurakurimura 2008/08/09 18:36 いやまて
a = a[] - b[]もa = a[] * b[]も動くじゃないか。
なんでa = a[] + b[]だけ動かないんだよぉ...

トラックバック - http://d.hatena.ne.jp/kurimura/20080809

2008-07-04

[]国内予選 23:48

チーム名はてきとーに去年から即値だけ変えてmain=-277;で

てきとーに参加しててきとーに4問通った。

とりあえずA,B,C,Dといたー。

今年の国内予選はどれも頑張れば解けそうに思えた(E,Fはまだ深く考えてないけど)。

  • A

とりあえず2重ループ普通ゴリゴリと。

  • B

なんか変な素数に対するエラトステネスの篩を書いて通した。

実は書くのに手間取ってる内にCのほうが楽そうな気がしてCを先に解いた。

  • C

適当パースして実行するだけ。

適当構文木をnewしまくって(deleteはめんどいからしなかった),構文木にevalしまくって解いた。

  • D

よくある最短経路を求めるグラフ問題。

問題文を思いっきり勘違いして迷路の命令をゴールにたどり着くように書き換える問題と思ってた。

チームの一人が勘違いしてるのを教えてくれたので、さくっとただのグラフの最短経路問題に落とす。

とりあえずx,y,方向で各頂点を生成して最短経路求めるまではすぐできた。

最初適当にウォーシャル-フロイトで書いたら遅すぎて涙目に。

やっぱり9重ループ(x,y,方向のループが3つ)って駄目か。

ダイクストラに置き換えするのに時間無駄に食う。

*1

*1:今気づいたけど最適化オプション付けずに書いてた。最適化するとウォーシャル-フロイトつかっても通るのかな?

トラックバック - http://d.hatena.ne.jp/kurimura/20080704

2008-06-23

[]Compound interest 09:15

nihaさんのコードを全力でパクリながら縮めてたけど逆転されたー。

むー、%1$s使うのか。

気がつかなかったー。素晴らしい。

トラックバック - http://d.hatena.ne.jp/kurimura/20080623

2008-04-29 templateって難しい

[]template thisはどうやるんだろう 09:42

D言語で急にコンストラクタテンプレート関数にしたくなったんだけど、

どうすりゃいいんだろう?

class Test{this(T)(T value){...}}

上のような書き方だとコンパイル通らないし。

とりあえずstd.boxer.Boxclassを使ったような感じの実装しようとして悩み中。

別にコンストラクタ初期化できなくても、

static opCallを使えば十分見た目は良いんだけどすっきりとしない...

だれか偉い人、いい案あったら教えて!

トラックバック - http://d.hatena.ne.jp/kurimura/20080429

2008-04-25 しんばーじょん

[] 06:20

わーいD2.013

D言語君の__FILE__と__LINE__は大分話が分かるやつになったらしい。

void check(T)(lazy T v,string file=__FILE__,int line = __LINE__){
    if(!v)printf("Error: AssertError Failure %.*s(%d)\n",file,line);
}
void main(){
    check(0);
    check(0.0);
    check(null);
    assert(0);
}

これが気持ち的には正しい動作するようになるのはうれしいなぁっと。

opDotと__threadは面白いような気がしつつ使い道がまだ思いつかないや...

トラックバック - http://d.hatena.ne.jp/kurimura/20080425

2008-03-28 phobosってやっぱり微妙

[]std.typecons.Tupleが使えない。 09:53

D言語(v2.012)のstd.typecons.Tupleがだめ過ぎる。


ええと、std.typecons.Tupleってのは簡単に言うとboost::tupleみたいなもんです。

ところが、こいつには問題があって、むちゃくちゃ大雑把に実装を説明すると

struct Tuple(type){//説明のために1要素限定のTuple
	mixin(type.stringof ~ " _0;\n");
}

こんな感じに文字列mixinを使って変数を宣言しています。

が、type.stringofというのが呼び出されるのはstd.typecons.Tupleの中なので

std.typecons以外のモジュールで定義された型に触れません。

つまり

import std.typecons;
struct Hoge{}
Tuple!(Hoge) Huga;//Error: std.typeconsの中ではHogeは定義されていない

みたいな宣言を行うことが出来ません。

正直、この制限が鬱陶しかったので適当に修正加えてみました。


tupleImpl全書き換え

private template tupleImpl(uint index){}
private template tupleImpl(uint index,type,string name,T...){
    mixin tupleImpl!(index,type,T);
    mixin("alias _" ~ ToString!(index) ~ " " ~ name ~ ";\n");
}
private template tupleImpl(uint index,type,T...)
{
    enum string indexStr = ToString!(index);
    enum string decl = "type _"~indexStr~";"
        ~"\ntemplate field(int i : "~indexStr~") { alias _"~indexStr
        ~" field; }\n";
    mixin(decl);
    mixin tupleImpl!(index + 1, T);
}

struct Tuple直後のmixin(tupleImpl!(0, T).result);を変更

    mixin tupleImpl!(0, T);

なんかライブラリ周りで不満な点があったら、

自分の使うphobosだけ適当に修正加えてその場凌ぎをしてしまう癖が。

phobosは色々微妙なんだけど、Tangoとかは使う気が沸かないんだよなぁ

haru-sharu-s 2008/03/29 02:05 もったいない.ぜひ投稿してください><;

kurimurakurimura 2008/03/29 21:48 std.typeconsは最近出来たばかりだし、少し待てばこれ相当の事を誰かやるんじゃないのかなぁ。
と、無責任に傍観している最中です。

トラックバック - http://d.hatena.ne.jp/kurimura/20080328

2008-03-07 dmd v2.012

[]this(this)と~thisは死ねば良いと思うよ 00:39

D言語の新バージョンで遊んでみた。

struct S{}
struct T{~this(){}}
struct U{this(this){}}
struct V{V opAssign(V x){return*this;} ~this(){}}
void main(){
	S a;a=a=a;//OK
	T b;b=b=b;//NG
	U c;c=c=c;//NG
	V d;d=d=d;//OK
}

~this()かthis(this)が定義すると、

なんと勝手にopAssignも定義しやがるんですが、そいつの帰り値の型がポインタです。

だから、b=bの式の型はT*になるとか、わけがわからん。

ただ、自分でopAssignも定義すれば大丈夫になるからまぁマシか。

個人的には構造体のデストラクタは嬉しいんだけどね。

トラックバック - http://d.hatena.ne.jp/kurimura/20080307

2008-03-03 いつものこと

[]よくわからんけど通らない(win dmd v2.011) 17:08

とりあえず最小限のえらー発生コード

void main(){
	int[string]x=["AA":0];
	cast(void)x["AA"];
}

連想配列リテラルなんて普段使わんから、

自分が悪いのかコンパイラ(+ライブラリ)が悪いのかよくわからん。

とりあえずは急場を凌ぐために

void main(){
	int[string]x=["AA":0];
	foreach(k,v;x)x[k]=v;
	cast(void)x["AA"];
}

とかやって誤魔化してるけど。

TODO:v2.050くらいまでに直らなかったら後で調べる。

トラックバック - http://d.hatena.ne.jp/kurimura/20080303

2008-02-27

[]std.algorithm.mapが使えねー 23:58

久しぶりにD言語愚痴を。

とりあえずstd.algorithm.mapイマイチ

なにが使えないかってmapの返す型です。

Ranges[0] map(string fun,Ranges...)(Ranges rs);

具体的にはこれ書こうとしてエラー出るのが嫌

map!(toInt)(words);//文字列の配列を数値の配列に変換

これは引数string[]だから、

戻り値string[]にしないと駄目なので通らない(dmd v2.011)


ようするに(A->A)->[A]->[A]じゃなくて(A->B)->[A]->[B]が欲しい


というわけでphobos適当書き換え。

やったことは非常に簡単。

map関数戻り値の型を以下のように書き換えればOK。

- Ranges[0] map(string fun, Ranges...)(Ranges rs)
+ typeof(unaryFun!(fun)(Ranges[0][0]))[] map(string fun, Ranges...)(Ranges rs)
- Ranges[0] map(alias fun, Ranges...)(Ranges rs)
+ typeof(fun(Ranges[0][0]))[] map(alias fun, Ranges...)(Ranges rs)

nihaniha 2008/02/28 01:20 できるもんだと思ってましたが、そういえばそうですね…。早速適当に書き換えときました。

kurimurakurimura 2008/02/28 01:50 できるものと思っててコード書いてたら動かなくてアレー? とか悩んでました

トラックバック - http://d.hatena.ne.jp/kurimura/20080227

2008-01-14 今日もPKU

[]PKU3406 00:05

今日もodzさんのところから問題ゲット(id:odz:20080113)。

ただ、他の人と比べてメモリの使用量がすんごい事になってる。

ううむ、なんか、実装に大分差がありそうだなー。

問題がだるい大きさなのでコードサイズの削減がかなーり適当です。

たぶん、普通にまだ削れる気がする。

続きを読む

トラックバック - http://d.hatena.ne.jp/kurimura/20080114

2008-01-12 久しぶりにPKU

[]PKU2291 21:16

id:odz:20080110を見て全力で挑戦。

ソースコードの変化の流れをついでに書いたので超長くなった。

続きを読む

トラックバック - http://d.hatena.ne.jp/kurimura/20080112

2007-11-04

[]v2.007 22:22

わーいD言語にopStarが来たー

くろーじゃくんも嬉しいなっと

ACM/ICPCアジア予選後に知って早く遊びてーとうずうずしてました。

[]アジア予選行ってきました。 22:22

去年は1問しか解けないという無能さを存分に発揮したので、

今年は2問を目標に参加してきましたー

無駄に文がダラダラと長くなった。


続きを読む

トラックバック - http://d.hatena.ne.jp/kurimura/20071104

2007-08-28

[]Two Dice of A sides 19:01

http://golf.shinh.org/p.rb?Two+Dice+of+A+sides

id:letterさんマジでスゲー。

2byteの差からしてアルゴリズムが違うと踏んでたけどやぱりか。

変数を2個使う方法は考えていたけど、このやりかたは思いつかなかった。

とりあえず、id:letterさんに負けてるけど自分が書いたコードの解説

main(n){
  while(9/printf("N=%d,A=%d\n",n++,5-~(n/11?:n-11)/2));
}

9/printf(...)はprintfの戻り値は出力したバイト数であるという点と、

最後のN=99のときに始めて戻り値が10になるのを利用。

単純に10>printf(...)と書くより1byte短い。

類似系としてprintf(...)%5も、こっちは思いつかなかった。


あとはprintfの中身はループ毎に値を計算する方式。

細かい技術だけど、-~a==a+1なのを利用して短縮。

KiKi 2007/08/29 21:22 はじめまして。9/printf思い付きませんでしたorz
皆さんすごすぎ!!

kurimurakurimura 2007/08/31 10:21 ちはっす。
9/printfは思いつくというより、もはやイディオムになってましたw
そういうわけで慣れれば考えずに無意識にできるようになりますよー

正直 5-~(N/11?:N-11)/2 の部分のほうが難しいと思ってたので、
それを自力で書けているKiさんなら後は慣れれば十分いけますよ

トラックバック - http://d.hatena.ne.jp/kurimura/20070828

2007-08-27 メモ

[]~(~0 << n) 21:40

自分の好きなビット演算メモしておく。

2^n-1を計算するときってほぼ無条件に(1 << n)-1を使ってしまう*1

が、(1 << n)-1は、~(~0 << n)と書くことも出来る。


残念なのは両式共にバイト数が同じだということ。

しかし、諦めてはいけません!

定数~0が変数に格納されている時は後者はさらに短縮できます!

a=~0としたとき

a << n^a

と書けます。演算子の優先順位のおかげで括弧が省けて2byteお得

変数に~0が入ってるときって滅多にないような気もしますが

while(n--){...}

ループ抜けた後とかで意外と結構あるので覚えておくと役にたったり立たなかったり

*1:すくなくとも自分は

トラックバック - http://d.hatena.ne.jp/kurimura/20070827

2007-08-09

そんなわけで例の本が出ました。

Short Coding ~職人達の技法~

Short Coding ~職人達の技法~

で、それについてとやかく書こうとしたけど、

どう考えてもここ見てる人は皆知ってそう、と自分も思う


私はD大好きっ子ですが、Cも好きなのでこの本はコードも含めてガッツリと読みました。

とりあえず、Cでショートコーディングする際に必須な技術は大体全部出てます。

これで、あなたもショートコーダーになれますよ! という感じ。

ショートコーディングとか難しそうとか思っている子も、

この本を読んでぜひチャレンジすると良いよ!


個人的には読んでいて、あー懐かしいなこの問題。

とか言いながら当時の自分の書いたコードと見比べて、

本のコードの方がより短縮されていてorz

という楽しみ方をしました。


あと、裏の楽しみ方として、本より短縮してやるぜウリィィ!

とかいうのもありかもしれません。

実行したいのですが自分は未だにどれも短縮できていません。

2007-08-01

そういえば 06:08

ショートコーディング本が発売されるらしい。id:Ozy:20070727

これは買わなきゃ損だよね!

[]PKU1023 06:08

うむむ、http://www.4dm.org/ShortCoding/index.php?POJ1023を見てビット演算で楽勝じゃんとか思って適当に書き書き。

しかし、逆に長くなってしまったorz

うーん、ビット演算を使える形に持っていくのにバイト数を結構使ってしまう。


問題の詳しい内容は上のURLを参照してもらうとして。

えーと、とりあえず、Fun Numberビット毎に重みの正負がバラバラなやつです。

重みの正負がビットによってバラバラと言えば-2進数です。

ようするにFun Numberは-2進数の一般化とも言えます。

で、実は-2進数と2進数に対する『ハッカーのたのしみ』の変換方法は、

Fun Numberと2進数の変換として一般化できます。

id:kurimura:20070228

char*p;
_int64 n,m;
main(x,v){
  for(gets(v);~scanf("%d%s%I64d",&x,p=v,&n);
      printf(m/2-~n/2>>x-1?"Impossible\n":"%0*s\n",x,_i64toa(n+m^m,v,2)))
    for(m=0;*p;)
      m=m*2|*p++/2&1;
}

入力 -> pnを2進数に変換 -> オーバーフロー判定 -> 入力Fun Numberに変換 -> 表示

という形になっています。

ただ、このコードではオーバーフローの判定を微妙にイカサマしています。

本来は(m/2-~n/2>>x-1)は(m+n>>x)で十分なのですがm+nが64bitに収まらないため、

    m+n    >> x
 ≒ (m+n)/2 >> x-1
 ≒ m/2+n/2 >> x-1
 ≒ m/2-~n/2>> x-1

と変形して通しました。

最下位1bitの情報を捨ててるのでイカサマコードです。

しかもn/2を-~n/2にして無理やり通しています。

イカサマなしなら、A+B == (A&B)*2+(A^B)を活用して(m&n)+(m^n)/2 >> x-1としたほうが良いかな。

トラックバック - http://d.hatena.ne.jp/kurimura/20070801