全ソースファイル: gasshuku_java.zip
各単語が検索文字列中に出現した回数と文章中に出現した回数の積の平方根の総和を求める。
ソースファイル: Startup.java
検索文字列と文章のそれぞれについて、検索文字列中に出現する各単語を、単語を表す文字列をキー、出現回数を値としてハッシュテーブルに登録し、スコアを計算します。
文章の区切りはnextCharメソッド内で検出し、'-'に変換して返します。それ以外の特殊文字はnextCharメソッドで読み飛ばしています。
与えられたいくつかの長方形を重ね併せた図形の面積を求める。
ソースファイル: Atlantis.java
C#版のアルゴリズムではなく、合宿の時に矢島さんが使ったアルゴリズムで作りました。ソートする部分が支配的なので、計算量はO(n2log2)で、C#版よりずっと効率的になっています。
Erdosの共著者をErdos number 1とし、Erdos number nの人の共著者をErdos number n+1とする。著者のリストと本のタイトルの一覧から、与えられた人のErdos nubmerを求める。
ソートファイル: Erdos.java
入力ファイルを読み込んだ後でerdos.setNumber(0)を呼び、この中で、erdosを0とした時の値を再帰的に求めています。
「２以上の整数のなかから交互に選んでいき、選べる数が無くなったら負け。ただし、すでに選ばれた数の倍数と、それらの倍数の和は選ぶ事ができない。」というルールのゲームで、残っている数のリストを入力とし、必ず勝てる方法の次の一手を全て求める。
ソースファイル: Numbergame.Java
全ての可能性を探索して解を求めます。
探索中に一度出現した状態については、「必ず勝てる状態」「負ける可能性がある状態」の2つのいずれかに分類してそれぞれリストに保持しておき、同じ状態が再度出現した時には以前の結果を使います。
この部分が、C#版より効率的になっています。
2nビットの二進数から、nビットの二進数を取り出す。元の二進数を循環されて考えると、2n個の二進数を取り出すことができる。このsn個の数字が全て異なっている物をOuroboros numberと呼ぶ。
2つの整数nとkを与えられたら、nに対する最小のOuroboros numberのk番目の値（kビット目からk+n-1ビット目までを取り出した数字）を求める。
ソートファイル: Ouroboros.java
上位nビットには始めに0を入れてしまいます。その後は単純なバックトラックによる探索です。まず0を試し、同じ数が2度出てきてしまう場ならば1で試します。それでも駄目ならバックトラックします。
あるnビットの数Nがすでに出てきているかどうかはBitSet型の変数flgのNビット目が1かどうかで判断しています。
また、flgと、求めた数を入れる変数dataは、常に同じオブジェクトを使っているので、バックトラックするときにはflgのデータを元に戻しています。dataの方は次の結果が上書きされるので何もしていません。
合宿の時にバックトラックが必要ないというはないが出ましたが、
列車の時刻表から、目的地にもっとも早くつく方法を探す。同じ時間に方法が複数ある場合は出発時間が遅い方を解とする。
ソースファイル: Railroad.java
問題を簡単にするために、全ての列車は2つの駅の間のみを移動するものとし、複数の駅に停車する列車は複数の列車に分割して表しました。その上で、各駅にもっとも早くつく時間を再帰的に調べて目的地への到着時刻を求め、次にその時間に目的地につくためのもっとも遅い出発時刻を同様に調べています。
素数以外で、各桁の数字の和と、素因数の各桁の数字の和が等しい整数をSmith Numberとする。与えられた数より大きい最小のSmith Numberを求める。
ソースファイル： Smith.Java
C#版では入力の値によって必要な範囲の素数を求めていましたが、入力は8桁までと分かっているので、始めに1012未満の素数を全て求め、これを使って素因数分解をすることにしました。
これで素因数分解できるのは1014=104060401までです。一方、最大の入力99999999に対する出力は100000165なので、これで正しく計算できていることが分かります。
最終更新日：2003/10/26