2011-10-07から1日間の記事一覧
問題リンク Aizu Chicken 解法 会津地鶏を買う量の解をQとすると、Qを境に言いつけどおりの買い物ができるかどうかが分かれます。よってQについての2分探索を行います。Qが0として求まった場合は買い物失敗です。 ソース
問題リンク Goldbach's Conjecture II 解法 エラトステネスの篩を作ります。 あとは2素数であるかどうかを調べます。 ソース
問題リンク Tsuruga Castle 解法 やるだけ問題です。 ソース
問題リンク Black-and-White 解法 3*3で揃っているものを探すだけなのでやりやすい方法をどうぞ。 今回は、bを1、wを-1として置き換えて、各行、各列、各斜めに対して総和をとり、絶対値が3になっているところがあるかどうかで判定しました。 ソース
問題リンク Persistence 解法 解となる幅がWだとします。すると、W' ソース
問題リンク Stellar Performance of the Debunkey Family 解法 ストレートな最小全域木問題です。 UnionFind木を用いてクラスカル法によって最小全域木を求めます。 (UnionFindクラスはwakaba.wikiのものを利用させていただいています) ソース
問題リンク Mysterious Worm 解法 虫の長さは最大10。各部分が取りうるのは3色なので、虫の全状態数は3^10に収まります。 よって幅優先探索可能となります。 虫の隣り合った色が違う部分を見つけ、それらの色ではない最後の1色で塗り替えて状態遷移とします…
問題リンク TETORIS 解法 実装問題です。 ブロックを置くロジックと、行を消すロジックの2つをがんばって作ります。 行が揃っていたら、それより上の行全てを1段下にずらします。これを続けられるだけ続けます。 ソース
問題リンク What Color? 解法 "#xxxxxx"をsubstringし、Integer.parseInt()で16を渡すことで一気に0〜255に変換できます。 あとは色全てと比較して近い色を探します。 ソース
問題リンク A King in Hawaii 解法 BigIntegerにはn進数に直すメソッドがあるので一発です。 ソース
問題リンク Badminton 解法 サーブを打つ人は点を決めた人なので、文字列の2文字目以降に登場するAの個数がAの得点です。Bも同様です。 ゲームが終わる時、必ず2点差以上がついているので、得点集計が終わった後に得点が高い方が決定打を決めたとわかります。…
問題リンク Haunted House 解法 やるだけ問題です。 午前人数*200 + 午後人数*300 が収入です。 ソース
問題リンク Doctor's Research Rooms 解法 (部屋の番号を0〜n-1と考えています。) 幅優先探索+経路記憶の問題です。ここでいう経路は通った道筋だけでなく、スイッチのON, OFFのことも含みます。 部屋は高々15個なので、部屋の照明の状態と今いる部屋の対…
問題リンク Dice Puzzle 解法 全探索+枝刈りで解きました。 サイコロの状態数は24なので全状態数はざっと24^8だけあります。 サイコロを隣接して置くための条件が厳しいのでバサバサ枝刈りしてスピードアップさせます。 汚くて冗長なコードを書いてしまいま…
問題リンク Lunch 解法 全探索の方針でいきます。10! = 3*10^6くらいなので枝刈りできればまぁ大丈夫でしょう。 お弁当を積み重ねていくわけですが、上の段から考えていきます。 そうでないと、あるお弁当がつぶれないかどうかの判定が積み重ねの途中ででき…