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

Easy 問題概要 省略 解法 全探索。 あり得る組み合わせを全て試し、その結果をsetなどにつめていく。 最終的な答えは、setのsizeとなる。 コード class Cdgame { public: int rescount(vector <int> a, vector <int> b) { set<int> st; int sum1 = 0,sum2 = 0; int A = a.si</int></int></int>…

問題文, 制約 日本語なので省略 解法 構文解析＋全探索まず、入力で与えられる文字列から木を構築する. その木の内部節点にナンバリングする.後は、内部節点の個数分(多くても8個)だけ、'A'を0, 'O'を1, 'X'を2として 全通り(例えば、内部節点が3個なら、000…

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

Easy 問題文 M曲の歌がある. 歌は0~M-1でナンバリングされ、i番目の歌は、idol s[i]のみ歌うことができる. i番目の歌が歌われると観客の幸福度がh[i]増える.各idolは、多くて1曲しか歌うことができない. この条件の下、観客の幸福度を最大化せよ.入力は、s[i…

Easy 問題文 aが与えられる. a Xor b の計算結果の各桁の数字が全て4or7になり、かつ、a 複数ある場合はどれを出力しても良い. 解法 全探索aとbのXorはC++ならa^bで書ける. コード class LuckyXor { public: bool check(int x){ if(x == 0) return false; wh…

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>…

問題概要 3つ以下の数字がある。1stepに数字のうち1つを-9でき、1つを-3でき、1つを-1できる。計算結果が0以下になったものは0と見なす。 全ての数字を0にするためのステップ数を最小化せよ。 制約 3つの数字はそれぞれ[1,60]。 解法 bfsする。 (メモ化再帰…

問題概要 1~Nの番号付けされた家がある。道も1~Mの番号付けされている。それぞれの道は、家uと家vを距離lでつなぐ。 家1からスタートして同じ道を二度以上通らずに、家1以外の家を少なくとも1軒を経由して家1に戻るための最短経路を求める。ただし、そのよう…

Easy 問題概要 文字列s('a'~'z'で構成されている)のうちのちょうどk個の文字を任意の'a'~'z'に置き換えたとき、全ての文字が同じになるような文字列を返す。ただし、少なくとも1つは答えが存在し、複数答えがある場合は、そのうちの1つを返す。 制約 1 ≤ |s|…

acos(x)のxの範囲は、[-1,1]であり、 その範囲外の数値を入れると、nanとなる。

問題概要 '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[個数][和] := 作ることが可能かど…

問題概要 平面上のn個の円環から構成される鎖がある。最初と最後の円はそれぞれ、次の円、1つ前の円のみと交差し、他の各円は隣の2つの円のみと交差する。以下の2つの条件を満たす最短経路を求めよ。 経路は、最初の円の中心がスタートで、最後の円の中心が…

問題概要 少女が座標(0,0)のマスにいる。少女は隣接する4つのマスに移動できる。今、M個の隕石が落下する。各隕石は座標(X,Y)のマスに時刻Tのとき落下し、落下したマスとその隣接する4つの座標が通行できなくなる。この条件の下、少女が安全なマス(隕石の影…