近況

乱数講座 乱数講座というものに参加しました。 (9月7日) LCG Ring LCG Ringというプログラムを書きました。 (9月24日) LCG Ring ポケモンの乱数調整ユーザーなら見ただけで何を意味しているかは分かるはず。 ジョインアベニューのくじの解析 ポケモンBW2のジ…

LCGにおけるseedの検索を離散幾何に帰着させる

LCG(線形合同法)でseedを検索することを離散幾何の問題に帰着させるということを考えてみました。まず線形合同法の漸化式で使われる関数を(Ax + B) mod Mとしておきます。 seedを1増やしたとき、その一つ先のseedというのはA増えるか、A-M増えるかのどちらか…

重複なしにランダムに選んだ後ある特定のseed値になるようなseed値を求める その2 - oupoの日記に追記をしておいた。誰も興味がないようなネタだろうけど…。

確率計算

過去に書いたプログラムが、投稿したwebサービスから消えていたのでブログに残しておく。(2011年11月に作成)ブラックシティとホワイトフォレストの最初に決まる13人の中にグレースがいる確率を求めるプログラム (だったと思う)。だだぢぢさんがTwitterで話題…

asm.jsを試す

Firefoxで実装されているというasm.jsを試しました。これはJavaScriptのプログラムのうち、一部を非常に制限されたルールにしたがって書いてそこに"use asm"というディレクティブをつければ、その部分が非常に高速化されるというしろものです。以前、「メル…

『文章力の基本』(阿部紘久)より。 こういう作文、小中学校のときやってしまっていたなあ。

工作

緯度差1°あたりの経線弧の長さを求めるプログラム

高校地学の教科書を読んでいたら計算したくなったので。久しぶりのプログラミング楽しかったです。 計算結果は教科書に載っているものと微妙に異なる数値が出てきます。 楕円の弧長の近似値を求めるのに区分求積法を使いました。もっと良い方法がありそうで…

AtCoder Regular Contest #013 D問題 切り分けできるかな?

AtCoderの過去問としてARC#013をやってみましたが、さんざんな結果でした。 C問題は以下に解説がありますので、ここではD問題の解説をします。 http://bynatures.net/wordpress/2761/ D問題の問題文: D: 切り分けできるかな? - AtCoder Regular Contest 013…

AtCoder Regular Contest #014

AtCoder Regular Contest #014というものに参加しました。プログラミングコンテスト初参加でしたけど楽しめました。僕が提出した答案はこちら: http://arc014.contest.atcoder.jp/submissions/all?user_screen_name=oupoA問題とB問題はクリアして、C問題はナ…

Code Puzzle

任天堂が公開しているCode PuzzleのRuby版をやっています。 今裏問題をクリアしたところです。裏クリアのあとにまだ真クリアが残っているそうですが、まだどうやったらいけるのか見つけれていません。数独ソルバを書くのが疲れました…。

RGenGCの発表資料を読んだ

ささだこういちさんによるRGenGCの発表資料を読みました。 英語だったので条件反射的にウッとなったのですが印刷してボールペンを片手に辞書を開きながら読み通しました。 RGenGCとは何物か、その仕組みはどうなっているのかということに注目してまとめます。…

群論

「群論入門」は最後の読み飛ばしていい印がついている「多面体群」の節と、演習問題以外はやり終わりました。 代数学1 群論入門 (代数学シリーズ) 自分で立てた問題を考えてみました。 命題「正規部分群の正規部分群はもとの群の正規部分群である」は成り立…

factory-predictor その19 探索時に随時スケジュールをチェック

OneEnemyPredictorの各再帰ステップで随時スケジュールをチェックするようにしてみたところ随分速くなりました。 これで前回の記事のダム問題はもう用なしとなってしまいました…。100個のランダムなseedで実行してみて最悪時間が3.86秒となりました。入力は…

factory-predictor その18 ダム問題の完全ではない解

全ての選出と交換に渡る全ての敵の組み合わせを計算 その8 ダム問題 - oupoの日記 ダムがいくつかあり、グループAとグループBに分かれている。 水道局がいくつかあり、各水道局はグループA, グループBそれぞれ1つずつのダムとつながっている。 グループA, B…

factory-predictor その17 樹形図

http://oupo.github.io/factory-predictor/ 樹形図へのビジュアライズをしてみたにゃん。うーむ。面白みがないなあ

amazonのほしい物リストの並び替えGreasemonkeyスクリプト

アイテムを消去しておいて同じ内容のアイテムを追加するという方法になっております 最初は他のリストに移動してまた移動し直すという方法だったのですが、移動するにもアイテムに付けられたコメントなどの情報を引数として渡す必要があること、そして移動は…

factory-predictor その16 性格値の消費などの考慮とアイコン画像の表示

http://oupo.github.io/factory-predictor/simple.html ソースコード: https://github.com/oupo/factory-predictor/tree/master/ 性格値の消費や1戦ごとの消費などを考慮して実際の結果に合わせた。 また、結果をアイコン画像で表示するようにした。画像はve…

はてなダイアリーのTwitter通知を新規記事のみにする

はてなダイアリーのTwitter通知は投稿済みの記事の修正をしたときにはいちいち通知してはいらないなあと考えていました。そこでこんなGreaseMonkeyスクリプトを作りました。 その場編集のみ対応です。 // ==UserScript== // @name Adjust Hatena Diary Twitt…

地図を細かく広くキャプチャする

あくまで自分が使っている方法です。もっと便利な方法があるかも。 Windowsはウィンドウの大きさを画面の解像度よりも大きくできないので、VirtualBoxのUbuntuを使います。 Chromiumブラウザでhttps://chrome.google.com/webstore/detail/screen-capture-by-…

traceur-compilerでスクリプトをあらかじめコンパイルしておく方法

traceur-compilerを使って書いたプログラムを公開しようというとき、ユーザー側でコンパイラのプログラムのロードとスクリプトのコンパイルが走ってしまうのが速度の点で気になります。そこであらかじめコンパイルしておく方法を紹介します。 スクリプトをコ…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その15 JSへ移植!

GUIのプログラムを作るため、JavaScriptに移植しました。http://oupo.github.io/factory-predictor/simple.htmlソースコード: https://github.com/oupo/factory-predictor/tree/master/js-version (追記: 4/10) IEの8以下には対応していません。 今はこんな…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その14

アイテムと種族による衝突判定がなぜ難しいかって推移律が成り立たないからだよなー。…ん、あれ?ちょっと待って。出てくる範囲に同じ種族が複数ないという前提なら、推移律成り立つじゃん。衝突することはアイテムが一致することと同値じゃないか!っていう…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その13

衝突判定がIDのみによる場合は、結果がちょうど20件になるのは当たり前だよな、と気づきました。 乱数列にははじめから重複がないと仮定してもよくて、その上では「1件目の採用の前に何件スキップしたか」「1件目と2件目の間に何件スキップしたか」「2件目と…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その12

ナイーブ版を実装して結果を比較した後はもともとこういう記事を書くつもりでした。しかしナイーブ版による結果が予想外なものだったので予定が崩れました。 次はどうしよう。 ダム問題の貪欲法による解法を用いたこの1戦分の敵の組み合わせを出力するプログ…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その11

ナイーブ版を実装してみて、1つ前のプログラムによる結果がナイーブ版による結果を全て含んでいることを確認してみたところ...ナイーブ版による結果が毎回20件になるという不思議なことが起こりました。

全ての選出と交換に渡る全ての敵の組み合わせを計算 その10

ダム問題について考えていたところ、そういや1つの敵のエントリーの決定範囲には同じ種族が複数存在しないことが利用できるんじゃないかと思いつきました。 つまり、ダム問題においては、「グループAの各ダムとつながっている水道局はそれぞれ高々1個」とし…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その9

前のダム問題はカバーできる水道局の個数についての貪欲法ではうまくいかないことを確認しました。

全ての選出と交換に渡る全ての敵の組み合わせを計算 その7

考察めも。skippedが互いに衝突しない6個のエントリーである状況を考える。skippedの各エントリーはplayersと衝突する。ここでskippedの6つの種族のうちplayersとダブるものが2つ以下だったとしよう。すると、それ以外の4つはすべてアイテムによる衝突となり…

全ての選出と交換に渡る全ての敵の組み合わせを計算 その6

長い間放置していたけれど久しぶりに手をつけました。だいぶ忘れているのでまずはどういう状況だったか振り返るところから。復習メモ: 敵の手持ちを1体1体決めていくわけだが、プレイヤーの手持ちと衝突するかどうかが問題になる。プレイヤーの手持ちは未確…

筆者: oupo (連絡先: oupo.nejiki@gmail.com)