問題リンク Combination of Number Sequences 解法 AOJ0008のときにほのめかしたキャッシュを使わないと厳しい問題ですね。 単純に解こうとするとO(n!)です。 9!=3*10^5くらいならば時間的に余裕ですが最大ケースである10!だと厳しいです。 なのでn=10のとき…

問題リンク Drawing Lots II 解法 アミダの状態とスタート地点を与えたときにどこにたどり着くかを返すメソッドを用意しました。 元の状態でゴールに行けなかったら棒を1本加えます。 加える順番は上の段からで、加えられる箇所は両隣に棒が存在しないときで…

問題リンク Enclose Pins with a Rubber Band 解法 n個の頂点のうち、凸包に使われない頂点はいくつあるかを求める問題です。 頂点数が100以下と小さいので凸包は愚直に求めました。 x座標が一番小さい点は必ず凸包に含まれるのでそれを開始点とします。 残…

問題リンク The Number of Island 解法 島がいくつあるかを数える問題。 陸を見つけたらそこから隣接点へ深さ優先探索をかけます。訪れた陸は海にして再訪を防いでいます。 ソース

問題リンク Tic Tac Toe 解法 かなり愚直にだらだらと解きました。 横に揃っているか 縦に揃っているか 斜めに揃っているか を各個調べています。 ソース

問題リンク Trading 解法 取引先数が1000社以内なので、大きさ1001の配列t, t2を用意して（問題文に会社番号のとる値についての記載がありませんが番号は1000以下のようです）、それぞれ、会社iと取引した回数（今月分と先月分）をカウントします。 出力は会…

問題リンク Secret Number 解法 英数字ごちゃまぜの文字列から数字をピックアップして和を求める問題です。 先頭からサーチをかけて、数字を見つけたら、数字が続く限り10倍して足しこんでを繰り返します。 ソース

問題リンク Palindrome 解法 文字列Sが回文かどうかを判定する問題です。 回文ならひっくり返しても元のSと一致するはずなのでそれで判定します。 文字列の逆転はStringBuilder.reverse()が便利です。 ソース

問題リンク What is the Bottommost? 解法 下の段のi番目の数字は上の段のi番目とi+1番目の和の下1けた、なので配列でこれを実装します。 ソース

問題リンク Rank Checker 解法 チーム番号と正解数をメンバに持つクラスTを作りました。TはComparableインタフェースを実装して正解数の多い順にソートできるようにしてます。 順位付けですが、例えばチームA,B,C,Dがそれぞれ40,30,30,20の正解数のとき、Dは…

問題リンク Card Game 解法 場に出ていない残り7枚のうち手札に加えて和が20を超えないのは何通りあるかを数えれば勝ちです。 ソース

問題リンク Intersection of Rectangles 解法 かなり面倒な問題です。 長方形A, Bが 辺が交差する Aの中にBがある Bの中にAがある などなどの場合を逐一調べて解きました。 ソースコードはライブラリから不要な要素を削ってなかったりして大分長くなってます…

問題リンク Orthogonal 解法 ABベクトルとCDベクトルの内積で解きました。 AB・CD = |AB||CD|cosθ なので2ベクトルが直交していれば内積は0になります。 ソース

問題リンク The Number of Area 解法 ノートに直線を引いて分割してみます。すると、法則が見えてきます。 既に直線がn本あるとき、n+1本目の直線を適切に引くと新たに面はn+1個増えます。 なので dp[i] : 直線がi本あるときの面の数 dp[i] = dp[i-1] + i と…

問題リンク Goldbach's Conjecture 解法 素数見てからエラトステネス余裕でした。 組み合わせ数を答えるので(a,b)と(b,a)は区別されません。 ここは、a素数であるかを調べて解きました。 ソース

問題リンク Sequence 解法 書かれている数列の定義通りに計算するだけです。 ソース

問題リンク Sum of Nth decimal places 解法 a/bしたとき、小数第n位までに登場する数字の和を出す問題。 まぁやるだけです。アルゴリズムにこんがらがってきたら、除算の筆算を手で書くと整理できるかと思います。 ソース

問題リンク Sum of Prime Numbers 解法 素数ときたらエラトステネス。 ただ、どの大きさまで作ればいいか分からないので、一旦、10000個目の素数が何なのかを求めるプログラムを作りました。結果は104729です。 後は、大きさ104730の篩を作って、累積和を貯…

問題リンク Factorial II 解法 N! (N N!を素因数分解したときに10が何回出てくるか（２と５のペアの数）を求めると言いかえられます。 ２の数と５の数のうち小さい方が１０の登場回数になります。 登場回数は必ず５の方が小さいので、即ち５の登場回数がこの…

問題リンク Differential II 解法 数字を昇順、降順に並べ替えれば最小値と最大値が作れます。 並べ替えにArrays.sort()を使うと楽です。 ソース

問題リンク Apple and Peach 解法 s[i]〜s[i+4]の５文字が"apple", "peach"になっているかを調べ、一致したら置換します。 空白文字でsplitしてequals()で調べようとすると、Sample Inputにある"apple."に対応できません。 ソース

問題リンク Blood Groups 解法 A: 0 B: 1 AB:2 O: 3 として、配列でカウントしました。 ソース

問題リンク Class 解法 ?:演算子の羅列で解きました。 ソース

問題リンク Cup Game 解法 ボールが入っていればtrueというboolean配列を使いました ソース

問題リンク Differential 解法 最小値最大値を覚えて差をとるだけの問題です。 ソース

問題リンク Sum and Average 解法 平均を求めるだけの問題です。 小数第１位を四捨五入する必要があるのでprintf("%.0f")を使うといいと思います。 ソース

問題リンク Prime Number II 解法 素数と来たら自分はエラトステネスの篩を反射的に作ります。 N素数も判定したいので適当に篩の大きさを55000にしています。 後は、Nから２方向の素数を探しに行くだけです。 ソース

問題リンク Puzzle 解法 全探索します。各数字が何個残っているかを配列で管理します。 最初、２個ペアとする数字を決めます。残った１２個の数字で３ペアが４つ作れるかを全探索します。 ソース

問題リンク A Thief 解法 ナップサック問題です。DPで解きます。 dp[i][j]はi番目までのアイテムを使って重さj以下の中で得られる最大の価値 を表します。 漸化式は dp[i][j] = Max{ dp[i-1][j] : i番目のアイテムを採用しない dp[i-1][ j-w[i] ] + v[i] : i…

問題リンク Expression 解法 基本は数字を４つ並べ替えて、計算順序と演算子を全通り試行する方針で解きました。 まず、各演算が再帰の形で表せます。 演算結果を表すクラスEを用意しています。メンバは演算結果の整数値xと、演算を表す文字列eです。例えば…