読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

動的計画法

SRM 709 Div1 easy : Xscoregame

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

SRM 694 Div1 medium : DistinguishableSetDiv1

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

SRM 694 Div1 easy : TrySail

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

SRM Div1 easy : BiconnectedDiv1

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

Typical DP Contest J : ボール

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

Typical DP Contest I : イウィ

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

Typical DP Contest H : ナップザック

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

Typical DP Contest G : 辞書順

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

Typical DP Contest F : 準急

問題リンク: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)…

Typical DP Contest E : 数

問題リンク : 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>

AOJ 2607 : Invest Master

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

Typical DP Contest D : サイコロ

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

Typical DP Contest C - トーナメント

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

Typical DP Contest B - ゲーム

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

Typical DP Contest A - コンテスト

問題リンク : 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>

SRM 655 Div1 easy : LuckySum

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

AOJ 1229 : Young, Poor and Busy

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

AOJ 2067 : Reading Brackets in English

問題リンク : 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) に…

UVa 12484 : Cards

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

AOJ 2605 : Social Monsters

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

AOJ 1270 : Manhattan Wiring

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

SRM 653 Div1 250 : CountryGroupHard

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

AOJ 0284 : Happy End Problem

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

Codeforces 498B : Name That Tune

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

UVa 12856 : Counting substhreengs

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

UVa 10593 : Kites

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

AOJ 2121 : Castle Wall

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

AOJ 2042 : So Sleepy

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

AOJ 1238 : True Liars

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

UVa 12294 : RPG battles

問題リンク : http://uva.onlinejudge.org/external/122/12294.html問題概要 : ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 ) 各ステージは p1, p2…

UVa 12295 : Optimal Symmetric Paths

問題リンク : http://uva.onlinejudge.org/external/122/12295.html問題概要 : n * n のセルがあり、セルの中には1以上9以下の数字がかかれている 左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小と…

UVa 10328 : Coin Toss

UVa演習 2014/7/14 (月) 問3問題リンク : http://uva.onlinejudge.org/external/103/10328.html問題概要: n回コインをなげたとき、2^nだけコインの状態がある そのうち連続でk回以上表がでているようなものはいくつあるか?解法: 動的計画法 dp[何桁までみ…

UVa 1220 : 3794 - Party at Hali-Bula

UVa演習 2014/6/17 (木) 問1問題リンク : http://uva.onlinejudge.org/external/12/1220.html問題概要: とある会社の社員達がパーリィを開くことにした Big Bossと呼ばれる社員以外はちょうど1人のボスをもつ(つまり、ツリー状のグラフになる) パーリィに…

UVa 607 : Scheduling Lectures

UVa演習 2014/6/17 (火) 問1問題リンク : Scheduling Lectures問題概要: n個のジョブがあり、それぞれ処理にt[i]秒だけ時間がかかる ジョブは0から順番に番号付けられていて、0から順に処理されていかなければならない 1つのプロセッサーで処理できるジョ…

UVa 10690 : Expression Again

UVa演習 : 2014/6/10 (火) 問8問題リンク : http://uva.onlinejudge.org/external/106/10690.html問題概要: N+M個の整数(-50以上50以下)が与えられる (x1+x2+...+xN)*(y1+y2+...+yM)の最大値と最小値を求めよ解法: 動的計画法 dp[i個の整数をつかった][そ…

UVa 10069 : Distinct Subsequences

UVa演習 : 2014/6/10 (火) 問7問題リンク : http://uva.onlinejudge.org/external/100/10069.html問題概要: 2つの文字列X,Zがあたえられる X中に部分列としていくつZが存在するか?数えよ解法: 動的計画法 dp[Z[0:i]][X[0:j]] := 総和 ただし答えは10^100…

UVa 12324 : Philip J. Fry Problem

UVa演習 2014/6/10 (火) 問6問題リンク : http://uva.onlinejudge.org/external/123/12324.html問題概要: スペースシップで旅をする 旅はn個のフェーズに分かれている 各フェーズはt[i]秒で終わる 各フェーズでb[i]個のスペースシップ加速素材を手に入れる…

UVa 11088 : End up with More Teams

UVa演習 2014/6/10 (火) 問3問題リンク:http://uva.onlinejudge.org/external/110/11088.html問題概要: n人の人がいて、それぞれが30以下のパワーをもっている その中から3人チームを何組か作りたい チーム全体のパワーは20以上でなければならない 最…

UVa 10898 : D: Combo Deal

UVa演習 2014/6/10 (火) 問2問題リンク:http://uva.onlinejudge.org/external/108/10898.html問題概要: I種類の食べ物があり、それぞれの値段が与えられる C種類のセットがあり、その値段も同様に与えられる クエリーとして、I種類の食べ物をそれぞれ何個…

UVa 11611 : Colored Tiles

問題リンク:http://uva.onlinejudge.org/external/116/11611.html問題概要: H*Wのマスに図にあるようなピースを置いていく マスは3種類あり、 空のマスにはピースを置ける 壊れているマスにはピースを置けない 色の指定があるマスにはその色のピースしかお…

AOJ : 2449

問題リンク:Connect | Aizu Online Judge問題概要: 略解法: 1行覚えるタイプの動的計画法 dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値 としてDPする bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする 2重…

AOJ 2285 : Anipero

問題リンク:Anipero | Aizu Online Judge問題概要: 略解法: 動的計画法 pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度 pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最…

AOJ 2090 : Repeated Subsequences

問題リンク:Repeated Subsequences | Aizu Online Judge問題概要: 長さが300以下の文字列があたえられる この文字列を空でない2つの文字列に分ける こうしてできる2つの文字列のLCSの中で最も長いものを出力せよ 複数ある場合はどれを出力しても良い解法…

UVa 11240 : Antimonotonicity

問題リンク : http://uva.onlinejudge.org/external/112/11240.html問題概要: n個の要素からなる配列が与えられる この部分列のなかで以下の条件を満たすもののうち最長のものの長さを求めよ A > B D 解法 : 貪欲に決めていく(考え方的にはDP?) n個の配列…

UVa 526 : String Distance and Transform Process

問題リンク;String Distance and Transform Process問題概要: 2つの文字列が与えられる 最初の文字列に以下の3つの動作だけを使用して目的の文字列に変更するためにかかる 動作の最小の使用回数とその動作を出力せよ 1:文字列の任意の場所にアルファベ…

UVa 10616 : Divisible Group Sums

問題リンク:http://uva.onlinejudge.org/external/106/10616.html問題概要: n個の要素からなる配列A[i](0 配列A[i]からM個の要素を選んだ時、その和がDで割りきれるような選び方は何通り存在するかクエリーは以下の形式からなる D M D,Mは上の説明に登場す…

AOJ 1291 : Search of Concatenated Strings

問題リンク:Search of Concatenated Strings | Aizu Online Judge問題概要: n個(1 n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか? ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを1つとみなす解法:…

AOJ 2366 : Elevator

問題概要:Elevator | Aizu Online Judge問題概要: 日本語なので略解法: 動的計画法を行う 荷物があるフロアの中で最も上にあるフロアから1フロアずつ全ての荷物をもっていきながらおりていく そのフロアにある荷物を全て1つ下のフロアに持っていくため…

AOJ 2510 : Twin book report

問題リンク:Twin book report | Aizu Online Judge問題概要: 日本語なので略・自分が読み落としていた文 > 加えて,本の返却期限が近いため,まずはなるべく早くすべての本を読み終えるようにしてもらう事にした つまり、読める本があるなら感想文よりもそ…

AOJ 1287 : Stopped Watches

問題リンク:Stopped Watches | Aizu Online Judge問題概要: n個の時計の情報が与えられる ただ、どれが秒針でどれが分針、時針なのかはわからないし どこを基準に数えているのかも分からない 全ての時計がとりうる時間の間隔のうちもっとも短いものを出力…