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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Grand Contest 012 B: Splatter Painting

DP

http://agc012.contest.atcoder.jp/tasks/agc012_b 解法 di が小さいのが鍵に見える。dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。 補足 ある頂点から距離 d …

CSAcademy Special MVC

editorial読んで概要はすぐに理解できたけど、cactus上のDPを整理するのに手間取った。この回難しすぎる。https://csacademy.com/contest/archive/#task/special-mvc/

Educational Codeforces Round 17: D. Maximum Path (Simpath)

非想定解法です。普通に解いた方が明らかに楽です。http://codeforces.com/problemset/problem/762/D

AtCoder Regular Contest 066: D - Xor Sum

DP

寝坊したので不参加。 http://arc066.contest.atcoder.jp/tasks/arc066_b 関係あるかどうか微妙なのだが、この問題と問題設定が似ている問題がCodeforcesにある。Codeforcesの方の問題はcarry型の桁DPで"殴れる"(想定解は異なるものである)。 http://codef…

Codeforces Round #382 (Div. 1) C: Ostap and Tree

DP

http://codeforces.com/contest/736/problem/C 問題概要 木が与えられる。頂点を黒か白で塗りつぶす。どの白頂点も距離K以内に黒頂点があるような塗りつぶし方は何通りあるか。 1≦n≦100 0≦k≦min(20,n-1)

Educational Codeforces Round 16: E. Generate a String

DP

問題ページ 問題概要 現在の文字列の末尾に 'a' を追加(コスト x) 現在の文字列の末尾を削除(コスト x) 現在の文字列全体をコピーし、末尾に貼り付け(コスト y) という 3 種類の操作を使って長さ n の文字列を作る最小のコストを求めよ。 $1 \le n \le…

Codeforces Round #365 (Div. 2) E. Mishka and Divisors

DP

http://codeforces.com/contest/703/problem/E 問題自体は典型だけど TL 1000ms + オーバーフロー + K=1 のコーナーケースで苦しめられた。

Educational Codeforces Round 15: F. T-Shirts

http://codeforces.com/problemset/problem/702/F 別の解があるようです。それと嘘解法の可能性があるので、あまり鵜呑みにしないでください。

CSAcademy Round #9: 101 Palindromes

DP

https://csacademy.com/contest/archive/#task/101-palindromes/

CSAcademy Round #9: Sum of Squares

DP

https://csacademy.com/contest/round-9/#task/sum-of-squares

Codeforces Round #363 (Div. 1) C. LRU

DP

http://codeforces.com/contest/698/problem/C

Codeforces Round #362 (Div. 1) D. Legen...

http://codeforces.com/contest/696/problem/D

TopCoder SRM 693 (Div. 1) BiconnectedDiv1

DP

問題 i→i+1にコストw1[i]の辺を、i→i+2にコストw2[i]の辺を張ったグラフを考える。いくつかの辺を取り除いて作れる二重辺連結のグラフのうち、辺のコストの総和の最小値を求めよ。 二重辺連結とはどの辺を取り除いても連結なグラフのことである。 1≦n≦100

CodeChef SnackDown Online elimination round

https://www.codechef.com/SNCKEL16

SnackDown Online Qualifier 2016

https://www.codechef.com/SNCKQL16

AtCoder Beginner Contest #038

http://abc038.contest.atcoder.jp/ 解説動画、ニコニコ動画だとシークバー使えなくて見るのが面倒(一般会員の感想)。

Codeforces Round #351 (Div. 1) C. Levels and Regions

3 時間近く掛けてようやく AC。 http://codeforces.com/contest/674/problem/C 問題 数列 t[i] が与えられる。これを K 個の連続する部分列に分割する。各部分列はゲームにおけるレベルに対応しており、プレイヤーはレベル 1 からレベル K の順に攻略してい…

Educational Codeforces Round 12 F. Four Divisors

大体は Editorial に書いてある方法だと思います。 http://codeforces.com/contest/665/problem/F 問題概要 1 から n までの整数のうち約数をちょうど 4 つ持つものは何個あるか。

TopCoder SRM 688 (Div. 2) Hard. ParenthesesDiv2Hard

DP

問題概要 括弧列 S といくつかの区間[Li, Ri]が与えられる。swap をすることにより全ての区間 [Li, Ri] に対し S[Li, Ri] が対応の取れた括弧列になるようにしたい。swap 回数の最小値を求めよ。もし不可能なら -1 を出力せよ。 なお、どの区間も重なってい…

TopCoder SRM 687 (Div. 2) Hard. Queueing

DP

2つほど解法を思いついたので両方書きます。 問題概要 2 つのレジがあり、レジ i には len[i] 人並んでいる。レジ i が一人を処理するのに掛かる時間は確率的に変化し、k 秒で処理する確率は (1/p)*(1-1/p)k-1 である。 レジ 1 の方が真に早くすべての人を処…

Codeforces Round #346 (Div. 2) G. Fence Divercity

DP

http://codeforces.com/contest/659/problem/G

TopCoder SRM 686 (Div. 2) Hard. BracketSequenceDiv2

DP

最初 Div 1 と同じ問題だと思ってスルーしそうになった。 問題概要 () で構成された文字列が与えられる。いくつかの文字を削除して作ることのできる正しい括弧列は何通りあるか。 Div 1 は文字の消去パターン数を求める問題だったのに対し、こちらは出来上が…

TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1

DP

起床に失敗しました。 問題概要 ()[] で構成された文字列が与えられる。正しい括弧列にするような文字の削除方法は何通りあるだろうか。

2016 TCO Algorithm Medium. EllysSocks

問題文 数列 a が与えられ、P 個の独立したペアを作る。 できるだけ絶対値の最大値が小さくなるようにペアを構成したとき、差の絶対値の最大値はいくつになるだろうか。

CROC 2016 - Elimination Round E. Intellectual Inquiry

DP

codeforces.com 問題概要 k 種類のアルファベットで構成された長さ n の文字列を t の末尾に繋げて文字列 s を作る。不連続を許した s の部分文字列の種類数を最大化したい。 s の部分文字列の種類数の最大値を求めよ。

RUPC 2016 day3 G: Destiny Draw

DP

※この解説は難しく考えすぎているのであまり参考にしない方がいいかも。 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=G らてさんにいい解法を教えてもらったので、そっちで書いたコードも挙げておきました。 原理は No.…

TopCoder SRM 683 (Div. 2) Hard. SubtreesCounting

DP

どことなく Codeforces を感じる。

8VC Venture Cup 2016 - Final Round (Div. 1) B. XOR Equation

DP

何も考えず桁 DP したけど結果的に提出は早かったので良しとしたい。 codeforces.com 問題概要 和が s、xor が x になるような正整数の対 (a, b) はいくつあるか。

Codeforces Manthan, Codefest 16 C. Spy Syndrome 2

制約が怖すぎる。 codeforces.com

動的計画法入門(数え上げ)

数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。

TopCoder SRM 682 (Div. 2) Hard. FriendlyRobot

DP

かなり苦戦。 解法 自明な DP は次のようなもの。 dp[ i 番目まで見た ][ 現在の x 座標 ][ 現在の y 座標 ][ 変更した回数 ] := 原点を通った回数の最大値 しかし O(n4) なので間に合わない。 少し考えると現在の x 座標と y 座標はなくても更新できること…

Educational Codeforces Round 8 D. Magic Numbers

DP

最初に通した解法、嘘っぽいのにどうして通ったんだろう。 codeforces.com 解法 桁 DP で解ける。 dp[ 上から i 桁目まで確定 ][ b 未満が確定 ][ a 超えが確定 ][ 0 以外を使ったか ][ 上からの桁数の偶奇 ][ mod M ] := この状態に至るパターン数 以下のこ…

Codeforces Round #342 (Div. 2) D. Babaei and Birthday Cake

codeforces.com 解法 次のような DP ができる。 dp[最後に使った体積] := 体積の総和の最大値 体積 r[i]*r[i]*h[i] は最大で 1012 になってしまうので一見この DP は不可能に思えるが、体積を座標圧縮すれば可能になる。 更新するときは最後に使った体積が v…

Codeforces 8VC Venture Cup 2016 - Elimination Round F. Group Projects

DP

通した人のコードを眺めてたら大体何をしてるのか分かったので解説を書きます。 codeforces.com 解法 配列はソートしておく。 次のようにグループ分けするのではなく、 次のようにグループ分けすると考えても imbalance は変わらない。 imbalance は図に書か…

Codeforces 8VC Venture Cup 2016 - Elimination Round D. Jerry's Protest

DP

問題を理解するのに苦戦した。 codeforces.com 解法 得点差にのみ着目して DP を行う。 dp[i][j] := i 試合目まで行ったとき、得点差が j であるような場合の数 試合数は 2 回で、得点差は 5000 通り、遷移数は 5000 通りなので 2*5000*5000 回程度ループを…

Codeforces Round #342 (Div. 2) D. Finals in arithmetic

DP

暴力解法なのであくまで参考程度に。 codeforces.com 解法 左端と右端から同時に 1 桁ずつ決定していく桁 DP を行う。 dp[ 両端 i 桁が確定 ][ 左側 i+1 桁目で桁上げしている ][ 右側 i 桁目で桁上げしている ] := この状態に到達できるか 「左側 i+1 桁目…

Codeforces AIM Tech Round (Div. 1) B. Array GCD

DP

kmjp さんのコードを見て解法を察しました。ありがとうございます。 codeforces.com 問題概要 数列 an が与えられる。この数列に以下の操作を行う。 連続する部分列を削除する 要素をひとつ選び +1 または -1 する。 操作 1 は一回のみでき、操作 2 は同じ要…

Typical DP Contest J - ボール

DP

よくある期待値の問題。 tdpc.contest.atcoder.jp 解法 oxoooxox の状態からすべて倒すまでに投げるボールの個数の期待値を $E[10111010]$ と表すことにする。つまり bitDP をする。 パターン 1:投げた先 3 マスがすべてが埋まっている v ooo このときの期…

Typical DP Contest C - トーナメント

DP

アルゴリズムが難しいというより計算量解析が難しい。 tdpc.contest.atcoder.jp 解法 セグ木っぽく区間に番号を割り振る。こうすると左の子と右の子のインデックスを求めるのが簡単になる。 考えるべきは次の DP。 dp[ i ][ j ] := 区間 i でプレイヤー j が…

Typical DP Contest D - サイコロ

DP

tdpc.contest.atcoder.jp 解法 積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。 これを使うと dp[ 振ったサイコロの個数 ][ gcd(サイコロの目の積,D) ] := 確率 ができる。状態数は D の約数のうち素…

Codeforces Round #341 (Div. 2) E. Wet Shark and Blocks

DP

本番中は問題の意味がわからなかったけど、終了後の Twitter 上で行列累乗という単語が流れていたので多分こんな問題だったんじゃないかなと思ってます。 codeforces.com 問題概要 数字 a1, ... , an が入っている袋が b 個ある。それぞれの袋から 1 つずつ…

Codeforces Wunder Fund Round 2016 D. Hamiltonian Spanning Tree

DP

方針はすぐに思いついたけど上手く書けなかった。 codeforces.com 解法 ・x ≧ y のとき できるだけ全域木以外の辺を使うのが最適。 スターグラフでなければ全域木以外の辺を用いてハミルトンパスを作れるが、スターグラフのときは全域木の辺を 1 本使わなけ…

第2回 ドワンゴからの挑戦状 予選 D - 庭園

DP

dwango2016-prelims.contest.atcoder.jp

TopCoder SRM 679 (Div. 1) Medium. RedAndBluePoints

DP

※y 軸を下向きを正として取って説明しているので注意してください。 問題概要 2次元平面上に青い点と赤い点がいくつか存在する。 内部に赤い点を含まないように凸多角形を描くとき、多角形の内部にある青い点の個数の最大値を求めよ。ただし点や線分も多角形…

Codeforces Round #338 (Div. 2) C. Running Track

問題文 codeforces.com

Codeforces Good Bye 2015 D. New Year and Ancient Prophecy

問題文 http://codeforces.com/contest/611/problem/D

yukicoder No.329 全射

DP

問題文 http://yukicoder.me/problems/663

yukicoder No.324 落ちてた閉路グラフ

DP

問題文 http://yukicoder.me/problems/879

yukicoder No.317 辺の追加

DP

問題文 http://yukicoder.me/problems/896

Codeforces Round #335 (Div. 1) A. Sorting Railway Cars

DP

問題文 codeforces.com 問題概要 配列Aが与えられるので、以下の操作を行ってソートする。 要素をひとつ選んで左端に移動させる 要素をひとつ選んで右端に移動させる ソートするのに必要な最小の操作回数を求めよ。