AOJ

AOJ 2243: ダンレボのあれ

問題 Step Step Evolution | Aizu Online Judge 上の図の一番右のように右足と左足が交差しないようにパネルを踏む時、同じ足で連続して踏む回数を最小にするにはどうしたら良いか。 解法 DP。例えば、i番目のパネルがi-1番目のパネルより右にある時、i番目…

AOJ 1316: ドーナツ

問題 The Sorcerer's Donut | Aizu Online Judge 上のようにドーナツ状になっている文字表の中に2回出てくるフレーズを探す。2つ以上ある場合は最も長いものを返す。同じ長さなら辞書順で前にあるものを返す。 解法 例にあるとおり、 ABCD EFGH IJKL のFから…

AOJ 1277: ひとりすごろく

問題 Minimal Backgammon | Aizu Online Judge ひとりですごろくをする。N+1マスの直線のすごろくがあり、最初はスタート地点0に駒があり、ゴール地点はNである。プレーヤーはサイコロを振って出た目の数だけ駒を進める。ゴールするときはちょうどNに止まる…

AOJ 1336: 最後に出てくるアリをシミュレーションする

問題 The Last Ant | Aizu Online Judge N引きのアリが直線の巣穴の中を動いている。それぞれの位置と向きが与えられ、一定の速さでその方向に動く。2引きのアリが出会う時、巣穴の広いところで出会えればすれ違うだけだが、狭いところで出会うとぶつかって…

AOJ 2386: Sightseeing Tour

問題 Sightseeing Tour | Aizu Online Judge N個の頂点があり、任意の2点iとjを結ぶ辺のコストがi→jとj→iで別々に定められているので、全ての頂点の任意の2点を結ぶ最小コストの有向グラフを作る。ついでに、一筆書きの経路も含んでいる必要がある。 解法 任…

AOJ 1345: Bit String Reordering 文字列の並べ替え

問題 Bit String Reordering | Aizu Online Judge というデータが与えられる。は0または1で、は整数である。を並び替えて、「だけ同じ文字列が並んだ後、だけ同じ文字列が並び……」という文字列を作り、その際に入れ替えた回数の最小値を返す。入れ替えは隣接…

AOJ 2583: JAG-channel テキスト整形

問題 JAG-channel | Aizu Online Judge hoge .fuga ..foobar ..jagjag ...zigzag .piyo というテキストを読み込んで、 hoge +fuga |+foobar |+jagjag | +zigzag +piyo というツリー形式に書き換える。 解法 各行について、読み込んでからはひとまず英文字列…

AOJ 2600: Koto Distance

問題: Koto Distance | Aizu Online Judge 街全体が無線LANルータによって定められたKoto距離以内に収まっているかを考える。 解法: 上の図のように、(x,y)からwのKoto距離以内の範囲というのは、x-w列目からx+w列目までと、y-w行目からy+w行目までである。…

AOJ 2232: ぷよぷよ再び

問題 Ennichi | Aizu Online Judge ぷよぷよ(Chain Disappearance Puzzle | Aizu Online Judge)と似ている感じがする落ち物系ゲームで、勝てるかどうか判断する。縦または横にn個以上並んでいたら消えるフィールドで、1回だけ横に隣り合う状態同士を入れ替…

AOJ 1286: Expected Allowance 深さ優先探索で期待値を計算する

問題 Expected Allowance | Aizu Online Judge サイコロの数n、サイコロ1つあたりの面の数m、削減量kが与えられる。サイコロを同時に振った時の合計値から削減量kを引いただけ金がもらえるが、その値が1未満の場合は1だけもらえる。この時の期待値を計算する…

AOJ 2311: Dessert Witch

問題: Dessert Witch | Aizu Online Judge すごく頭の悪いAIにオセロをやらせる。本当にそれだけ。 解答コード: 鬼のように汚い感じがする。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = ne…

AOJ 1295: Cubist Artwork

問題: Cubist Artwork | Aizu Online Judge ブロックを積み上げて作った立体について、上の図のように横から見た図と正面から見た図が与えられるので、それらを満たす立体を作るのに必要な最小のブロックの数を答える。 解法: 上の例では、下の図の赤字のよ…

AOJ 1126: The Secret Number

問題: The Secret Number | Aizu Online Judge 上のような図で、あるマスからスタートして、右か下にしか動けない上に、数字のマスの上しか動けないとしたときに、通った数字を順番に並べて作れる数字で一番大きい数字を答えろ、という問題。(ちなみに上の…

AOJ 2015: スクウェア・ルート

問題: Square Route | Aizu Online Judge 解法: 縦と横それぞれについて、作りうる長さとその数を出しておく。作りうる長さは、w1, w1+w2, w1+w2+w3 ... のように連続した辺を足した組み合わせになる。辺の数が1500以下、辺の長さが1000以下なので、辺の種類…

AOJ 2254: Fastest Route

問題: Fastest Route | Aizu Online Judge 解法: ステージが最大で16しかないので、ある時点でのクリア状況は最大で216通りしかない。 各状態についてDPで解いてやれば良い。bitDPと呼ばれているらしい。 解答コード: import java.io.IOException; import ja…