問題 Space-Time Sugoroku Road | Aizu Online Judge 解法 幅優先探索。各マスに到達するのに必要な最小回数を更新した時だけキューに入れるようにすれば、ループを避けることが出来る。 コード import java.util.ArrayDeque; import java.util.Arrays; impo…

問題 And Then. How Many Are There? | Aizu Online Judge 解法 bitDP。円の個数は最大で24個しかないので、遷移の状態は最大16777216通りしかない。bitで管理するとどの円の上にどの円が載ってるかも楽に管理できる。 コード import java.io.IOException; p…

問題 Water Pipe Construction | Aizu Online Judge 解法 ワーシャルフロイト法でそれぞれの基地間のコストを計算する。各基地について、水源からのコストと目的地までのコストを算出し、最も小さくなる時を出力すれば良い。 コード import java.util.Scanne…

問題 Shopping | Aizu Online JudgeN個の店が等間隔に一直線に並んでいて、店に行く前に店に行かなければならないという制限がある時、最短で行くにはどのくらい歩けば良いか。 解法 1回しか通らない道と3回通る道があるので、それを個々の店の間について考…

問題 Stylish | Aizu Online JudgeStylishという言語では、丸括弧()、カールしてる括弧{}、四角い括弧[]についてそれぞれインデント数が決まっている。これらをそれぞれR, C, Sとする。インデントはドットで表される。最初にStylishマスターが書いたコードを…

問題 Erratic Sleep Habits | Aizu Online Judge睡眠のサイクル（12時に寝てt時間寝る）と、D日目はM時に起きないといけない、という情報が与えられるので、睡眠サイクルをリセットする最小回数を求める。 解法 動的計画法。dp[i日目に][サイクルjがきてる]…

問題 One-Dimensional Cellular Automaton | Aizu Online Judgeとの漸化式が与えられるので、からを求める。 解法 上のような行列Dを考える。問題の操作は下の式のようになるので、最初の状態に行列DをT回かければ良い。よってを考える。などの計算はまとも…

問題 Balloon Collecting | Aizu Online Judge 落ちてくる風船をキャッチするゲーム。キャッチャーは風船を積むごとに動きが遅くなるほか、風船は最大3個までしか積めない。積んでいる風船はHouseに戻ることで0にすることが出来る。最小の移動で全ての風船が…

問題 Repeated Substitution with Sed | Aizu Online Judge n個のαとbの組が与えられる。1回の操作で文字列γの中のαを全てβに置き換えることができる。αとβを上手く使いながら、γをδに変換するのに必要な最小の操作回数を考える。 解法 幅優先探索。βはαより…

問題 Princess in Danger | Aizu Online Judge 解法 まずは制限時間や冷凍庫位置を考えずに、ワーシャルフロイト法で任意の2点間の最小必要時間を出しておく。すると任意の2冷凍庫間の最小必要時間も出る。この後は冷凍庫間の移動だけを考えるので、それ以外…

問題 Building a Space Station | Aizu Online Judge 3次元空間にn個の球形の宇宙ステーションがあるので、それらを行き来する通路を作る際の、通路の最小合計距離を求める。 解法 2つの宇宙ステーション間の距離を求め、最小全域木探索する。 コード import…

問題 X-Ray Screening System | Aizu Online Judge 解法 それぞれの物体の四点を取って、その中に空白が入ってたらアウト。空白のある物体が存在しない時は上下関係を見て、矛盾があればアウト。 本当は、必ず1つは長方形が存在するはずなので、それを上手く…

問題 Curling 2.0 | Aizu Online Judge スタートのマスとゴールのマスが決まっている平面上で、駒をゴールまで運ぶ。駒は滑って移動するしかなく、障害物にぶつかるまで止まれない。ぶつかられた障害物は消滅する。フィールド外に出た場合は失敗となる時、最…

問題 Whist | Aizu Online Judge 解法 Google コード import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { char T = sc.next().charAt(0); if (T == '#') { sc.c…

問題 Butterfly | Aizu Online Judge あれな感じの女の子ができるだけ多くの男とデートしたいのだが全員とする時間がない時、イケメンとだけデートできるように最適なデートプランを考える。ふぁっく。 解法 DFS コード import java.util.ArrayList; import …

問題 Shredding Company | Aizu Online Judge 解法 DFS コード import java.util.Scanner; public class Main { private static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { N = sc.nextInt(); S…

問題 Leaky Cryptography | Aizu Online Judge 解法 Kの後ろからi桁目を0にした時に、下i桁の答えが条件に合うならば、Kの後ろからi桁目は0であり、合わなければ1である。 コード import java.util.Scanner; public class Main { public static void main(St…

問題 Carpenters' Language | Aizu Online Judge 解法 "("の数と")"の数が一緒ならYes。マジなんなんだこの問題。 解答 import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOExcep…

問題 Ginkgo Numbers | Aizu Online Judge 2つの整数mとnが与えられるので、m2+n2 の約数となる x2+y2 を満たす整数xとyが存在するかどうかを調べる。 解法 全探索。素因数分解。 コード import java.io.IOException; import java.util.Scanner; public clas…

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

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

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

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

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

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

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

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

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