AOJ Volume1
問題リンク Taro's Obsession 解法 容疑者を頂点にした有向グラフで考え、Y->Xという証言を辺にします。頂点の出次数が0の頂点はもう出力してしまってよく、その頂点をグラフから取り除きます。これを繰り返せばOKです。 ソース
問題リンク Beaker 解法 DFS+貪欲で解けました。 一番大きいビーカーの水を小さいビーカーへ振り分けるやり方は非常に多くなるのでたぶん時間が厳しいです。ここで逆転の発想、全てのビーカーに水を注ぐことができた時、最後に水が入っているビーカーはどこ…
問題リンク Jigsaw Puzzle 解法 DFS+枝刈りで解きました。ただ何も工夫をしないと余裕でTLEを貰います。 パズルとピースは全て1行を1つの整数として表すことにします。パズルは穴があいている部分が1、ピースは穴が無い部分が1になるようにします。こうする…
問題リンク Byakko Delivery Company 解法 交差点とその進入方向をノードにしたダイクストラ法が基本方針です。辺のコストは移動時間です。 ただし、(交差点、進入方向)だけではこの問題は解けないです。なぜなら、その交差点に最短で辿りつく場合が常に解の…
問題リンク Distance Between Two Cities 解法 バリバリ数学問題です。 まず、2つの都市間の最短距離は、円の中心と2つの都市を通るようにスパッと球を切断したときの円弧の長さとなります。 切断面の半径Rは球の半径と同じなので、2つの都市それぞれの座標(…
問題リンク Lupin The 4th 解法 経路復元+メモ化再帰で解きました。 dp[蔵を訪れた状態][現在いる蔵]に、その状態から全ての蔵を回るまでにかかる最短時間を格納しておきます。 さらに、next[i][j][2]に、状態 i 現在地 j のとき、次にどの状態に遷移すれば…
問題リンク Chairs Where Demanding People Sit 解法 シミュレート問題です。 椅子の状態を管理しておき、A〜Dの人に対応した座らせ方を実装します。 ソース
問題リンク Trouble in Artist Shinagawa's Artifact 解法 2つのサイコロが同じものであるかをチェックできるかがカギです。 1つのサイコロは転がしたりすることで24種類の状態を持ちます。 あとは頑張って調べます。 ソース
問題リンク Greatest Common Divisor: Euclidean Algorithm 解法 ユークリッドの互除法をやるだけです。 ソース
問題リンク Baseball Championship 解法 チームについて勝ち数、負け数を数えてソートするだけです。 ソース
問題リンク What is the Most Popular Shop in Tokaichi? 解法 売上の大きいところを記憶するだけです。 ソース
問題リンク Deven-Eleven 解法 AOJの本文中に肝心の図が無いので本家の問題文を参照するといいでしょう PCK2008本選。 6角形座標なので図を見て、移動ベクトルを作ります。ただ注意すべきはy座標が偶数か奇数かで移動ベクトルは変わるということです。移動の…
問題リンク Tsuruga Parking 解法 重いシミュレート問題です。定義を読んで根気強く実装するしかないと思います。 駐車場の状態を配列で作っておき、そこに車があと何分停車しているかを入れておきます。0は空車を表すことにします。 これを使って1分毎にシ…
問題リンク Baby Tree 解法 DPです。 dp[i][j]: i日目に肥料jを与えたときの最大成長度 という表を作ることができます。 初日は何を与えても成長度1なのでdp[0][i]は全て1です。 次の日以降は直前の日の状態から算出できます。 dp[i][j]を埋めたかったら、dp…
問題リンク Eleven Puzzle 解法 素直に20ステップまで幅優先探索を行うと状態数が多すぎて死んでしまいます。 なので両側探索を使いました。 ゴールの状態から20の半分の10ステップ以内で辿りつける状態を予め調べておきます。これをmとします。 そして、与…
問題リンク Convenient Location 解法 ある頂点から、自分以外の全ての頂点までの各々の最短経路長の総和が最小となる頂点番号を答える問題です。 ある頂点から別の頂点までの最短路が欲しいので全点間最短経路を求めるワーシャル・フロイド法を使います。 …
問題リンク Search 解法 2分探索における目的の値との比較が何回行われるかを数える問題です。 アルゴリズムは問題に乗っている通りです。 自分は比較を行うという部分をメソッド化しています。 回数を数えるコードを散在させないためです。が、この問題は単…
問題リンク Stoning Fortune 解法 幾何問題です。 3本の線分に0, 1, 2と番号付けしたとして、0と1, 1と2, 2と0の線分の交点を求めます。 交点が存在しなかったら三角形は作れません。 あとは3つの交点でできる三角形の面積を求めて大きさを見るだけです。線…
問題リンク 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 が収入です。 ソース
