問題概要、制約 省略。 Cleaning Robot | Aizu Online Judge 解法 確率DPをする。dp[i][j] := バッテリーをi使って位置jにいるときの確率。 位置は二次元座標だが、(x, y)をy * 3 + xのようにすると次元を1つ落とすことができる。 コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

問題概要 長さL-1の平均台の上にN羽のうさぎがいる。i番目のうさぎの初期位置はxiであり、0 ≤ xi ≤ xi+1 ≤ L-1を満たす。それぞれのうさぎは、1回ジャンプすると右にaiだけ移動できる。任意の回数ジャンプすることできるが、別のうさぎを飛び越えたり、L以上…

問題概要 文字列Sが与えられるので、それが "Cat" か "Rabbit" かを判定せよ。ただし、文字列Sが "Cat"とは、 CAT := ””(empty string) | ’m’+CAT+’e’+CAT+’w’ を満たすことである。(+は連結を意味する)文字列Sが"Cat"でなければ、"Rabbit"である。 制約 1 ≤…

Easy 問題文 N × Nのボードにそれぞれ英小文字が書いてある. ある英小文字を好きな英小文字に書き換えることができる.ボードをチェック模様(ある文字を見たとき、上下左右に隣接する文字が全て異なり、ボードを2つの文字で表現することができる) にするため…

Easy 問題文 省略 解法 シミュレーション boolの関数visitedを利用し、既に訪れたところに再び来た場合は、"Lose", -1に到達した場合は、"Win"とする. コード class DevuAndGame { public: string canWin(vector <int> nextLevel) { int now = 0; vector<bool> visited(</bool></int>…

Easy 問題文 省略 解法 全探索 コード class PointDistance { public: int dist(int x1,int y1,int x2,int y2){ return pow(x1-x2,2.)+pow(y1-y2,2.); } vector <int> findPoint(int x1, int y1, int x2, int y2) { for(int x3 = -100 ; x3 <= 100 ; x3++){ for(i</int>…

問題概要 'A','B','?'で構成される文字列がある。全ての'?'を'A'または'B'で置き換えたとき、最終的な得点を最小化せよ。得点は、連続する文字列で"AA"または"BB"となるものが1pointである。ただし、overlapも考えるので、"BBB"は2pointとなる。 制約 1 ≤ |S…

問題概要 N個の数列がある。これを、N/2個に分割し、かつ、それらの数列の和を等しくすることは可能か。可能ならば、"Possible"、不可能ならば、"Impossible"と出力せよ。 制約 1 ≤ N ≤ 50 1 ≤ value ≤ 50 解法 dpする。 dp[個数][和] := 作ることが可能かど…

問題概要 Claireという女性がいる。彼女がN人の男性のうちの何人かとデートをするプランを立てることを考える。N人の男性にはそれぞれM個のデートをする時間帯(SからE)とその男性とデートしたときの満足度Lが与えられる。彼女は各男性に対して、全ての時間帯…

問題概要 横x×縦yのマップが与えられ、マップは以下のもので構成される。 S : スタート位置 G : ゴール位置 1 : 火属性のモンスター 2 : 氷属性のモンスター 3 : 木属性のモンスター 4 : 土属性のモンスター 5 : 水属性のモンスター モンスターを手に入れる…

問題概要 T日の睡眠サイクルがある。これはi日目に深夜12時からti時間睡眠を取ることを意味する。N個の組が与えられ、各組ではDi日目にM時から仕事が始まることを意味する。 睡眠サイクルは、1日に1つ進み、T+1日目には1日目に戻る。また、カフェインを摂取…

※ 未提出なので結果は不明。-> AC(2015/12/31) 問題概要 A,B,Cの3つの会社がある。それぞれの会社にはN人の社員がいて、各社員iにはスループットtiが与えられる。以下の三つの条件のより上の条件を満たすように出力せよ。 会社の全ての社員を使わなければな…

問題概要 主婦の琴子が家を出てn個のスーパー内いくつかをまわり、買い物リストにあるq個の品物を全て買い、家に戻ってくるための最小コストと最短距離を出力せよ。各スーパーにはki個の品物の名前と価格が与えられる。 制約 n ≤ 10 q ≤ 15 解法 今いるノー…

問題概要 n個の文字列が与えられる。これらを連結させてできる最小の文字列の長さを出力せよ。連結とは、例えば、ABCとBCDを連結するならばABCDとなる。なお、ある文字列が他の文字列の中に完全に含まれていても良い。 制約 n ≤ 14 解法 任意の二つの文字列…

問題概要 洞穴がいくつか存在する。そのうち中央の洞穴の番号を1とし、そこから渦巻き状にm個の番号がつけられている。ある洞穴からは左下、下、右下のいずれかに移動できる。また、洞穴のうちその番号が素数のものを素数洞穴という。スタート地点の番号をn…

問題概要 N個の変数があり、それぞれの変数は[si,fi]の期間でレジスタに割り当てられる。[si,fi]∩[sj,fj]=Φならば同じレジスタを使うことができる。この条件の下で使用するレジスタの個数を最小化せよ。 制約 1 ≤ N ≤ 10000 1 ≤ si ≤ 10000 2 ≤ fi ≤ 30000 …

問題概要 N個のマスがあり、各マスにはL個の一回休みのマスと、B個のふりだしに戻るマスがある。 1〜6までの目のサイコロを降り出た目の数だけ進む。 このときTターン以内にゴールに到達するための確率を求めよ。 ただし、ゴールを超えるような目が出た場合…

問題概要 パネルの初期状態と最終状態が与えられるので以下の条件の下で最終状態にするための最小コストを求めよ。 パネルは'W'と'B'で構成されており、'W'が白いパネル、'B'が黒いパネルを表す。 パネルを交換するmachineがあり、このmachineは任意の場所を…