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

hamayanhamayan's blog

Exhausted? [AtCoder Regular Contest 076 F]

http://arc076.contest.atcoder.jp/tasks/arc076_d

Connected? [AtCoder Regular Contest 076 E]

http://arc076.contest.atcoder.jp/tasks/arc076_c

Built? [AtCoder Beginner Contest 065 / AtCoder Regular Contest 076 D]

http://arc076.contest.atcoder.jp/tasks/arc076_b

Reconciled? [AtCoder Beginner Contest 065 / AtCoder Regular Contest 076 C]

http://arc076.contest.atcoder.jp/tasks/arc076_a

Trained? [AtCoder Beginner Contest 065 B]

http://abc065.contest.atcoder.jp/tasks/abc065_b

Expired? [AtCoder Beginner Contest 065 A]

http://abc065.contest.atcoder.jp/tasks/abc065_a

自然数の収納方法 [yukicoder No.535]

https://yukicoder.me/problems/no/535

フィボナッチフィボナッチ数 [yukicoder No.534]

https://yukicoder.me/problems/no/534

Mysterious Stairs [yukicoder No.533]

https://yukicoder.me/problems/no/533

Possible or Impossible [yukicoder No.532]

https://yukicoder.me/problems/no/532

エヌスクミ島の平和協定 [yukicoder No.531]

https://yukicoder.me/problems/no/531

年齢って毎年変わるし覚えるの難しいよね [yukicoder No.530]

https://yukicoder.me/problems/no/530

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

凸包 頂点集合の部分集合で構成されてる多角形が凸多角形かつ全ての頂点を包含する多角形 O(NlogN)のアルゴリズムがある ここに色々紹介されている 動的凸包という概念もある 直線を使っても凸包が作れるらしい これ これもそれっぽいことをする 問題 AOJ 凸…

XOR Replace [AtCoder Grand Contest 016 D]

http://agc016.contest.atcoder.jp/tasks/agc016_d 解法 http://agc016.contest.atcoder.jp/submissions/1365639www.youtube.com 解説放送の副読本として書きます。一回の操作は配列とそのxor和とのswapに相当する。 これは解説放送の通り。そのため、それぞ…

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

木DP dp[i] := 頂点iの部分木についての何か Codeforcesで見つけた記事 全方位木DPという派生もある 二乗の木DPという、頂点集合のDPをマージする時に部分木の要素数の個数分だけ使ってマージするようにするとO(N^3)がO(N^2)に落ちるテクがある 元ネタ 木DP…

+/- Rectangle [AtCoder Grand Contest 016 C]

http://agc016.contest.atcoder.jp/tasks/agc016_c

Shrinking [AtCoder Grand Contest 016 A]

http://agc016.contest.atcoder.jp/tasks/agc016_a

競技プログラミングにおけるデバッグ用情報まとめ

木 13頂点12辺 1 2 2 3 3 4 1 5 5 6 2 7 2 8 7 9 6 10 7 11 13 1 6 12 無向グラフ 14頂点17辺 1 2 2 3 3 1 3 4 4 5 5 6 6 7 7 8 8 5 9 10 10 11 11 9 3 9 12 13 13 4 13 14 12 14 非連結な無向グラフ 13頂点14辺 1 2 2 3 3 1 1 4 4 5 5 6 6 7 7 8 8 5 9 10 1…

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

WaveletMatrix 理解が追いついてなくて、不確定な情報が多い可能性があります ウェーブレット行列、ウェーブレット木というのもあるが下位互換でできることは一緒?(かなり怪しい解釈) ウェーブレット行列は静的なものだが、動的にもできるし、永続化もでき…

Chef and Prime Queries [CodeChef June Challenge 2017]

https://www.codechef.com/problems/PRMQ 問題概要 N要素の配列Aがある。 これについて、Q個の以下のクエリに答える。 A[L]~A[R]を素因数分解したときに、X以上Y以下の素因数の個数を答えよ。

Army Creation [Educational Codeforces Round 22 E]

http://codeforces.com/contest/813/problem/E 問題概要 N個の配列Aと、ある数Kがある。 これについてオンラインで以下のクエリに答える。 同じ数字はK個までしか数えないものとして、A[L]~A[R]の数の個数を数えよ。

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

強連結成分分解 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