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

hamayanhamayan's blog

競技プログラミングにおける有向グラフに関する問題まとめ

強連結成分分解 SCC 有向グラフを任意の2頂点が強連結(互いに連結)である頂点集合を成分として分解する 強連結成分を縮約すると有向グラフがDAGになる(DPやトポロジカルソートができるようになる) 強連結成分分解を使って2-SAT問題が解ける これ 問題 AOJ 強…

Insertion [AtCoder Beginner Contest 064 D]

http://abc064.contest.atcoder.jp/tasks/abc064_d

Colorful Leaderboard [AtCoder Beginner Contest 064 C]

http://abc064.contest.atcoder.jp/tasks/abc064_c

帰省ラッシュ [yukicoder No.529]

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

10^9と10^9+7と回文 [yukicoder No.528]

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

ナップサック容量問題 [yukicoder No.527]

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

フィボナッチ数列の第N項をMで割った余りを求める [yukicoder No.526]

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

二度寝の季節 [yukicoder No.525]

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

An overnight dance in discotheque [Codeforces Round #418 (Div. 2) D]

http://codeforces.com/contest/814/problem/D 問題概要 N個の円がある これらの円は互いに交わらない(接する場合はある) これらの円を2つのグループに分ける。 円は外側から数えて奇数番目の領域は塗られて、偶数番目の領域は塗られない 適切に2つのグル…

競技プログラミングにおける細かな話題まとめ

Meldable Heap Meld(併合,マージ)ができるヒープ マージテクで実装するとMeldはO(log^2N) Skew Heapで実装するとMeldはO(logN) 問題 AOJ JAG春コンテスト2013 E. Minimum Spanning Tree 解説1 解説2 解説3 UTPC2012 L. じょうしょうツリー 解説 二部グラフを…

ClangでASTを出力する

概要 ClangではCやC++のコードをASTとして出力してくれる機能がある AST: Abstract Syntax Tree, 抽象構文木 資料1 資料2 資料3 2017/06/05時点での情報です ClangでASTを出力するには clang -Xclang -ast-dump -fsyntax-only sample.cとすれば出る。 Clang3…

F. Mirrored [AtCoder Regular Contest 075]

http://arc075.contest.atcoder.jp/tasks/arc075_d

D. Widespread [AtCoder Beginner Contest 063 / AtCoder Regular Contest 075]

http://arc075.contest.atcoder.jp/tasks/arc075_b

C. Bugged [AtCoder Beginner Contest 063 / AtCoder Regular Contest 075]

http://arc075.contest.atcoder.jp/tasks/arc075_a

E. Sagheer and Apple Tree [Codeforces Round #417 (Div. 2)]

http://codeforces.com/contest/812/problem/E 問題概要 N頂点の根が頂点1の木がある。 各頂点にはりんごの個数A[i]が書いてある。 根からどの葉への距離は全ての葉に対してパリティが一致する(偶奇が一致する) 以下のようにゲームを行うとする ある葉から…

コイン [yukicoder No.524]

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

LED [yukicoder No.523]

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

Make Test Cases(テストケースを作る) [yukicoder No.522]

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

Cheeses and a Mousetrap(チーズとネズミ捕り) [yukicoder No.521]

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

C. Sagheer and Nubian Market [Codeforces Round #417 (Div. 2)]

http://codeforces.com/contest/812/problem/C 問題概要 N個の商品がある。 ここから、K個の商品をS円以内で買うとする。 K個の商品を買ったとき、i番目の商品の値段はA[i] + K*i(iは1-indexed)となる。 この時、Kを最大化して、その中で合計金額Tを最小化せ…

A. Sagheer and Crossroads [Codeforces Round #417 (Div. 2)]

http://codeforces.com/contest/812/problem/A 問題概要 問題の図を見ると分かるが、4つの方面について各4つの信号がある。 この信号が青かどうかの4×4の配列が与えられるので、歩行者と車が事故を起こす可能性があるか判定せよ。 車と車の事故は考慮しない。

競技プログラミングにおける高速ゼータ変換・高速メビウス変換問題まとめ

高速ゼータ変換・高速メビウス変換 互いに逆関数の関係にある 資料1 資料2 資料3 高速メビウス変換はその形から包除原理で良く用いられる 高速ゼータ変換 rep(i, 0, N) rep(j, 0, 1 << N) if (!(j & (1 << i))) f[j] += f[j | (1 << i)]; 高速メビウス変換 r…

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

線形計画問題 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

競技プログラミングにおける数え上げ数学計算問題まとめ

数え上げ数学計算 凄いふわっとした表現だけど、aCb,aPb,nHk,n!らへんの計算まとめ uwiさんのここにその全てがある このサイトの例題として紹介していく 問題 階乗の逆元をかけて計算する系 yukicoder No.117 組み合わせの数 (二項定理系ライブラリ最強Verif…

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」 ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい) Zobrist Ha…

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 よくある方針一覧 1. xor計算は各ビットで独立なので、別々に計算する 2. trieを使ったxorの最大最小探索がある 問題 性質3…

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

FFT : Fast Fourier Transform 高速フーリエ変換 畳み込みというのを高速化する手法 C[k] = sum{i=0...k}A[i]*B[k-i]を高速化する(O(NlogN)) 流れ 1. 配列A,Bを高速フーリエ変換する 2. 配列CをC[i] = A[i] * B[i]で作る 3. 配列Cを逆高速フーリエ変換すると…

CodeChef May Challenge 2017 問題と解説

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