2017-04

スポンサーサイト

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

CGJ 2012 QR

図形問題だけ解いて逃げるつもりだったけど、TL見てると他の問題もおもしろそうだったのでそっちも解いてみたら、
ひゃくてんだー(


D問メモ

最初問題を勘違いして、ある方向にレイをうてばいいのかなーって思った。
そんなことはなくて、全方向だった。

ぜんぶ格子上に乗ってるので、戻ってくるとすればx,yにそれぞれ整数距離だけ進んだ方向にうったレイに限られる。

方針としては、レイをうつ方向を見つけてきて、その方向にレイをうって戻ってくるかを確かめる。

反射位置は有理数になるから有理数クラスでも書こうかと思ったけど、めんどくさいからフィールドのほうを整数倍拡大してみることにした。まあ結局どっちもいっしょだけど。

そこまで決めたところで、ジャッジシステムどうなってるのかなと思って、
うかつにもSolveボタンを押してしまって、残り4分とか出て、
4分ではたぶん難しいと思います。

smallに提出したやつ
http://ideone.com/u44VD

実行速度がおそくて4分ぎりぎりで超エキサイティングしてた。
方向を求めるところが遅いみたいだったのでそのへんを修正してlargeに提出した。

largeに提出したやつ
http://ideone.com/D8gKS

D問だけで5時間ぐらいかかったので初心者ですね。

実行時間は20秒ぐらいだった。

あとで@hasi_tくんが「javascriptで」20秒、C++で3秒ぐらいでできたって言ってたので秀才ぐぬぬとか言ってた。

そのあとで-O2つけたら8秒ぐらいだった。

他の問題もおもしろかったです。
スポンサーサイト

GCJとAtCoderがあった

GCJの予選とAtCoderの残骸に寄ってみた。
競技プログラミングとかたまにやるとすごく虐げられておもしろい。
AtCoderの競技自体は盛大にぶっ壊れてたけど@chokudai先生の人徳あるし大丈夫だろう。

そのAtCoderはHaskellがサブミットできるみたいなのでまだまだへたくそなHaskellで書いてみた。

サブミットしたやつ
http://ideone.com/aKKdZ

なんかきたない。同じ文字が何回も出てきてるし。

ちょっと修正したやつ
http://ideone.com/4z7SA

出力まわりがイミフだったので少し整えてみた。タプルよりリストのほうが使いやすいのかな?

なんかmapのラムダがちょっと気になるので聞いてみた
https://twitter.com/#!/rydotyosh/status/191184500376604672

@SubaruG先生が内包表記でいいんじゃねって言ったから内包表記にしてみたやつ
http://ideone.com/PiVcW

@fumieval先生がflipって言ってたんだけど複雑すぎて理解できなかったorz

GCJはまだ解答出てないしまあいいや。

包絡線で遊ぼう

包絡線というのは、ある形状がパラメータとともに変化していくとき、
これらの形状に接するような曲線のこと。

日常生活に不可欠な包絡線だけど、どうやって計算するか知らないことに気がついたので
ちょっと遊んでみた。

参考:
物理のかぎしっぽ 包絡線
http://hooktail.sub.jp/mathInPhys/envelope/

つづきがあるっぽい »

Quick Hull

convex hullをquick sort的に計算するアルゴリズムだと。。。
かんがえたひとすげー。

テキトーに書いたコード:

convexhull.h

適応的しきい値

借りた本をスキャンしたんだけれど
真ん中のへこんだ部分がどうしても暗くなる。

本の印刷のコントラストが適度に低くて
しかも本が適度に分厚いと
真ん中のへこんだ部分がより大きく暗くなるので
全体の文字がつぶれないようにがんばると
どうしてもこうなる。

threshold0.png threshold0.png

そこで適応的にしきい値かけるソフトを探したんだけれど
openCVに標準で関数があったので
テキトーに書いてみた。
ていうか「適応的しきい値」とか「適応的二値化」ってマイナーなのかしら
あんまりソフトがひっかからんかったような気がする。

適応的しきい値をかけるとこういう感じになってくれてとてもうれしい。

threshold0.png threshold1.png

参考
http://opencv.jp/sample/filter_and_color_conversion.html#threshold

ソース

#include <cv.h>
#include <highgui.h>

int
main (int argc, char **argv)
{
IplImage *src_img = 0, *dst_img;
IplImage *src_img_gray = 0;

//args
// inputfile outputfile blocksize thresholdparameter
char *outfile="out.jpg";
int block=5;
double param=5;

if (argc >= 2)
{
src_img = cvLoadImage (argv[1], CV_LOAD_IMAGE_COLOR);
}
if (src_img == 0)
{
return -1;
}
if (argc >= 3)
{
outfile=argv[2];
}
if(argc>=4)
{
int b=atoi(argv[3]);
if(b<3)b=3;
b/=2;
b*=2;
b++;
block=b;
}
if(argc>=5)
{
double p=atof(argv[4]);
param=p;
}

dst_img = cvCreateImage (cvGetSize (src_img), IPL_DEPTH_8U, 1);
src_img_gray = cvCreateImage (cvGetSize (src_img), IPL_DEPTH_8U, 1);

cvCvtColor (src_img, src_img_gray, CV_BGR2GRAY);

cvAdaptiveThreshold (src_img_gray, dst_img, 255, CV_ADAPTIVE_THRESH_MEAN_C, CV_THRESH_BINARY, block, param);

cvSaveImage(outfile,dst_img);

cvReleaseImage (&src_img);
cvReleaseImage (&src_img_gray);
cvReleaseImage (&dst_img);

return 0;
}

«  | HOME |  »

カテゴリー

ブログ内検索

プロフィール

rydot

Author:rydot
かりんととお茶が好物の情報心理学好きのへたれCAD屋さん且つなんちゃってクリスチャン。

twitter @rydotyosh
hatenablog http://rydot.hatenablog.com/

images下およびdropbox下のリソースはccのはず。プログラムはオープンソースのはず。たぶんリンクフリー。

最近の記事

リンク

このブログをリンクに追加する

最近のコメント

最近のトラックバック

月別アーカイブ

RSSフィード

ブロとも申請フォーム

この人とブロともになる

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