2017-05-01から1ヶ月間の記事一覧
線形計画問題 LP : Linear Programming シンプレックス法という解法があるが、これを使うのはまれ 双体というのを取ると、フロー問題に帰着できる場合がある 参考1 参考2 整数計画問題 IP : Integer Programming これを解くのは難しい 枝刈りを上手くやる全…
問題概要 "+"と"-"から成る文字列がある。 "+"は数をインクリメントする命令で、-は数をデクリメントする命令。 ここから、連続でなくてもよい部分文字列をとって、X=0に対して実行する時、Xの範囲(=Xの最大-Xの最小)を最大化せよ
http://agc015.contest.atcoder.jp/tasks/agc015_e
http://yukicoder.me/problems/no/520
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 : …
http://yukicoder.me/problems/no/517
http://agc015.contest.atcoder.jp/tasks/agc015_d
http://agc015.contest.atcoder.jp/tasks/agc015_b
http://agc015.contest.atcoder.jp/tasks/agc015_a
GKLEEとは GPUプログラムの検証ソフトウェア Utah大学の研究成果 サイト 実行環境 Windows 10 Home 64bits Windows Bash GKLEE コミットf77577343c67a3f1815ce5e802e2c933f8df876a 環境構築 1. 必要な物を入れる sudo apt-get install git bison flex libboo…
www.youtube.com 問題 rngさんが解説をしていて、それを文字に起こしただけの記事。 0:25 E. Need for Speed 問題 解答 「二分探索やるだけの問題」 問題 N地点と合計時間Tがある。 i番目の地点は、地点D[i]でその前の地点からこの地点までのスピードはS[i]…
ハッシュ ある状態や数列を一意なハッシュ値に変換することで上手く判定や数え上げをやる ハッシュ化する手法は「unodered_mapやset」「ローリングハッシュ」「Zobrist Hash」 ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい) 衝突させな…
https://www.hackerrank.com/contests/w32/challenges/balls-and-boxes 問題概要 N色のボールがあり、i番目の色のボールはA[i]個ある。 M個の箱があり、j番目の箱にはC[j]個入れられる。 以下のルールで箱にボールを入れる 各箱には、各色のボールを多くとも…
https://www.hackerrank.com/contests/w32/challenges Duplication 以下のルールで文字列を作る 最初は"0"から始める 現在の文字列がsであるとき、その0と1を逆転させた文字列をtとする 現在の文字列がsであるとき、次の文字列をs+tとして文字列を伸ばしてい…
https://www.codechef.com/problems/COOK82B 問題概要 N個の数列がある。 「A[i]の約数をkとするとき、A[i] = A[i] / k, A[j] = A[j] * kと変更する」操作をする。 この操作を行うことで数列を全て同じ要素にできるなら「justdoit」と出力。 もし、できない…
https://www.codechef.com/problems/COOK82D 問題概要 N頂点M辺の無向グラフがある。 良いグラフは「全ての頂点がその頂点から初めて全ての辺を通りその頂点に戻ってくるパスが存在する連結なグラフ」とする。 完璧なグラフは「全ての連結成分が良いグラフで…
平衡二分木 平衡二分木はただ順番が正しく守られている二分木 順番ってなんだって感じですが、「数列としての順番」「値の大小としての順番」のどちらでもよくて、このへんはinsertするときに自分でちゃんと合うようにやる 実装が色々あるが、求められるクエ…
分割統治法 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」 色んな分割統治法があるが、大体空間サイズが半分になってlogNくらいで解けるようになる 再帰的な定義がなされているやつを再帰的に処理して解決する問題もある 列の分割統治法は…
https://community.topcoder.com/stat?c=problem_statement&pm=14597&rd=16929 問題概要 N個のランプがあり、on/offのどちらかの状態をとる。 最初はinitの状態になっている。 ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通り…
https://community.topcoder.com/stat?c=problem_statement&pm=14596 問題概要 N頂点の連結な無向グラフがある。 これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。 2つの距離が満たされる無向グラフがあれば復元…
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ができる機構がある。履歴は一直線。 完全永…
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 排他的論理和 性質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…
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, …
https://www.codechef.com/MAY17 Chef and his daily routine CESから成る文字列が与えられる。 それは1日のある時刻での作業を時系列順で伝えている。 その人は一日を料理する(C),食べる(E)、寝る(S)の順でこなす。 正しく時系列順で伝えられているかどうか…
最短経路を求めるには ダイクストラ【単一始点最短経路】 参考1 参考2 最大値ダイクストラ 応用して各頂点のある値の最大値を求めるダイクストラもある ダイクストラの正負を逆転させただけ 辺が負のコストを持つときに使える ベルマンフォード(Bellman-For…
https://code.google.com/codejam/contest/5314486/dashboard#s=p0 A. Fresh Chocolate Nグループあり、それぞれG[i]人いる。 1パックにP個のチョコが入っている。 あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。 もし、チョコが余…
http://codeforces.com/contest/799 A. Carrot Cakes T秒でK個ケーキを焼ける装置が1つある。 同じ装置をもう一つだけD秒かけて用意できる。 用意すると、並行してケーキを焼ける。 同じ装置を用意することで、用意しない場合より早くN個のケーキが作れるか …