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

hamayanhamayan's blog

2017-05-01から1ヶ月間の記事一覧

競技プログラミングにおける線形計画問題・整数計画問題まとめ

線形計画問題 LP : Linear Programming シンプレックス法という解法があるが、これを使うのはまれ 双体というのを取ると、フロー問題に帰着できる場合がある 参考1 参考2 整数計画問題 IP : Integer Programming これを解くのは難しい 枝刈りを上手くやる全…

MaximumRange [SRM 715 Div1 Easy]

問題概要 "+"と"-"から成る文字列がある。 "+"は数をインクリメントする命令で、-は数をデクリメントする命令。 ここから、連続でなくてもよい部分文字列をとって、X=0に対して実行する時、Xの範囲(=Xの最大-Xの最小)を最大化せよ

Mr.Aoki Incubator [AtCoder Grand Contest 015 D]

http://agc015.contest.atcoder.jp/tasks/agc015_e

プロジェクトオイラーへの招待 [yukicoder No.520]

http://yukicoder.me/problems/no/520

City Construction [HackerRank World CodeSprint 11]

https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland 問題概要 N頂点M辺の有向グラフがある。 ここでQ個のクエリを処理する。 1 x d : 新たに頂点を1つ用意し、d=0ならxから新頂点へd=1なら新頂点からxへ有向辺をはる 2 x y : …

壊れたアクセサリー [yukicoder No.517]

http://yukicoder.me/problems/no/517

A or...or B Problem [AtCoder Grand Contest 015 D]

http://agc015.contest.atcoder.jp/tasks/agc015_d

Evilator [AtCoder Grand Contest 015 B]

http://agc015.contest.atcoder.jp/tasks/agc015_b

A+...+B Problem [AtCoder Grand Contest 015 A]

http://agc015.contest.atcoder.jp/tasks/agc015_a

Windows BashでGKLEEを動作させるまで

GKLEEとは GPUプログラムの検証ソフトウェア Utah大学の研究成果 サイト 実行環境 Windows 10 Home 64bits Windows Bash GKLEE コミットf77577343c67a3f1815ce5e802e2c933f8df876a 環境構築 1. 必要な物を入れる sudo apt-get install git bison flex libboo…

AtCoder社 「ICPC World Final 応援配信!」 レジュメ

www.youtube.com 問題 rngさんが解説をしていて、それを文字に起こしただけの記事。 0:25 E. Need for Speed 問題 解答 「二分探索やるだけの問題」 問題 N地点と合計時間Tがある。 i番目の地点は、地点D[i]でその前の地点からこの地点までのスピードはS[i]…

競技プログラミングにおけるハッシュ問題まとめ

ハッシュ ある状態や数列を一意なハッシュ値に変換することで上手く判定や数え上げをやる ハッシュ化する手法は「unodered_mapやset」「ローリングハッシュ」「Zobrist Hash」 ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい) 衝突させな…

Balls and Boxes [HackerRank Week of Code 32]

https://www.hackerrank.com/contests/w32/challenges/balls-and-boxes 問題概要 N色のボールがあり、i番目の色のボールはA[i]個ある。 M個の箱があり、j番目の箱にはC[j]個入れられる。 以下のルールで箱にボールを入れる 各箱には、各色のボールを多くとも…

HackerRank Week of Code 32 問題と解説

https://www.hackerrank.com/contests/w32/challenges Duplication 以下のルールで文字列を作る 最初は"0"から始める 現在の文字列がsであるとき、その0と1を逆転させた文字列をtとする 現在の文字列がsであるとき、次の文字列をs+tとして文字列を伸ばしてい…

Balanced Array [CodeChef May Cook-Off 2017]

https://www.codechef.com/problems/COOK82B 問題概要 N個の数列がある。 「A[i]の約数をkとするとき、A[i] = A[i] / k, A[j] = A[j] * kと変更する」操作をする。 この操作を行うことで数列を全て同じ要素にできるなら「justdoit」と出力。 もし、できない…

Nasty Queries [CodeChef May Cook-Off 2017]

https://www.codechef.com/problems/COOK82D 問題概要 N頂点M辺の無向グラフがある。 良いグラフは「全ての頂点がその頂点から初めて全ての辺を通りその頂点に戻ってくるパスが存在する連結なグラフ」とする。 完璧なグラフは「全ての連結成分が良いグラフで…

競技プログラミングにおける平衡二分木問題まとめ

平衡二分木 平衡二分木はただ順番が正しく守られている二分木 順番ってなんだって感じですが、「数列としての順番」「値の大小としての順番」のどちらでもよくて、このへんはinsertするときに自分でちゃんと合うようにやる 実装が色々あるが、求められるクエ…

競技プログラミングにおける分割統治法問題まとめ

分割統治法 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」 色んな分割統治法があるが、大体空間サイズが半分になってlogNくらいで解けるようになる 再帰的な定義がなされているやつを再帰的に処理して解決する問題もある 列の分割統治法は…

FourLamps [TopCoderOpen 2017 Round2A Div1 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=14597&rd=16929 問題概要 N個のランプがあり、on/offのどちらかの状態をとる。 最初はinitの状態になっている。 ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通り…

DistanceZeroAndOne [TopCoderOpen 2017 Round2A Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14596 問題概要 N頂点の連結な無向グラフがある。 これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。 2つの距離が満たされる無向グラフがあれば復元…

FoxAndCake2 [TopCoderOpen 2017 Round2A Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14609&rd=16929 問題概要 チェリーがC個、いちごがS個ある。 これを以下のルールでグルーピングする。 全てのチェリーといちごが何処かのグループに入る 何グループに分けてもいい 各グループ1…

競技プログラミングにおける中国剰余定理問題まとめ

中国剰余定理 中国風剰余問題、中国人剰余問題、CRT : Chinese Remainder Theorem 表記ゆらぎがむっちゃあるのでCRTで統一した方がいいんじゃないかと思ってる 解説 解ける問題 ある数m1,m2,...,mnとある数a1,a2,...,anがあり、 x ≡ a1 (mod m1) x ≡ a2 (mod…

競技プログラミングにおける永続データ構造問題まとめ

永続データ構造 persistent data structures 解説 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。 完全永…

AtCoder Beginner Contest 062 / AtCoder Regular Contest 074 解説

ABC062 http://abc062.contest.atcoder.jp ARC074 http://arc074.contest.atcoder.jp 【ARC074/ABC062】コンテストは終了しました。ご参加ありがとうございました。解説PDF:https://t.co/Wpk2kKKcJz解説動画:https://t.co/6I4t8RR6Ru— AtCoder (@atcoder) …

競技プログラミングにおけるXOR問題まとめ

XOR 排他的論理和 性質1「交換則、結合則が成り立つ」2「a xor a = 0」3「ある数xのb番目のビットが1である x mod 2^(b+1) ≧ 2^b」性質4「0≦aのとき、4a, 4a+1, 4a+2, 4a+3のxor和は0」 方針1「xor計算は各ビットで独立なので別々に計算」2「trieを使ったxor…

競技プログラミングにおける畳み込み問題まとめ(FFT,アダマール変換,メビウス変換,ゼータ変換)

2種類の畳み込み subset convolution 資料1 資料2 資料3 ゼータ変換とメビウス変換は逆変換の関係にある ゼータ変換(状態xを含む状態yを全列挙) 高速ゼータ変換でO(n2^n) g[x] = sum{y⊆x}f(y) → rep(i, 0, N) rep(msk, 0, 1 g[x] = sum{x⊆y}f(y) → rep(i, …

CodeChef May Challenge 2017 問題と解説

https://www.codechef.com/MAY17 Chef and his daily routine CESから成る文字列が与えられる。 それは1日のある時刻での作業を時系列順で伝えている。 その人は一日を料理する(C),食べる(E)、寝る(S)の順でこなす。 正しく時系列順で伝えられているかどうか…

競技プログラミングにおける最短経路問題まとめ [ダイクストラ, ベルマンフォード, ワーシャルフロイド]

最短経路を求めるには ダイクストラ【単一始点最短経路】 参考1 参考2 最大値ダイクストラ 応用して各頂点のある値の最大値を求めるダイクストラもある ダイクストラの正負を逆転させただけ 辺が負のコストを持つときに使える ベルマンフォード(Bellman-For…

Google Code Jam Round 2 2017 問題と解説

https://code.google.com/codejam/contest/5314486/dashboard#s=p0 A. Fresh Chocolate Nグループあり、それぞれG[i]人いる。 1パックにP個のチョコが入っている。 あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。 もし、チョコが余…

Codeforces Round #413 問題と解説

http://codeforces.com/contest/799 A. Carrot Cakes T秒でK個ケーキを焼ける装置が1つある。 同じ装置をもう一つだけD秒かけて用意できる。 用意すると、並行してケーキを焼ける。 同じ装置を用意することで、用意しない場合より早くN個のケーキが作れるか …