優先度付きキューに値を追加する操作と取り出す操作はO(logN)で行えるの。グラフにおけるノードの数をV、エッジの数をEとすると優先度付きキューを用いたダイクストラ法の計算量はO((V + E)logV)となる。今回、2 ≦ V ≦ 10^3, 1 ≦ E ≦ V(V-2)/2なので**O(10^6log10³)となる。また、この処理をクエリーの数q(1 ≦ q ≦ 10)だけ行うので最終的な計算量はO(10^7log10³)となる。

クラスのプロパティによってオブジェクトをソートする

今回優先度付きキューに入れるのは自作したクラスのオブジェクトだ。オブジェクトの持つdistanceプロパティの値によってソートさせたい。こういう時は自作したクラスに対してimplements ComparableとしてcompareToメソッドを実装することで実現できる。

ソースコード

2017-05-08

Connected Cell in a Grid in Hacker Rank

Hacker Rank Java DFS 深さ優先探索行列

問題

R行C列の行列が与えれれる。行列の各マスは0か1のどちらかが書かれている。1の島の大きさ(マスの数)が最大を出力する問題。ここで島の定義は、水平方向、垂直方向、斜め方向で1が隣同士ならばそれらは１つの島とすることができる。

www.hackerrank.com

解法

頑張って深さ優先探索をする

2017-05-08

Merge Sort: Counting Inversions in HackerRank

Hacker Rank Java Merge Sort

問題

Int型の配列が与えられ、ソートするために必要なスワップの数をカウントするという問題

www.hackerrank.com

解き方

O(N²)の解法

この解法はバブルソートの要領で解く。 forループを２重にしてiを0 ≦ i < arr.length, jをi+1 ≦ j < arr.lengthのようにループさせた時に、arr[i] > arr[j]の条件でカウントしてあげると解ける。

O(NlogN)の解法

この解法はマージソートの要領で解く。２つの配列をマージさせる時に、左側の配列の値が大きければ、移動させる距離の分だけカウントさせてあげることで、スワップの回数を取得することができる。

ソースコード

2017-05-02

Google code jam 2017 Problem A. Alphabet Cake 解法

Google Code Jam codejam PrintWriter FileReader

問題

Dashboard - Round 1A 2017 - Google Code Jam

R行C列のグリッドが与えられる。各マスには?か異なるアルファベット１文字が書かれている。この時、以下の条件で？のマスを別のアルファベットで埋めるプログラムを書く。

条件

？には入力値として既に登場しているアルファベットのどれかを埋める
同じアルファベットで描かれる図形は四角形で無ければならない

例

G??
?C?
?JJ
の場合
GGG
CCC
JJJ
が回答の１つとなる。

解法

まず、各行に着目し、行rが全て？の場合と１つでもアルファベットが含まれている場合で場合分けをする。

行rにアルファベットが含まれている場合

この場合は、登場したアルファベットの両サイドの?をそのアルファベットで埋める。

行rが全て`？`の場合

この場合は、前の行をそのままコピーしたもので埋める

ソースコード

2017-04-28

Javaのメモリー構造とガベージコレクションについて

Java メモリー Java VM Java仮想マシンガベージコレクション

JavaVM

Java VMとは…

Java 仮想マシン (Java virtual machine、Java VM、JVM) は、Java バイトコードとして定義された命令セットを実行するスタック型の仮想マシン。APIやいくつかのツールとセットでJava実行環境 (JRE) としてリリースされている。この環境を移植することで、さまざまな環境でJavaのプログラムを実行することができる。

Java VMとは - IT用語辞典 Weblio辞書

今回はこのJava VM内部のメモリー構造をまとめる。

JavaVMのメモリー構造

JavaVMのメモリー構造は以下の要素で構成されている。

Javaヒープ：アプリケーション・プログラムのオブジェクトを格納する領域。この領域は詳しく後で述べる。
Permヒープ：クラスやメソッドなどのメタデータを格納する領域。
Cヒープ：OSネイティブなメモリ領域。
スレッドスタック：OSネイティブなメモリ領域。

Javaヒープ

Javaヒープ領域は大きくNewとOldという領域に分かれている。 NewはさらにEdenとSurvivor**という領域に分かれている。

Javaヒープでは、新しいオブジェクトはNewへ古いオブジェクトはOldに格納されている。具体的には、新しく生成されたオブジェクトはまず、NewのEdenに格納される。その後、ガベージコレクション(以下CG)という仕組みによって、オブジェクトは破棄されるか、SurvivorやOldに移行される。

ガベージコレクションの仕組み

GCとは、不要になったオブジェクトを自動的に破棄する仕組みである。この仕組が無いと、不要になったオブジェクトがメモリー上にずっと保持されたままになり、メモリー領域がなくなってしまう。

GCの処理の流れは以下の通りだ。

新しく生成されたオブジェクトはNew領域のEden領域に格納される。
Eden領域がいっぱいになったら、Copy GCという機能が発生する。
Copy CGとはNew領域を対象に、使用済みのオブジェクトは破棄される。またまだ必要なオブジェクトはSurvivor領域に移行される。
一定回数以上のCopy GC後、まだ使用され続けているオブジェクトはOld領域に移行される。
Old領域がいっぱいになるとFull GCという機能が発生する。FullGCとは、Javaヒープ、Permヒープの全体を対象に不要となったメモリーを回収する。

このようにJavaVM内では効率よくメモリーが使われている。

参考

Java Review：JavaVMのメモリ管理をマスターする (1/2) - ITmedia エンタープライズ

マツシタのお勉強

welcome to my engineering blog

問題

解法

問題

解法

問題

解法

計算量

クラスのプロパティによってオブジェクトをソートする

問題

解法

問題

解き方

O(N2)の解法

O(NlogN)の解法

問題

解法

行rにアルファベットが含まれている場合

行rが全て？の場合

JavaVM

JavaVMのメモリー構造

Javaヒープ

ガベージコレクションの仕組み

参考

O(N²)の解法

行rが全て`？`の場合