解法 個数制限なしナップサック問題を3パラメータそれぞれについて解く。割と問題文読解ゲー。 配列を再利用すると、0-1ナップサックと個数制限なしナップサックの違いはループの方向のみとなる（蟻本） という意味を確認しておく。0-1の場合は、j のループ…

解法 先にワーシャルフロイドで陸路経由と海路経由それぞれについて全点対最短路を解く。あとは dp[配達し終えたノード][ボートの位置] = はじめの位置からの最短距離 としたDPを書けば良い。WarshallFloyd+DPでなく、普通にダイクストラでやろうとすると ML…

解法 setのDPをする。任意の二人を遭遇させるたび、持っている断片を集める。それを日数でループする。 一度に多数の人間の断片が集積すること、また一度はぐれた人に二度以上合う事によりさらに集められる事を考えると良い。日数と人の番号の表で、それぞれ…

解法 左右対称に着目して、その場合の数を求めるためにmapで数え上げた文字の数を半分にする。 奇数の文字が２つ以上あったら回文は作れない。一つの文字のみが奇数なら、中央に一文字置けば回文になる。後は同じものを含む順列を利用する。 （回文の半分の…

解法 互いに (i)場所を選び (ii)ファンの人数 a, b を選び (iii)ファンの人数が一致する（a = b）とき (iv) それぞれ 1 / (ファンの人数の範囲) を足し合わせる。 class TheFansAndMeetingsDivTwo { public: double find(vector <int> minJ, vector <int> maxJ, vector <int></int></int></int>…

問題文 http://uva.onlinejudge.org/external/119/11954.html解法１ 二項演算子に遭遇するたびに両側区間で再帰する。（普通の構文解析と同じ）1000文字までのビットが存在しうるので、数字は deque で各桁の値(1 or 0)を管理する。単項演算子の優先順位は数…

問題文 http://uva.onlinejudge.org/external/120/12001.html解法 問題の否定を取って全体の場合から引けば O(N^2) で答えが出る。 O(N^4) でも通るみたいだけど、多分それだとコードが書きにくくなる気がする。下で組み合わせは パスカルの三角形のDP でな…

問題文 http://uva.onlinejudge.org/external/119/11955.html概要 二項展開せよ。解法 パスカルの三角形のDP（orメモ化再帰） long long 係数、乗数、文字の場合分け 反省 最大ケースに気をつけよ 場合の数は long long にならないか？今回は関係ないが、確…

解法 ソートして初めからK番目までの和反省 EasyとMediumが似たような問題だった。本番でChallengeフェーズのとき Easy の問題を Med の問題と思い込んで、無意味に Easy 落とそうとして失敗した。 #include <bits/stdc++.h> using namespace std; #define allof(c) (c).beg</bits/stdc++.h>…

解法 ソートして区間[i, i+M)を足したものをすべて調べる。heights[i+M-1]*M との差分が最小のとき、その差分を出力するだけ。 #include <bits/stdc++.h> using namespace std; #define allof(x) (x).begin(), (x).end() class BuildingHeightsEasy { public: int minimum(i</bits/stdc++.h>…

解法１ D周りをFからDに更新するループをT回繰り返す。T回のループの中で編集用のvectorをもって、ループの最後にvector本体に代入する。解法２ 全てのFから最も近いDまでの距離をBFSで求めて、Fの場所のセルに値を代入。最後にDまたはセルの値がT以下のFを…

解法１ 先ず蟻本に掲載されている問題(Ants)と同じように、２つのボールの衝突は衝突していないですり抜けると同等であることに気づく。ボール二者のみについて着目すると、これらは「互いに離れていく」か「両方左に進む」か「両方右に進む」か「互いに近づ…

問題文 http://uva.onlinejudge.org/external/118/11837.html概要 鍵盤が同じ間隔で打たれているとき、譜面Bは譜面Aのメロディを剽窃した疑いがある。疑いがある場合は 'S' そうでない場合は 'N' を出力せよ。（詳しい内容は本文参照）解法 入力の表を配列に…

解法 区間DP。計算結果の重複を防ぐので set memo[l][r]; で計算結果を管理する。事前に括弧付けされたものは一つの項としてまとめなければならないので、文字列[l,r) が、完全に "(expr)" の形で表せる場合を捉える必要がある。（str[l] = '(', str[r-1] = …

概要 プレイヤー二人が交互に対戦する。行列から行を選べるので、その行の要素それぞれについて１以外で割り切れる数の内好きな数で割って良い。一つも割り切れる要素がない場合（つまり行の要素が全て１の場合）その行は選ぶことは出来ない。自分の番のとき…

解法 拡張グラフにおけるダイクストラを書くだけ。 ポイントは 座標に対応したノード番号のナンバリング（座標としてxとyの２要素持つよりキューに入れるとき都合が良い） ノード番号から座標への変換 左右の足を交互に移動 -> グラフの要素を2倍にする 複数…

問題 http://uva.onlinejudge.org/external/118/11863.html解法 区間DP（メモ化再帰）左右から区間を狭めていくだけ。 自分がパスしたら相手もパスするので、パス可能最大回数 K という情報に意味は無い。 数列に42が含まれる場合、ワイルドカードなので、は…

問題文 http://uva.onlinejudge.org/external/117/11795.html概要 "Mega Man" であるあなたは "Mega Buster" を使って敵のロボットを倒していく。ただ "Mega Buster" だけでは全ての敵を倒すことが出来ない。倒した敵から武器を奪い、その武器を使うことで倒…

問題文 http://uva.onlinejudge.org/external/118/11870.html概要 テストで英単語の同義語と対義語の試験が出る。対策の手間を省くために、単語の対義語の対義語が元の単語の同義語である場合、少ない関係を覚えるだけで覚えていない単語同士の関係も導き出…

問題文 http://uva.onlinejudge.org/external/118/11860.html概要 アルファベットの小文字と記号で表された文書がある。一つの単語はアルファベットの小文字以外の文字で区切られる。全ての単語を含む区間を出力せよ。解法 尺取り法で解く。 #define INF (1<…