制作物まとめ
作ってきたもの一箇所にまとめたくなったのでまとめ
(趣味でやったやつだけ)
スライドパズル (2009)
部活でつくったやつ (2010)
- Google Earth のAPIいじって思い通りに移動できるようにしたり
- OpenGLでGUIつくったり
- ちょっとweb系(PHP)書いたり
農家の逆襲 (2011)
インターン (2012)
- 3週間ぐらいwebアプリつくってた
ファ〇マドア (2012)
- ドア付近に設置しておいて、ドアの開閉をスイッチにしてファ〇マの入店音が鳴る
- 完成して意気揚々と設置したけどうるさいので一日で取り外した
- エフェクトーンっていう似たものがあるらしい
LifeGame3D (2013)
- 思いついたから作ってみたシリーズ(3)
- ライフゲームの結果の履歴を奥行きにプロットしたやつ
- 1分ぐらい見てたらなるほどーってなって飽きた
- これもProcessing
5E Fighter (2013-2014)
Androidアプリ (2014-2015)
- バイトで作ってた
- カメラまわりに詳しくなった
いもあつめ (2015)
- 芋を転がして集めて大きくして油にダイブしてコロッケを作る
- 正直あたまがおかしかった
- Unityでさくさく実装
3Dビリヤード (2016)
- 思いついたから作ってみたシリーズ(4)
- ビリヤードを3次元に広げてみたやつ
- 単純に難しかった
- Unity
制作中 (2016-2017)
- アクリル板を削ったりしている
nanって何なん
メモです
チェック環境 : Visual Studio 2015 Update 3
Releaseビルド
infからnanをつくる
const float nan = numeric_limits<float>::quiet_NaN(); const float inf = numeric_limits<float>::infinity(); printf("nan = %f\n", nan); printf("inf + inf = %f\n", inf + inf); printf("inf - inf = %f\n", inf - inf); printf("inf * inf = %f\n", inf * inf); printf("inf / inf = %f\n", inf / inf); [output] nan = nan inf + inf = inf inf - inf = -nan(ind) inf * inf = inf inf / inf = -nan(ind)
inf-infがnanっていうの、言われてみれば確かにって感じだった
nanをチェックする
printf("isNan(nan) = %s\n", isnan<float>(nan) ? "true" : "false"); printf("isNan(inf-inf) = %s\n", isnan<float>(inf-inf) ? "true" : "false"); [output] isNan(nan) = true isNan(inf-inf) = true
「nan」と「-nan(ind)」という表記ゆれがあったが、isnan()ではどっちもnan判定してくれるらしい
オーバーフローからinfをつくる
const float max = numeric_limits<float>::max(); printf("max = %f\n", max); for(int i=0; i<100; i++) { float x = max + pow(10.f, i); if( isinf(x) ) { printf("max + 10^%d -> inf\n", i); break; } } [output] max = 340282346638528859811704183484516925440.000000 max + 10^32 -> inf
オーバーフローによるinf化、maxに足して起こるのは10^32ぐらいが目安
ヒープ汚れによる初期値nan
class A { public: explicit A() {} public: float a, b, c; }; { A* class_a = new A(); class_a->a = class_a->b = class_a->c = nan; printf("1: addr=%p a=%f b=%f c=%f\n", class_a, class_a->a, class_a->b, class_a->c); delete class_a; } { A* class_a = new A(); // メンバ初期化しない printf("2: addr=%p a=%f b=%f c=%f\n", class_a, class_a->a, class_a->b, class_a->c); delete class_a; } [output] // だいたいこんな感じになる 1: addr=00919F28 a=nan b=nan c=nan 2: addr=00919E68 a=0.000000 b=0.000000 c=0.000000 // だが、15回に1回ぐらいの頻度で同じアドレスにメモリを確保し、初期値がnanになる 1: addr=00DEA200 a=nan b=nan c=nan 2: addr=00DEA200 a=nan b=nan c=nan
絶対に変数初期化しような
平方根、指数、対数
const float min = -max; const float eps = numeric_limits<float>::epsilon(); printf("sqrt(-eps) = %f\n", sqrt(-eps)); printf("sqrt(inf) = %f\n", sqrt(inf)); printf("exp(max) = %f\n", exp(max)); printf("exp(inf) = %f\n", exp(inf)); printf("log(0) = %f\n", log(0.f)); printf("log(-eps) = %f\n", log(-eps)); printf("log(inf) = %f\n", log(inf)); [output] sqrt(-eps) = -nan(ind) // 少しでも負ならnan化 sqrt(inf) = inf exp(max) = inf // inf化 exp(inf) = inf // めちゃくちゃ大きくなるが、数値ではあるのでnanではない log(0) = -inf // 0なら-inf log(-eps) = -nan(ind) // 少しでも負なら未定義 -> nan log(inf) = inf // logは収束しそうな形してるけど収束しない
ちなみにnan突っ込んだときは全部nanになる (伝播する)
ICPC2015 アジア地区つくば大会 参加記
チームUNYOLERの1人として参加しました
国内予選が33位の大学内3位と普通なら落ちてるレベルなんですが謎のパワー(ホスト校枠)で通過してました。やったぜ。
メンバー
- negi_magnet : やるだけだけ解けるマン。コンテスト中は大体実装
- everysick : 解法の考案が強い(という印象)。コンテスト中は読解+考案+実装
- イイモデさん(仮称) : UNYOLERの名付け親。その名の意味は本人にも分からない。コンテスト中は読解+考案
11/28(土)
- 会場までチャリで30分ぐらいなので昼まで寝てた
- 会場でメンバーと合流して受付
- とりあえず机上にあった企業からの品を山分けする(いいねマグネットとかはじゃんけんで決めた)
キーボードの練習セッション。Endを押しまくる- 色々なダメケース(array[-1]とか)を出してみる。REだろと思ってたものがWAと表示されて戦慄
- SampleChallengeはサンプルを投げなかったので負けた
- 筑波大生は宿が無いから自宅に帰ってねと通告される。泊まりたいかどうかを事前に聞かれすらしなかったので若干の不満があった(泊まりたいとは言ってない)
- 🍣
11/29(日) コンテスト中
- 本番だァァァ
- 最初に自分が環境構築、イイモデさんがA、sickくんがBを読む
- 構築した後、Aの概要を聞いてそのまま書き始める。10000ぐらい回せばええやろって適当に考えて書いた(適当すぎたので反省ポイント)。AC
- Bの概要を聞く。左の円から順に位置決めればよさそうと思って書く。立式が面倒になって二分探索した(完全に頭が働いてない反省ポイント)。AC
- Cはトラウマ(サンプル一致後のWA&TLE&RE連発)
- Cのバグに悩んでいた頃、Dは1次元にして考えればいいとsickくんから聞き、範囲の右端が小さい順にソートするやつでいけそうと感じる
- イイモデさんはEを考えてた
- Cの実装をsickくんと交替してDの紙コーディング開始
- C通らないので紙デバッグしてもらいつつD実装
- D投げる→WA→バグ見つける→直して投げる→WA→ｳｫｫｱ
- CもDもデバッグが間に合わず終了。2完
- ロスタイム中にDのコード眺めてたらバグ発見して生殺しだった
11/29(日) コンテスト後
- 疲れからか、不幸にも解説中に寝落ちしてしまう
- 表彰式の途中でCを書いてAOJの方に投げてみたけどやっぱりWA
- 焼きそばおいしい
- Googleのクイズが面白かった
- 帰ってからCとDが通った。CはIMPOSSIBLEじゃないときに出力する数の計算がダメだったっぽい
まとめ
- 2完31位でした
- もっと頭を使おう
- 今年度で競プロ引退なので、最後に地区行けてよかったなーという感じです
CODE FESTIVAL 2015 参加記
CODE FESTIVALという競プロのお祭りに参加してきました
予選A : 4完136位(ここで通過)
予選B : 寝過ごした
行き路
筑波からだと1.5hぐらいで着くので8時起きの8時半出発
電車で隣になったオッサンから刺激臭がしてつらみポイントが貯まる
ちょっと歩こうかと思って神谷町で降りたら会場まで登り坂になっててつらみポイントが貯まる
到着して席に着くと隣が知り合いでつらみポイントが減る
本戦
[A]
文字列の長さ見るだけ
[B]
Nが小さいので愚直に確率計算 →なんだかWA
doubleの誤差のせいかと思って場合の数計算 → オーバーフローしてた
(ここで一旦飛ばしてC〜E解く)
確率計算の時の÷6を÷8にしてみる → AC
なにこれこわい
[C]
貪欲な気もしつつ念のためDFS
(ペナルティ無いし、ダメ元で貪欲投げても良かったな…)
メモ化してなくてTLE → メモ化したらAC
[D]
減るとしても1だけっていうのに早めに気づけたのが幸い
一番重複してる区間群の最初と最後を探して、その最初と最後を内包するボタンがあったら(最大重複数-1)、なかったら(最大重複数そのまま)。って感じで実装
最大重複数を配列で持つと配列への入力時にTLEしそうだったので累積和で持った(実際に最大重複数をチェックするときは配列の頭から順に見るのでオッケー)
forの範囲ミスって2WA生やしつつもAC
[E]
後ろから適用が面倒に感じたので処理の最初と最後に文字列反転させることにした
手計算してみたら！の前にある-には意味が無いことに気づくので最初に消す
「--」→「」、「!が奇数個」→「!」、「!が偶数個(>0)」→「!!」ってルールで変換
途中で3WAほど食らったけど、そのたびに適当なケース試して手計算と違ってデバッグして…を繰り返した(結構すぐWAケースが見つかったので幸い)
順位表見たらGがそこそこ解かれてたので見てみる → ナムアミダブツ！1,000,000,007だ！
(1,000,000,007というか数え上げへの苦手意識ほんとにどうにかしないとまずい)
いろんなケース考えたりしてたら時間がきて終了
結果として5完の119位でした。Bでつまづいたのが結構大きい…
でもパーカー圏内なので満足です
自由時間とか
両日ともほぼセッション1のとこにいました(うなぎ、ペアプロ、LT、rngと聞いてました)エキシビションマッチは座席の目前にrngさんのディスプレイがあったのでずっと見てました。タイピングめっちゃ速い…(速いというか、記号や数字が混ざっても速度が落ちてないように見えた)
ボドゲとか書道はセッション見てたらやる時間なかった
ホテルに移動。22時台からごちうさを放送してるTOKYO MXに感激する
終物語→あの花→うたわれと見て就寝。そういえばあの花の映画見てないな…
ホテルのお湯出るマシーンの隣にプラスチックのコップが置かれてたの最高にクソUIだと思います
あさプロ
眠くて難問やると寝そうだったのでeasyからやっていくことにした
[A]
iを100までループさせてi*i>=Nになるときにi*i-Nを出力するだけ
[B]
文字列を道端で拾う世界とは一体…うごご
長さが奇数なら無理で、偶数ならs[i]とs[i+n/2]の不一致数を数えるだけ
[C]
ソートして点が高い方からk-1個選んでもにょもにょ
n==kのときが若干厄介で、0点でもいい判定をするときにa[k-1]を足してテストしていたが、n==kだとa[k-1]が2度足されるのでバグってしまう
入力1行目のN K M Rを見てM.K.Rを連想し頭の中でガチマッチが始まった
[D]
2重ループで始点を決めて、メモ化DFSで最大長を探索
メモ化してなくてTLEしたあたり全く成長してない…(本戦でも同じことした)
easy全完したのでmiddleに移動
[E](MiddleのC)
白は黒が置いた方にしか置けないので黒のことだけ考えればいい
ひっくり返す白の数が少ない方を選ぶだけでよかった(貪欲法)
黒連続何個、白連続何個、とかいうのはdequeで管理
[F](MiddleのD)
凹凸をなるべく均す方が少なくなるなーとか考えてたりしたけど結局時間切れ
5完してeasy20位、middle34位でした
チーム対抗リレー
ゑって文字が入ってる名前のチームです(忘れてしまった)
自分はDのピザを担当。上からk番目と下からk番目とを足したの全部一緒じゃね？ って気づいたら3行実装でAC
あとはFのグラフ列挙を手伝ったり、WAのコードとにらめっこしてたら終わった
ハッピーアワーはトイレ行ってたら実質終わってました(表彰が始まってた)
帰り路
久々に神田でラーメン食うぞと思ったけど値段的に松屋2回分だと気づいて足が止まった
結局つくばに帰って松屋に行きました。茄子のやつ美味い
まとめ
こどふぇす楽しいので行きましょう。青コーダーでも大丈夫です
来週もオンサイト(模擬地区)だ、がんばるぞい
ICPC2015国内予選参加記
参加してました。チーム「UNYOLER」です
ICPCとは、大学間対抗の競技プログラミングコンテストです。詳しくはこちら
A問題
- チームの人に任せた
- ささっと一発AC
B問題
- チームの人に任せた
- こっちも一発AC
C問題
- 自分の担当。インデントで括弧を表した数式を計算した結果を返す、みたいな問題
- 入力が何行目かのi、処理するインデントレベルlv、計算するパターンopを引数にしたsolve(i, lv, op)みたいなのを作って再帰的に処理してた
- やったぜ一発AC
解法考えるフェイズ
- D問題
- 買うか買わないかで2択だとパターン最大2^100で終わらんし……
- 小銭それぞれの数は関係する…？
- E問題
- お前は何を言ってるんだ(画像略)
- スレッドの実行順(10!) * 実行シミュレーション(10^4 * 10) = 終わらんこれ
- チームの人が書いてたけど結局途中でDに移った
- F問題
- なるほど、わからん
- ほか 見てない
D問題
- DP[小銭の合計額][今いる店舗の番号] = pair(500円玉の枚数, 購入価格) でいけるんでは
- 自分が書き始める
- サンプル合わねぇ
- 実行出力とサンプル出力と比較しながらデバッグ
- サンプル全一致、提出
- WA(デデドン)
- なんだなんだって思いながら色々変えて再提出してたがWA取れず、時間切れ
結果
- 3完33位、大学内3位とかいう3に恵まれた結果でした
所感
- DPに弱い(確信)
- コーディング速度は良い方かもしれない(3完勢の中で上の方だった)
- n完早解きっていう結果になることが多いので、もっと複雑な問題を解けるようにしていきたい
vector<bool>
「vector< bool >は省メモリだけど遅い」と言われますが、どのぐらい遅いのか。検証します
検証条件
- vector< bool >で宣言した配列と、bool[]で宣言した配列それぞれについて、以下のコードを実行する
// 10^8回の代入 for(int i=0; i<10000; i++) { for(int j=0; j<10000; j++) { v[j] = (i%2); } }
- 開始から終了までにかかった時間と、使用メモリ量を計測
- 時間はclock()を使ってμs単位で計測(読みづらかったのでmsに換算)
- 使用メモリ量はsizeof(v)を使用
- 生成にかかる時間は対象外
検証結果
| 型 | メモリ使用量[byte] | 実行速度[ms](100回計測した平均値) |
| vector< bool > | 24(※1) | 1703.82 |
| bool[] | 10000 | 494.2 |
めっちゃ遅い(3.45倍ぐらい)
(※1 : vector< bool >をsizeof()すると実際のデータ格納領域は含まれないらしい
ただ、vector< bool >は1ビット単位で管理してると聞いた覚えもあるので、単純に考えると1/8ぐらいになってるのかも…？)
せっかくなので他にも検証
| 型 | メモリ使用量[byte] | 実行速度[ms](100回計測した平均値) |
| vector< bool > | 24(※1) | 1703.82 |
| bool[] | 10000 | 494.20 |
| vector< bool >(iteratorでループ) | 24(※1) | 2729.79 |
| bitset | 1256 | 1424.48 |
結論：vector< bool >は遅い(確信)
ちなみにここまで遅いのはboolのときだけです。intとかなら結構マシ
MikuMikuWatch製作記
この記事は「coins Advent Calendar 2014」の14日目の記事です。
AdventCalendarから来られた方のために簡単に自己紹介します。
ねぎです。3編生です。概念としての初音ミクが好きです。
What is "MikuMikuWatch" ?
MikuMikuWatchとは、開発中のAndroid Wear向けアプリケーションです。
腕時計型の端末の画面上に、時計と一緒に初音ミクを映します
→ 日常生活の中でふと時計を見ると、初音ミクが生活している様子が伺えます
→ 幸せになります
→ やったぜ。
製作記
- 10月初頭、ひらめいた
MikuMikuWatch作ります
— ねぎ (@negi_magnet) October 2, 2014時間帯によって絵が変わって、ミクさんの生活が垣間見れるイメージ
— ねぎ (@negi_magnet) October 2, 2014- ゴリゴリ実装する
いいんでねーの pic.twitter.com/6XOV1MqXhZ
— ねぎ (@negi_magnet) October 2, 2014(ドット絵なのは自分がドット絵じゃないとまともに描けないからです)
進捗です(寝起き→朝食) http://t.co/zmVbNLdKcF
— ねぎ (@negi_magnet) October 3, 2014時間帯によって絵が変わります
- 権利的にはクリプトンファミリーいけるんだよな…
リンちゃんなう #MikuMikuWatch pic.twitter.com/N9VKjZOsXN
— ねぎ (@negi_magnet) October 14, 2014製作で困ったポイント
- 初音ミクという概念の具現化
初音ミクの1日の生活について考える必要がある
— ねぎ (@negi_magnet) October 2, 2014— ねぎ (@negi_magnet) October 3, 2014同じ睡眠でも布団で寝るのとプラグ差してスリープモードに入るのぐらい変わってくる
— ねぎ (@negi_magnet) October 3, 2014初音ミクというのは外見と声以外の公式設定がほぼ存在せず、1人1人が考える初音ミクというのには差異があります。
そのため、このアプリで初音ミクの1日を描くというときに、「これは自分が考える初音ミクであって、真の初音ミクではないのではないか…？」という疑念と葛藤に襲われました。
(考えている本人は大真面目です)
最終的に、このアプリに登場する初音ミクは自分が考える初音ミクであると割り切りました。
- 圧倒的絵心不足
- 320x320というキャンパスに対して32x32のドット絵を貼り付けていくスタイル
- 描いていくうちに絵柄が変わってきて昔のを描き直したりしてるとつらいことになった
現状
- プログラムはほぼ完成しました
- 絵を描く時間とスピードが足りないッ…！
- ということで製作停滞中。描ききったらGoogle Playに出したいです
- (2015/7/25追記) Google Playで公開しました
https://play.google.com/store/apps/details?id=negi.magnet.mmw
