SRM 607 Div2 Easy BoundingBox たくさんの点が与えられる。これらの点を内包する最小の矩形の面積を求める。 Med PalindromicSubstringsDiv2 vectorS1とS2が与えられる。これらを連結したSに含まれる回文はいくつか。 普通にO(N3)で判定していったらTLEにな…

SRM 609 Div2 Hard VocaloidsAndSongs GUMIちゃんとIAちゃんとMAYUちゃんが三人でアルバムを出すんだってさ、アルバムに収録する曲はS曲で全ての曲は1〜3人で歌う。３人が歌うのはそれぞれgumi,ia,mayu曲。１曲でも違う娘が歌ってれば異なるアルバムとみなし…

SRM 610 Div2 Easy Divided By Zero 配列のある要素を別の要素で割った商が配列に存在しないなら商の値を配列に追加する 一回全部試しても増えたのとすでに走査してあるのを試して無かったりってのがあるので適当な回数無駄に回すと Med TheMatrix 市松模様…

SRM 612 Div2 Easy LeftAndRightHandedDiv2 i人目の人が左利きか右利きかの情報Sが与えられた時、聞き手が衝突するペアは何組か Rの右にLがあるか調べる Med EmoticonsDiv2 絵文字が1つ書いてある。これを描かれた絵文字全てをクリップボードにコピー。クリ…

しばらくやってなかったです。 SRM 614 Div2 Easy MicroStrings 初項 A, 公差 -Dの等差数列の非負である要素を順に文字列として返す やるだけ stringstreamでも使えばいいんじゃないかな Med MinimunSquareEasy 平面上にN個の点がある。この平面上の正方形で…

SRM 621 Div2 Easy 文字列が辞書順なのか短い順なのか両方なのかどちらでもないのか Med 配列に含まれる整数の和で作れない最小の整数。 何が作れるかをdpみたいに計算する Hard colorに含まれる全ての色をつくるのに必要な絵の具の数。２つの絵の具を混ぜる…

SRM 624 Div2 Easy costの中からk個選んだ時の最小コスト dpで解いた。自分で漸化式考えて、dpに落としたのは初めてです Med heightsの要素を1増やしていってM個の同じ要素作るには最低なんかインクリメントすればいいか 最初に思いついた方法では時間が足り…

問題 Formation 解く 最初簡単だろうと思って、貪欲法で解いたら、WA。 DPで解こうとするとMLEになる。 適当な人数になるまではCANにしとけばいいことに気づく。 cとaが小さくなるまでCANに割り振って、そこからDP,runtime error 数分悩む。1000 1000 3とか…

問題 日本語なので説明はありません Icicles 解法 これもDPって言うらしいです。誰かがDPだって言ってました。知りません。 つららが両端のつららよりも長ければ解け始めるってことからそのつららの長さに影響するのは両端だけ、つまり各つららに対して両端…

予選4完、本選2完です。たしか本選Aランクが220点以上だったと思います。 0592 Average Score やるだけ。下を40にそろえて平均を出す。 0593 Vote 面白い競技の順に走査してく 0594 Super Metropolis 幅優先探索で解こうとしたけど、無理。普通に計算で解け…

本選の問題がAOJで見つからないです。４完。 0576 Homework Lから国語と算数の両方の宿題が終わるのにかかる日数を引く 0577 Unique number それぞれの数字をカウントしとく。制約読み間違えてWAだした。 0578 Signboard 新しい看板の一文字目と二文字目を探…

予選で4完、本選で3完です。本選はWA連発のすえなんとかACでした。実際にはWAとかでないので一発でACできるように精進 0565 Lunch パスタの最安値とジュースの最安値を足して50引く 0566 Soccer 勝ち点数えて順位付け 0567 Best Pizza 結構迷った。結局貪欲…

問題 Knapsack Problem 解法 DPです。蟻本に詳しい説明が載ってます。何個でも使えるとかいうって問題使い回しすぎな気も。 心臓に悪いコード int dp[MAX_N+1][MAX_W+1]; int N, W, v[MAX_N], w[MAX_N]; int main(){ scanf("%d%d", &N, &W); rep(i, N) scanf…

問題 0-1 Knapsack Problem 解法 dp[i][j] := i番目までの荷物でjまでの重さを入れた時に価値の最大値 漸化式 dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) (j >= w[i]) DPで解きます。典型問題。問題の下に解説があるので参照。 int dp[MAX_N+1][MA…

問題 Coin Changing Problem 解法 DPのプラクティスのセットのところの問題ですので当然DP。普通にDPを組むと何枚でも使用できるってのkを使用枚数の上限としてO(nmk)ってなるので間に合わない。たぶん正答率が低いのはこれでTLEが出てるからかと。 dp[i+1][…

問題 Lagrange's Four-Square Theorem 四平方定理っていうのがある。全ての自然数は高々4個の平方数の和で表すことができる。nが与えられる。高々4個の平方数の和がnになる組み合わせの数を答える。 解法 全探索とdpで解けます。両方で解こうと思います 心臓…

問題 Life game 解法 dp。 dp[i][j] := iマス目でお金をjだけ持っている確率 で解く 心臓に悪いコード int main(){ while(scanf("%d%d%d", &X, &Y, &Z) && X+Y+Z){ memset(dp, 0, sizeof(dp)); memset(m, 0, sizeof(m)); rep(i, X) scanf("%d", V+i); rep(i,…

問題 Cards 解法 dpでしょうか。lからrまでを重ねるための最小コストは(l<=i<r)、lからiまでとi+1からrまでのコストにlからiまでの塊とi+1からrまでの塊を重ねるためのコストの最小値。 dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + a[l]b[i]a[i+1]*b[r]) コード int dp[100][100], n, a[100], b[100]; int dfs(int l, int r){ if(l == r) return 0; if(dp[l][r] >= 0) return dp[l][r]; int res…</r)、lからiまでとi+1からrまでのコストにlからiまでの塊とi+1からrまでの塊を重ねるためのコストの最小値。>

問題 Sum of Different Primes 解法 動的計画法の勉強。DPどうやって書くのか、検討つかん。諦めてDFSで書いてみた。引数、３つになる。減らそうと思ったけど減らせない。O(1120以下の素数の数\K\N)で実装できそうだと思ったけど、O(K\N)*の実装考えてた。 …

8月に入ったら情報オリンピックの過去問を解いてく予定なので動的計画法が使えないとどうにもならないと思い、勉強します。題材は蟻本の01ナップサック問題から ナップサック問題 重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品…

問題 Cleaning Robot 解法 dpでやった、dp[i][y][x] := iターン目に(y,x)につく確率。 漸化式は dp[i+1][次のy座標][次のx座標] += dp[i][今のy座標][今のx座標] * 0.25 if(進めるなら) dp[i+1][今のy座標][今のx座標] += dp[i][今のy座標][今のx座標] * 0.2…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157) 解法 DPで解きます。ソートした後最長増加部分列を求めます。 コード int n, m; vector<pi>s; int dp[1024]; int main(){ while(scanf("%d", &n) && n){ s.clear(); int h, r; rep(i, n){</pi>…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011) 解法 詳しくはhttp://www.deqnotes.net/acmicpc/p0017/。 コード ````cpp int m[64][64], in[64][32]; int main(){ int n, f, day; while(scanf("%d", &n) && n){ memset(m, 0, sizeo…