2011-09-01から1ヶ月間の記事一覧
問題リンク Doctor's Strange Particles 解法 典型的なパズルの問題です。 1行目の10個のマスについて、1か0かを決めます。2^10パターンあります。 このとき2行目のマスについて1か0どちらにするかはすぐ決まります。 すぐ上の1行目のマスを見て、0だったな…
問題リンク Train 解法 基本的にはシーケンスの通りに探索していきます。 まず大きいサイズのchar[]を作っておきます。ここに列車を構築していきます。 最初は配列の真ん中にいることにします。同時に、列車の最後尾と最前列があるインデックスを覚えていき…
問題リンク Hide-and-Seek Supporting System 解法 平面幾何問題です。N個の円とm個の点の対が与えられ、各対に対して対を結ぶ線分がどれかの円周に触れるかどうかを判定しろという問題です。 まず線分Lについて円iとの距離をdとします(「線分」と点の距離で…
問題リンク Abacus 解法 各桁で表わしたい数字を配列a[]にしておきます。 "====="の上の部分についてはa[i]が5以上かどうかを調べればおkです。 面倒なのは下の部分です。 高さ5のどこか1か所のみにそろばんの珠がない空白があります。高さを上から0,1, ..…
問題リンク Pocket Pager Input 解法 まず変換表を作っておきます。 入力されたシーケンスの長さが奇数だったら確実に"NA"となります。 2文字ずつシーケンスを読み、変換表のキーに引っかからなかった場合も"NA"です。 最後まで読み取ることができたらメッ…
問題リンク Puzzle 解法 ナンバープレース、数独とか呼ばれるパズルの問題です。 9*9のboolean配列を用意し、(i, j)のマスがルールに違反しているかのマークを付けます。 各列、行、ブロックに対して1〜9の出現回数を数え、回数が2以上の数字があったらその…
問題リンク Day Count 解法 日付を表すクラスを作って、翌日を得るメソッドを実装しました。 あとは左端の日から右端の日まで何回メソッドを呼ぶかを数えるだけです。 でも、これは流石に素直すぎる気がします。1年以上差が開いていたら、その年の日数をカ…
問題リンク League Match Score Sheet 解法 勝ち点と入力順によるソートが必要なのでクラスを作りました。 PriorityQueueに突っ込んでpoll()してますね。 ソース
問題リンク Speed Skating Badge Test 解法 やるだけ問題です。 if(){}else if(){}・・・を続けるよりは配列を使った方がプログラムがすっきり書けると思います。 ソース
問題リンク Summer of Phyonkichi 解法 基本は幅優先探索です。ただiステップ目の移動先がi番目のスプリンクラーの効果範囲内に入っている時のみ移動できます。 n回この移動をし、生き残っていたらぴょん吉野郎は生き延びます。また、ぴょん吉はその場にとど…
問題リンク Seven Puzzle 解法 初期状態のパズルを受け取ってそこからゴールの状態まで幅優先探索をかけるのは大変です。 まずパズルの状態を1つの整数で管理することにしました。 0376 5421 という状態は3765421という整数に変換できます。この整数から移…
問題リンク Patisserie 解法 n個のケーキの並べ方はn!あるので全探索はできません。 そこで次の部分問題を考えることができます。 ケーキの部分集合に対して、その中のiというケーキを左端に、jというケーキを右端にしたときの全体の最小幅という問題です。…
問題リンク Property Distribution 解法 上下左右4方向に隣接している要素の塊を消去し、消去したあとのマップに再び同じような処理を施します。答えはこの処理を施した回数となります。 要素に#, *, @ 意外の文字を入れることを要素の消去としています。 …
問題リンク A reward for a Carpenter 解法 大工の褒美は 受け取ったお金 - 柱の代金 - 交通費 なので交通費を最小にすればいいです。 典型的な最短経路問題です。 ただ、道に向きがあり、コストが異なるので行きと帰りで交通費の最小値が異なる場合がありま…
問題リンク Rectangular Searching 解法 ある'.'のマス(i, j)に注目します。このマスを左上に持つ長方形をO(H)で求めるために下準備をしておきます。そのマスを含めて、右側に何個の'.'マスが連続しているかという表を作ります。例えば、 ..* .*. ... という…