問題リンク : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2437&lang=jp問題概要 : 日本語なので略解法： DP + 半分全列挙で解いたまず、i文字目(1 与えられる文法に含まれる非終端記号間の関係をグラフにするとDAGなので、これは再帰などで…

問題概要 :長さ n (1 Aの各要素A[i]は 0 以上 50 以下である この数列に対して以下の処理を行う1. 変数 X を用意し、 X に 0 を代入する 2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する : X = X + ( X xor A[i] ) これを…

問題概要 : n人にm回質問をする. 人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている. 人iの質問jに対する回答は英大文字('A'~'Z')として表現される. 各人の各質問への回答が入力として与えられる. 全ての人を区別するためにしなければならな…

問題概要 : n人の生徒からなるクラスがある. 各生徒には強さがあり、それらは0以上255以下の整数として表される.n人の生徒を3つのグループに分ける. ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない. グループの強さ…

問題概要 : n個のノードが存在し、それらは0からn-1まで番号が割り振られているノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つまた、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ各辺は無向辺であるこのように…

問題リンク : J: ボール - Typical DP Contest | AtCoder問題概要：略解法： 期待値苦手すぎて謎だったので以下の解説記事を参考にしました Typical DP Contest J - ボール - Lilliput StepsビットDP (orメモ化再帰) まだ倒れていないものがある場所に対応す…

問題リンク : I: イウィ - Typical DP Contest | AtCoder問題概要 : 最大iwi数解法 : メモ化再帰 => WA 区間DP => TLE TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いたdp[L][R] := 閉区間[L,R]までで得られるiwiの最大値 区…

問題リンク : H: ナップザック - Typical DP Contest | AtCoder問題概要 : 日本語なので略解法 : まずナップザックに入れるものを色の番号が小さい順にソートする （同じ色のものは連続した場所に存在するようにしたいだけ） 通常のナップザックに加えて、今…

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder 問題概要 : 文字列sと自然数Kが与えられる sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ解法 : 他の人のブログを参考に解いたので、 コードにある通りコード: #include<bits/stdc++.h> #d</bits/stdc++.h>…

問題リンク：F: 準急 - Typical DP Contest | AtCoder 解法： dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1] 初期値は dp[0] = 1, dp[1] = 0 また、dp[N] = 0 dp[1]=dp[N]=0は、必ずその駅にとまることを意味する dp[i]は max(0,i-K)…

問題リンク : E: 数 - Typical DP Contest | AtCoder解法 : 桁DP dp[桁][余り][現在の桁までがNのこの桁までと一致しているか] := 総数コード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

問題リンク : Invest Master | Aizu Online Judge問題概要： n日間の株価の情報が与えられる 初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ 株の売買に手数料はかからないものとする また、最終日の所持金の最大値は高々１０＾５で…

問題リンク : D: サイコロ - Typical DP Contest | AtCoder解法 : Dを素因数分解したとき、その素因数に２、３、５以外のものが存在するのであれば求める確率は０となる （サイコロの目が１から６までしかないので、例えば７は２、３、５の積ではどうやって…

問題リンク : C: トーナメント - Typical DP Contest | AtCoder解法 : DP全然思い浮かばなかったので愚直に計算した 他の人のコード見て勉強しますコード: #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

問題リンク : B: ゲーム - Typical DP Contest | AtCoder解法 : dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の（すぬけのターン）最大or（すめけのターン）最小値両方の山が０を初期状態とし、１手1手戻りながら計算するコード : #include<bits/stdc++.h> #defin</bits/stdc++.h>…

問題リンク : A: コンテスト - Typical DP Contest | AtCoder解法 : bool dp[i] := i が作れるならtrue, otherwise falseコード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int n; bool dp[10001]; int main() { dp[0] = true; cin >> n; rep(i,n) { int tmp; cin >>…</n;i++)></bits/stdc++.h>

問題概要 : 4と7から構成される正の整数をLucky Numberと呼ぶ [0-9]と?から構成される文字列が与えられる ?には何の数字が入っても良いので、2つのLucky Numberの和がその文字列と等しくなるようなもののうち最小の和を求めよ解法 : 動的計画法 dp[桁][値][…

問題リンク : Young, Poor and Busy | Aizu Online Judge問題概要 : けんさんは函館に住んでおり、けいこさんは東京に住んでいる けんさんとけいこさんは電車を使って合う予定を立てている 電車の時刻表の情報を持っており、その情報は電車が出発する駅の名…

問題リンク : Reading Brackets in English | Aizu Online Judge問題概要 : S-expression は次のように定義される 1. a list of A は (A) に変換され、 2. a list of A and B は (A B) に変換され、 3. a list of A, B, C, ...,Y and Z は (A B C ... Z) に…

問題リンク : https://uva.onlinejudge.org/external/124/p12484.pdf問題概要 : 整数の書かれたN枚のカードが一直線上に並んでいる AさんとBさんは交互にカードを取っていく ただし、カードを取る際は両端のうちどちらかでないといけない 最初にAさんがカー…

問題リンク : Social Monsters | Aizu Online Judge問題概要 : N匹のモンスターがいる その中からK匹を選んでチームを作る 任意の2匹のモンスター間には仲良し度があり 仲良し度が0の場合、それらのモンスターを一緒にチームに入れることはできない それ以外…

問題リンク : Manhattan Wiring | Aizu Online Judge問題概要 : h * w の表に'2'と'3'がそれぞれ２つずつ存在する その他は'0'か'1'である '2'と'2'を、'3'と'3'を線で繋ぎたい ただし、それらの線同士が交差してはいけない 線の長さの和が最小となるように…

[備忘録] 問題概要 : 備忘録なので略解法 : DP { 0, 0, 3, 3, 0, 0 } という数列が与えられたとする 0..1...2...3...4...5...6 0 0 3 3 0 0 みたいな感じで間に板を置き、左から昇順に番号を割り振る dp[i] := 0番の板からi番の板までで条件を満たす組み合わ…

問題リンク : Happy End Problem | Aizu Online Judge問題概要 : 略解法 : DP 答えるものが多角形の頂点番号なので経路復元もしなければならない メモ化再帰でも間に合うと思ったが幻想だった 各点を出力に合わせてソートする 下にあるものほど前にくる 同じ…

問題リンク : Problem - 498B - Codeforces問題概要 : ある人がn曲の歌を決められた順番で歌う 自分はその歌の名前を思い出し次第その人に対して歌の名前を伝える そうするとその人はその歌をやめて次の歌を歌う 自分は１秒単位でその歌の名前を確率pで思い…

問題リンク : http://uva.onlinejudge.org/external/128/12856.pdf問題概要 : 長さ10^6以下の文字列が与えられる 文字列の部分文字列のうち、数字のみを含み、それを10進数の数として見たときにその値が3の倍数であるようなものを数えよ リーディング０も許…

問題リンク : http://uva.onlinejudge.org/external/105/10593.pdf問題概要 : n * n の char のシートが与えられる それに含まれる要素は 'x' か '.' のいずれか この中に含まれる大きさが１より大きい正方形とダイアモンドの数を数えよ解法 : 動的計画法 正…

問題リンク : Castle Wall | Aizu Online Judge問題概要 : 単純多角形が与えられる 自分はこの多角形の2頂点を選んで新たに辺を付け加えることができる これを0回以上行うことができるのだが、その際に追加した辺の長さの総和がr以下でなければならない この…

問題リンク : So Sleepy | Aizu Online Judge問題概要 : S個の駅とT個の電車がある 各電車は決められた時刻に決められた駅を出発し、決められた時刻に次の駅に到着する 自分が最初いる駅とその時刻、最終的に行かなければならないランデヴーである駅と集合時…

問題リンク : True Liars | Aizu Online Judge問題概要 : 自分今、伝説の島にいる その島には正直者と嘘つきがいて、自分はその正直者に用事がある 以前の調査で正直者はp1人、嘘つきはp2人いることが分かっている 今、各人に１から昇順に(p1+p2)まで番号を…