C#で書いてあるので、コンパイルするには.NET Framework SDKが必要です。
Microsoftのホームページからダウンロードできます。
全ソースファイル: gasshuku_cs.zip
各単語が検索文字列中に出現した回数と文章中に出現した回数の積の平方根の総和を求める。
ソースファイル: startup.cs
検索文字列と文章のそれぞれについて、検索文字列中に出現する各単語を、単語を表す文字列をキー、出現回数を値としてハッシュテーブルに登録し、スコアを計算します。
入力ファイルの終了を検出する部分は後から追加したので、少し強引な方法になってしまっています。
与えられたいくつかの長方形を重ね併せた図形の面積を求める。
ソースファイル: atlantis.cs
与えられた長方形を、他の長方形と重ならないような複数の長方形に分割してから面積を計算します。
合宿最終日に「計算量が指数関数になりうるのでは」という発言をしましたが、これは全くの勘違いでした。
入力の長方形の数をnとすると、分割された長方形の数はO(n2)なので、1つの長方形の分割数は平均してO(n)という事になります。したがって、1つの長方形を処理するのに必要な時間はO(n3)で、全体の計算量は(n4)になります。
実際に時間を計測してみたところ、確かにこの通りになっていました。
「２以上の整数のなかから交互に選んでいき、選べる数が無くなったら負け。ただし、すでに選ばれた数の倍数と、それらの倍数の和は選ぶ事ができない。」というルールのゲームで、残っている数のリストを入力とし、必ず勝てる方法の次の一手を全て求める。
ソースファイル: numbergame.cs
全ての可能性を探索して解を求めます。ただし、探索の途中で出現した状態をリストに保持しておき、同じ状態が再度出現した時には以前の結果を使います。
素数以外で、各桁の数字の和と、素因数の各桁の数字の和が等しい整数をSmith Numberとする。与えられた数より大きい最小のSmith Numberを求める。
ソースファイル： smith.cs
調べる数の平方根以下の素数を全て求め、素因数分解して調べます。一度求めた素数のリストは保持しておき、次に調べる数の方が小さい場合は以前に求めたリストを使います。リストを更新する時は、以前に求めたリストは破棄して全て求め直します。（再利用するようなプログラムを書くのが面倒だったため。）
ただし、実際には調べる値を一つずつ大きくしていくので、素数の再計算はかなりの頻度で発生しています。
最終更新日：2003/10/26