問題リンク 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です。例えば…

問題リンク Affine Cipher 解法 置換式の中にあるαとβが分からないと置換のしようがないのでこちらから求めます。[0,26)を与えて[0,26)の値域に全単斜するようなαとβの対を探します。とりあえず適当に、1 あとは、発見したαβの対を使って置換してみて、"that…

問題リンク Roman Figure 解法 ローマ数字を１０進数に変換する仕組みを作ると楽になると思います。 あとはルール通り、右隣にくるローマ数字が大きいか小さいかで場合分けして加算していきます。 ソース

問題リンク Poker Hand 解法 まぁ、やるだけの問題です。 ストレートの判定に気をつけるくらいでしょうか。 ソース

問題リンク A Figure on Surface 解法 超まわりくどい方法で解いていました。 ピースを１つの整数値で表して解こうとしたみたいです。 s = t = 0とします。 8*8マップを見て行って1になっている箇所をみつけたらフラグをonにします。 フラグがonになったら１…

問題リンク Is it Convex? 解法 四角形が凸かどうかを判定する問題です。 辺を考えてそれ以外の２点が全部左にあるか、もしくは全部右にあるかを調べ、これがどの辺についても成り立ったらそれは凸だと判定しました。 これ以外にも、内角がどれも１８０度以…

問題リンク Railway Lines 解法 電車がすれ違うということは、２つの電車の走行距離の和が路線全体の長さ以上になると同じ事です。 左から右へ走る電車を１駅分進めます。進んだ距離を速さで割れば走行時間がでるので、その時間分電車２を動かします。動いた…

問題リンク Ball 解法 全探索で解きました。ボールを右に流す、左に流すを全部試しても2^10程度なので余裕です。 ソース

問題リンク Plastic Board 解法 辺a, bと斜辺cの長さが与えられて、長方形とひし形の個数を数える問題。 長方形ならa^2+b^2=c^2が成り立ち、ひし形ならa=bが成り立ちます。 ソース

問題リンク Weight 解法 品物の重さXを2進数に変換した時に1になっている桁の重みの重りを採用します。 ビット演算子を使うちょうどいい練習問題だと思います。 ソース