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

はまやんはまやんはまやん

hamayanhamayan's blog

RUPC 2017 day1 解説

競技プログラミング

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day1

以下、解説

続きを読む

競技プログラミングにおける動的計画法更新最適化まとめ

競技プログラミング

動的計画法更新最適化?

動的計画法で更新式を立ててみると、データ構造などを上手く使うことで計算量が落とせる場合がある。
参考
http://codeforces.com/blog/entry/8219
http://codeforces.com/blog/entry/47932

SegmentTree

dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
みたいに区間和や区間最大最小をもたせることで更新を行う。

問題

http://codeforces.com/blog/entry/22616 のSegment Tree & Dp

Convex Hull Trick

関数の形式になっている区間最小値を素早く見つける手法
http://satanic0258.hatenablog.com/entry/2016/08/16/181331
http://d.hatena.ne.jp/sune2/20140310/1394440369

問題
  • Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry

http://codeforces.com/contest/319/problem/C
英語を読むのが苦じゃないなら、この問題が入門に最適。
問題概要

高さA[i]の木がN本並んでいる。
チェンソーでそれを切る。
高さは単調増加しており、各木には充電料金が決められている。
チェンソーで1cm切るのに充電を全て使い切る。
充電できるのは切り取られている木から。

「dp[i] = min{j=0...i-1}(dp[j] + A[i] * B[j])」となりCHTで解ける
http://codeforces.com/contest/319/submission/25726136
計算の過程でlonglongを超えてしまうので注意。

  • yukicoder No.409 ダイエット

http://yukicoder.me/problems/no/409
「dp[i] = (iの関数) + min{j=0...i-1}((jの関数)*i+(jの関数))」となりCHTで解ける
恐らく、日本語で最も基本的なCHTの入門問題
http://yukicoder.me/submissions/158961

  • 以下まとめ

http://codeforces.com/blog/entry/8219
https://www.hackerrank.com/contests/w30/challenges/poles
http://pekempey.hatenablog.com/archive/category/Convex%20Hull%20Trick
http://arc070.contest.atcoder.jp/tasks/arc070_c

分割統治

工事中

クヌース

工事中

きたまさ法

工事中

Week of Code 30 問題と解説

競技プログラミング

問題

Candy Replenishing Robot

https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot
カップ内のボールの数をb個とする。最初はb=N。
これについて以下の操作をT回する。

1. C[i]個のボールを取り除く。つまり、b=b-C[i](各操作で取り除けることが保証される)
2. 残ったボール数が5個未満(b < 5)ならば、カップ内のボールの数をN個にするように(N-b)個を足す

操作2で足されたボールの総和は?

Find the Minimum Number

https://www.hackerrank.com/contests/w30/challenges/find-the-minimum-number
2つのint,intの最小値 -> min(int, int)
3つのint,int,intの最小値 -> min(int, min(int, int))
4つのint,int,int,intの最小値 -> min(int, min(int, min(int, int)))
となるとき、Nつのintの最小値の文字列は?

Melodious password

https://www.hackerrank.com/contests/w30/challenges/melodious-password
N文字の以下のルールを満たす文字列を全て出力せよ。

  • 小文字の英語だけ使う
  • 子音と母音を交互に置く
  • 'y'は使わない
Poles

https://www.hackerrank.com/contests/w30/challenges/poles
N本の電柱をK本にまとめる。
電柱には重さW[i]と高度X[i]がある。
ある電柱は低い高度へ動かすことしかできず、コストW[i]*dXだけかかる。
コストの総和の最小値は?

Range Modular Queries

https://www.hackerrank.com/contests/w30/challenges/range-modular-queries
N個の数列Aがある。
Q個の「[left, right]の範囲でxを法にした時にyとなる要素数を答える」クエリに答える。

A Graph Program

https://www.hackerrank.com/contests/w30/challenges/a-graph-problem
N頂点の無向グラフGがある。
この点誘導部分グラフG'のうち、(G'の三角数)÷(G'の頂点数)が最大となるグラフの点集合を出力せよ。
三角数とはグラフの点集合のうち、(a,b),(b,c),(c,a)に頂点がある三点(a,b,c)の組となる数のこと。

Substring Queries

https://www.hackerrank.com/contests/w30/challenges/substring-queries
N個の文字列がある。
この文字列に対してQ個のF(S[x], S[y])のクエリに答えよ。
F(s, ss) := 文字列sと文字列ssでそれぞれ連続する部分文字列を取った時の最大の長さ。

続きを読む

Codechef March Cook-Off 2017 問題と解説

競技プログラミング

https://www.codechef.com/COOK80

問題

Safe Robot

https://www.codechef.com/COOK80/problems/ROBOTG
縦N横Mのマスがある。
ロボットはLRUDから構成された命令に従って移動する。
全ての命令の過程でマス目からはみ出ないロボットの初期マスが存在するか。
すれば"safe"、さもなければ"unsafe"

Rainbow Graph

https://www.codechef.com/COOK80/problems/RAINBOW
N頂点の無向完全グラフがある。
各辺には色(自然数)がついている。
頂点の部分集合で全ての頂点から出ている辺のうち少なくとも色が異なる2辺があるものを"面白い"とする。
面白い頂点の部分集合のうち、頂点数が最大のものは?

Yet Another Card Game

https://www.codechef.com/COOK80/problems/CARDS777
R個の赤カードとB個の青カードがある。
P個の赤コインと(R+B-P)個の青コインがある。
R+B回、以下のクエリを行う
1. コインを1つ選ぶ
2. カードをランダムに1枚選ぶ
3. もし、同じ色ならば1ポイント得点
得点できる点の期待値は?

Increasing Xor Sequence

https://www.codechef.com/COOK80/problems/INCXOR
N個の数列Aがある。
以下のルールを満たすようなN個の数列Bは何通りあるか(mod 10^9+7)。

  • 0 <= B[1] <= B[2] <= ... <= B[N] < 2^31
  • A[1] xor B[1] <= ... <= A[N] xor B[N]
続きを読む

CSAcademy Round #21 問題と解説

競技プログラミング

https://csacademy.com/contest/round-21/

問題

Min Coin Payment

https://csacademy.com/contest/round-21/#task/min-coin-payment
無限の1,5,50ドルがある。
これを使ってKドルを最小個数で作れ。

Prime Distance

https://csacademy.com/contest/round-21/#task/prime-distance
ある数Aに以下のどちらかの操作をする。
1. Aに素数を掛ける
2. Aから素数を割る
最小何回の操作でBにできるか

Max Wave Array

https://csacademy.com/contest/round-21/#task/max-wave-array
全ての要素が異なる数列Aがある。
これをA[1] > A[2] < A[3] > A[4] < ...のような規則で並べるとき、辞書順最大のものを答えよ

0-K Multiple

https://csacademy.com/contest/round-21/#task/0-k-multiple
ある数Nの倍数で全ての桁の数がKか0である最小の数を答えよ。

Special MVC

https://csacademy.com/contest/round-21/#task/special-mvc
N頂点M辺の無向グラフがある。
このグラフには奇数長の閉路しかない。
このグラフの最小頂点被覆数を求めよ。
最小頂点被覆 : 頂点の部分集合で全ての辺の端点のどちらかが必ずその集合に属す

Tournament Cycle

https://csacademy.com/contest/round-21/#task/tournament-cycle
N頂点のtournament graphのうち、長さKの閉路が少なくとも1つ含まれる個数を求めよ。
tournament graph : 完全グラフを有向グラフにしたもの

Catch the Thief

https://csacademy.com/contest/round-21/#task/catch-the-thief
N頂点M辺の無向グラフがある。
泥棒は

  • 初期頂点は分からない
  • 毎晩、隣接する頂点に移動する

自分は

  • 毎日夜まで任意の頂点で張り込みをする

どのような順番で張り込みを行えば捕まえられるか、張り込みをする頂点の順番を答えよ。
必ず捕まえられないなら"-1"

続きを読む

競技プログラミングにおける戻すDP問題

競技プログラミング

問題

ARC 028 D. 注文の多い高橋商店

http://arc028.contest.atcoder.jp/tasks/arc028_4

yukicoder No.155 生放送とBGM

http://yukicoder.me/problems/183

Codeforces Round #405 問題と解説

競技プログラミング

http://codeforces.com/contest/790
http://codeforces.com/contest/791

A. Bear and Big Brother

http://codeforces.com/contest/791/problem/A
2つの数A,Bがある。
一回の操作でAは3倍、Bは2倍される。
最小何回の操作でA > Bとなるか。

B. Bear and Friendship Condition

http://codeforces.com/contest/791/problem/B
N頂点,M辺の無向グラフがある。
このグラフが以下の性質を満たすか判定せよ。
「全ての独立した3頂点(X,Y,Z)について(X,Y)と(Y,Z)間に辺があるとき(X,Z)間にも辺がある」

C. Bear and Different Names / A. Bear and Different Names

http://codeforces.com/contest/790/problem/A
http://codeforces.com/contest/791/problem/C
N人の兵士がいる。
この兵士の名前について、N-K+1個の情報が与えられる。
i番目の情報は[i, i+K-1]の範囲の兵士に名前がダブっている兵士のペアがあるなら"NO"、皆異なる名前であれば"YES"。
ありうる兵士の名前(10文字以内の英語大文字小文字)を出力せよ。

D. Bear and Tree Jumps / B. Bear and Tree Jumps

http://codeforces.com/contest/790/problem/B
http://codeforces.com/contest/791/problem/D
N頂点の木がある。
f(s,t) := 頂点sから頂点tへの最短距離/Kの切り上げ
全てのs<tを満たす頂点のペア(s,t)についてf(s,t)の総和は?

E .Bear and Company / C. Bear and Company

http://codeforces.com/contest/790/problem/C
http://codeforces.com/contest/791/problem/E
文字数Nの文字列Sがある。
この文字列に対して、隣り合う文字をスワップする操作を行う。
"VK"という連続文字列が出てこないようスワップするときの最小スワップ数は?

D. Bear and Rectangle Strips

http://codeforces.com/contest/790/problem/D
縦2横Nの配列がある。
各マスには整数が書かれている。
このマスから内部の和が0となる長方形を最大何個被らず作れるか

続きを読む