ARCを使用しない場合の参照カウンタ方式の処理 alloc クラスからインスタンスを生成, retainCount←1 retain retainCount++ release retainCount-- ARCが有向の場合、コンパイラがretainやreleaseを自動挿入してくれるので、retainやreleaseの記述は不要（と…
リポジトリ UFO Shooting Down Operation(AOJ No.0204) 円形のUFOがN個あり、分速で原点に向かってくる。 原点からレーザーを発射して、UFOを破壊する。レーザーは無限にのびるが、発射位置(原点)から距離R以内の範囲では、威力が出ずUFOを破壊できない。 初…
リポジトリ Traveling Alone: One-way Ticket of Youth(AOJ No.0200) グラフG(V,E)が与えられる。エッジのコストは料金(cost)と時間(time)の２種類ある。 クエリがk個、(スタートノードs、ゴールノードg、cost or time)の形で与えられて、再短時間または最小…
リポジトリ Byakko Delivery Company(AOJ No.0194) 東西方向の道路 M本、南北方向の道路 N本 からなる格子状のマップが与えられる。格子点は交差点を表す。 東西-南北の方向に信号機がある交差点もあり、一定の周期で青、赤が切り替わる。 市内の交差点間を…
リポジトリ Eleven Puzzle(AOJ No.0190) ■ 1 2 3 4 5 6 7 8 9 10 11 ■ の形に持っていく11パズルの最小ステップ数を答える。 ただし、20ステップ以内で解けなければNAと答える。 アルゴリズム ■の上下左右で次の状態は多くて8個ある。 ２０ステップ考えたと…
リポジトリ Stellar Performance of the Debunkey Family(AOJ No.0180) 要するにMSTの総コストを求める。 コード 前作ったライブラリ使っただけ、Prim法。 import java.util.*; public class aoj0180 { static final Scanner stdin = new Scanner(System.in)…
Dice Puzzle(AOJ No.0171) アルファベットが書かれたサイコロが８つ与えられ、それらを全て使って立方体を作ることを考える。 立方体を作る際、サイコロが接している面は同じアルファベットの大文字と小文字でなければならない。 与えられた８つのサイコロで…
リポジトリ Bubble Sort(AOJ No.0167) が与えられたて、右から確定していくナイーブなバブルソートをしたときの反転数を答える。 制約 アルゴリズム が小さいので普通にバブルソートしてもいいが、2299 -- Ultra-QuickSortの問題だと間に合わない。ソート(So…
リポジトリ Fenwick tree, binray indexed tree(BIT) が与えられたとき、 累積和 加算更新 の操作ができるデータ構造で、空間計算量は、構築にかかる計算量は(n回addするので)。 当然だが(頻繁に)更新を行わないのであれば、普通にでテーブル作った方がいい…
リポジトリ Sport Meet(AOJ No.0161) nチームのレースの成績データの形式で与えられる。 id：チーム名 番目のレースのタイム分、秒 ４つのレースのタイム合計で順位を決め優勝、準優勝、ブービー賞のチーム名を答える。 制約 タイム合計が同一にはならないよ…
Eclipseのテンプレート機能がcontrol+spaceで使えるはずだったんだが、なんかSpotlightっていうのがでてきた。 Macだとcontrol+spaceにSpotlightメニューのキーボードショートカットが割り当てられてるみたいで、Eclipseのショートカットよりこっちが優先さ…
リポジトリ Russian Dolls(AOJ No.0157) マトリョーシカのデータ系列系列が与えられる。 もし, ならマトリョーシカをマトリョーシカの中に入れることができる。 最大何個のマトリョーシカからなるマトリョーシカができるかを答える。 制約 アルゴリズム1 hか…
リポジトリ 数列が与えられたとき、からいくつかの項を脱落させた数列を考える。 においてが成立するときを最長増加部分列(Longest Increasing Subsequence;LIS)という。 版 を最終要素とするLIS長とすると [tex: DP_i = \max \left \{ \begin{array}{lr} DP…
リポジトリ グラフ理論（Graph theory） 単一始点最短路(Single-Source Shortest Path) 全点対間最短路(all-pairs shortest-path) 最小全域木(minimum spanning tree) 巡回セールスマン問題(Traveling Salesman Problem) グラフアルゴリズムで共通で使う要素…
リポジトリ グラフの基本要素はグラフ(Graph) - kanetaiの二次記憶装置のほうにまとめる。 計算結果の単一始点最短距離とバックポインタ。buildPathで最短経路を構築する。 /** Results of Single-Source Shortest Path (SSSP) Algorithm */ public static c…
リポジトリ Triangle and Circle(AOJ No.0153) １つの三角形(頂点座標×3)と１つの円(中心座標＋半径)が与えられたときの位置関係を↓で求める。 円が三角形に含まれる場合 a 三角形が円に含まれる場合 b それ以外の場合で、共通部分がある場合には c 共通部分…
リポジトリ TODO: distanceLP distanceLL distanceLS 点間距離だけでなくいろいろあった方が便利なので作っとく 線分と点 のへの正射影を求めて、が上にあれば、 無ければ、 //instance method of Point class public final double distancePS(Line s){ Poin…
正射影(orthograph, orthogonal projection) 射影(projection)、鏡映(reflection) 一点からある直線または平面上に下ろした垂線の交点(垂線の足:foot of a perpendicular)。図形(点の集合)についても、図形上のすべての点の垂線の足の集合を正射影と呼ぶ。 …
メモ 後でまとめる 作業ディレクトリとrev svn diff -x -b -r 4117 intersectSC old ver. とする。 の場合 なら交差、なら非交差 かつの場合 なら交差、なら非交差 ※このとき常に、 その他の場合 なら交差、なら非交差 ※ //instance method of Line class pu…
リポジトリ Twin Prime(AOJ No.0150) nが与えられて、とは素数となるを求める 制約 コード その場で求めても十分間に合う import java.util.*; public class aoj0150 { static final Scanner stdin = new Scanner(System.in); static final int N = 10001; p…
Androidアプリ作ってて、コンパイル時に「Java heap space」みたいなエラーメッセージがでたので、そのときの対処。 多分、antとかで分割コンパイルすればいいだけの話だけど、 めんどいので、ヒープサイズ変更してみる。eclipse.iniのヒープの最小 Xms と最…
表示 defaults write com.apple.finder AppleShowAllFiles true killall Finder 非表示 defaults write com.apple.finder AppleShowAllFiles false killall Finder
リポジトリ Lupin The 4th(AOJ No.0146) 屋敷からmの距離の蔵iに１個20kgの宝が個ある。 蔵は全て、屋敷から同じ方向に向かって一直線上にある。 蔵にある宝を拾いながら、全ての蔵をまわる。 始点と終点はどこでも良い。 宝をkg持っているときの移動速度はm…
リポジトリ Spiral Pattern(AOJ No.0141) nが与えられて、n×nの中にぐるぐる模様を書く。 ぐるぐる模様は、左下から始まって１行または１列分開けて中心に向かって'#'で描かれる。↑のリンク参照 アルゴリズム 進行方向とその４近傍(自分がいる位置を除く)を…
リポジトリ Rotation of a Pattern(AOJ No.0133) 8×8のパターンを右回転 コード import java.util.*; public class aoj0133 { static final Scanner stdin = new Scanner(System.in); static final char[][][] pat = new char[4][8][8]; public static void …
なんかよく忘れるのでメモ ソート ファンクタ（無名クラス） Arrays.sort(array, fromIndex, toIndex, new Comparator<T>(){ @Override public int compare(T o1, T o2){ return o2 - o1; //降順 } }); Comparableインターフェース実装 class T implements Comp</t>…
リポジトリ Jigsaw Puzzle(AOJ No.0132) のジグソーパズル. ジグソーピースがn個与えられる。 プレイヤーがいくつかのジグソーピースを選ぶので、そのピースでジグソーパズルを完成できるかどうかを答える。 ジグソーピースは90度ずつ回転できる。 制約 アル…
C++での乱数の使い方をまとめとく。 rand, srand Cの標準ライブラリを使う方法。srandでシードを設定して、randで 0以上, RAND_MAX以下の整数乱数を発生させる。 良くやるのはの time_t time(time_t *timer); を使うやり方。引数のtimerには戻り値と同じ現在…
Chapter 21. Boost.Random - 1.51.0 様々な分布の乱数の生成できる。 C言語標準のrand, srandはグローバル関数となっているが、 Boost Randomでは乱数計算はvariate_generatorオブジェクトでまとまっていている。 C+11で、randomが使えるようになったが、Boo…
C++11 デフォだとC++11が使えるようになっていないが、Build Settingsで切り替えられるみたい(参考) 割と簡単だった。 [Build Settings]を開いて、[All]にスイッチする(多分始めは[Basic]になっている) [Build Options]のセクションでコンパイラを[Apple LLV…
