俺俺any
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
#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が出来たー。
継承を捉えるのに例外を使って補足しました。上の実装はあくまでコンセプトだけなので実装は超絶手抜きですが。
ところでこれとっても重いんで誰かもっとスマートな実装あったら教えてください
lexical_castの話
id:DigitalGhost:20091228
ポリシーもそうだけど、そもそも型自体書きたくないよとか言ってみる。
というわけで
int n1 = lexical_cast("123");
boost::optional
と書けるようにしてみました。
問題点を解決するのではなくてよりヒドイ方向にシフトしてみました
#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; } }
ICPCの思い出
全ておわったので適当に自分の中の思いを適当につづる。
来年からは参加資格を失うので今年が最後のICPCでした。
そんなわけで、現在の感想は例年と違うことを思いつくかなと思っていました変わりませんでした。
それは、いつも感じている自分の無力感です。
上位陣と比べると非常に手が遅くて絶望的な実力の差を感じる4年間でした。
別に絶望的な差を感じることは悪いことではありません、むしろ絶望的な感覚が非常に楽しい。
うちの大学は正直プログラムをまともに書ける人間が非常に少なくて自分ですら出来る子な部類に入ります。
そのせいで自分はプログラム出来る子じゃないだろうかという勘違いをしがちです。この大会はそれを打ち砕き自分の身の程を知るいい機会になります。
さて、4年間通して参加してきて、自分の足りない能力が色々と見えてきました。一番大きいのは英語力と実装速度のなさです。
英語に関しては、まぁ中学のころから駄目人間でした。これに関して言い訳をすると......言い訳が特に出来ません、ごめんなさいごめんなさいごめんなさい。
というわけで、大会中の英語は基本的にチームメイトに完全に依存していました。
そのせいで問題の細かい条件などを聞き落とすなどのミスが頻発するなど明らかに問題が出ていました。
もう一つの実装速度に関してですが、僕はとにかく手が遅い。大会中の最初の1問が遅いなんかは英語が読めないからスタート遅いだけなので大したことではないですが、
中盤以降のコーディングするスピードが上位陣と比べて圧倒的に遅いです。
この速度の差が生まれる要因は簡単でとにかく練習時間の少なさが原因と思われます。
自分は基本的にICPC向けの勉強会やライブラリなどを一切準備せずにその場で大会受けるだけというスタイルなわけで絶望的に練習が足りません。というか0です。
そのため、この手のプログラミングコンテスト向けに最適化されたコーディングスタイルが出来てない点が一点。
もうひとつlinux系への習熟度の低さ。正直大会中はgnome-terminalとvimとg++とPC^2しか使ってません。この辺linuxもっとまともに使えるようにならんとなぁがもう一点です。
まぁこの辺大会終わったのでもうどうでも良いという話もありますが、基本的に大会関係なくプログラム書くのが好きなのでダメなところはこれからも直していこうと思う。
最後にICPCありがとう。僕の大学生活において自分の能力のなさを指摘し続けてくれたこの大会は非常に有意義でした。
僕にとっては適当な大学生活の中で数少ない目標でした。この大会がなければ僕は自分のところの大学で一番プログラミングが出来るという非常に低いレベルで満足していたと思います。
というわけで2009年アジア予選
参加してきました。
一日目
東京へ新幹線でいつものように移動。
新宿駅あたりで昼飯を適当に食ってたら時間がやばいことになったのでタクシーで現地に向かう。
しょっぱなから遅刻して申し訳ないなぁとか思いながら会場に入る。
とりあえず練習問題をいつものようにやる。
適当に
#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を設置。
適当に談話室で色んなチームとだべりながらいんたーねっこ。
ついでに適当にtwitterのICPC参加者っぽい人をフォロー
自分の居た談話室以外でも同じようなことしてるところがあった模様。
二日目
本戦開始。
今回は正面と側面の高さマップ、2つの点集合を直線で切り分けれるか、水泳のやつ、20個のドア(だっけ？)、あと何か忘れたけど1個の5問をといた。
結果発表は早稲田らしいので早稲田に移動。
移動中になんかよくわからん団体がわめきながら行進してた。
｢憲法9条｣「最低賃金」「靖国」「派遣」「消費税」「普天間」あたりを何か言ってたけど、
主張の是非は置いといて、もう少し主張範囲を絞って活動したほうがいいんじゃないのかとおもった。
とりあえず会場についたらJavaチャレンジスタート。
基本的には同系のアルゴリズムの人との対戦が多かったので相手のボーナスアイテム付近に爆弾設置した分の領土で勝利パターンで4位まで進む。
で今回の大会で3部門を制覇したHITORI#のチームと戦って惨敗して終了。
最終順位は3位になった。とりあえずJAVAカレーもらた
とりあえず結果は10位でした。もう少し上の順位にいきたかった無念。難度的には解ける問題あったので時間配分ミス。
その後適当に酒のみ会場に行ってみて適当に酒飲んで適当にふらふらになって適当に騒いで部屋にもどって睡眠。
三日目
書く気力がなくなってきたので略。
2社ほど会社見学。基本的に専門分野外の話は聞いていてたのしーなーという感じでした。
その後てけとーに新幹線で帰宅。
*1:なお最初ルールを勘違いして最後に四方囲んだ方がアイテムを獲得すると勘違いして実装したけど先の理由で悪くはなかったのでそのまま放置
■
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); } }
rubyで14BでHello, world!
何となく要求があったりなかったりした気がするので紹介。
現在anarchy golf - hello worldのRubyの最高記録は12Bなのですが頑張っても分かりませんでした。
悔しいので自分の14Bのコードをネタばれします！
あすんでれネタばれ
というわけで時間が来たのでネタばれです。
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という条件にしました。
入力が終了したら次は出力です。ようするにカウントした値を出力していくだけです。
まぁとくに工夫する点もありませんね。
