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

hamayanhamayan's blog

Coins [AtCoder Grand Contest 018 C]

http://agc018.contest.atcoder.jp/tasks/agc018_c

Sports Festival [AtCoder Grand Contest 018 B]

http://agc018.contest.atcoder.jp/tasks/agc018_b

Getting Difference [AtCoder Grand Contest 018 A]

http://agc018.contest.atcoder.jp/tasks/agc018_a

SHA2017 CTF Teaser Round Writeupまとめ

CTF

https://ctftime.org/event/479 [Binary 100] No comment... again... 解説1 解説2 stringsコマンドを実行して文字を見てみると、「PerlApp」という文字がある。これはPerlコードを実行可能ファイルにするものIDAを使って逆アセンブルして解析するもの この…

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

bitDP 状態集合を添え字として持つDP、N 問題 yukicoder No.357 品物の並び替え (Middle) yukicoder No.286 Modulo Discount Store yukicoder No.107 モンスター yukicoder No.134 走れ!サブロー君 CodeChef Bear and Shop Trip JOI ぬいぐるみの整理 解説 …

Fennec VS. Snuke [AtCoder Regular Contest 078 D]

http://arc078.contest.atcoder.jp/tasks/arc078_b

Splitting Pile [AtCoder Regular Contest 078 C]

http://arc078.contest.atcoder.jp/tasks/arc078_a

オンリー・ワン [yukicoder No.546]

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

ママの大事な二人の子供 [yukicoder No.545]

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

Delete 7 [yukicoder No.544]

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

命題 [yukicoder No.543]

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

1円玉と5円玉 [yukicoder No.542]

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

Jigsaw [AtCoder Grand Contest 017 E]

http://agc017.contest.atcoder.jp/tasks/agc017_e

Game on Tree [AtCoder Grand Contest 017 D]

http://agc017.contest.atcoder.jp/tasks/agc017_d

Moderate Differences [AtCoder Grand Contest 017 B]

http://agc017.contest.atcoder.jp/tasks/agc017_b

Biscuits [AtCoder Grand Contest 017 A]

http://agc017.contest.atcoder.jp/tasks/agc017_a

競技プログラミングにおけるセグメントツリー問題まとめ

セグメントツリー 数列の区間に対してのクエリに答えるデータ構造 問題集 Codeforcesのやつ 基本 基本 発展的 激ムズ 覚えるべきなのは「普通のセグメントツリー」「遅延評価セグメントツリー」「動的セグメントツリー」(「シフトセグメントツリー」) シフ…

競技プログラミングにおける二分探索・三分探索問題まとめ

~探索 二分探索は単調変化する関数に対して、YES/NOの境目を見つける探索 参考 三分探索は凸関数である関数に対して、最大値・最小値を見つける探索 参考1 参考2 二分探索・三分探索は気がつくまでが長い。単調性が無いかというのは常に考えておく リアクテ…

競技プログラミングにおけるimos法・累積和問題まとめ

累積和 累積の和をとっておくと、区間の総和がO(1)で取得できる 参考 二次元に拡張することもできる 問題 1次元累積和 2次元累積和 CSAcademy Rectangle Path JOI休憩スペース (Refreshment Area) imos法 一定区間にある数を足すクエリを仕込みO(1),後処理O(…

11 [AtCoder Beginner Contest 066 / AtCoder Regular Contest 077 D]

http://arc077.contest.atcoder.jp/tasks/arc077_b

pushpush [AtCoder Beginner Contest 066 / AtCoder Regular Contest 077 C]

http://abc066.contest.atcoder.jp/tasks/arc077_a

ss [AtCoder Beginner Contest 066 B]

http://abc066.contest.atcoder.jp/tasks/abc066_b

ringring [AtCoder Beginner Contest 066 A]

http://abc066.contest.atcoder.jp/tasks/abc066_a

3 x N グリッド上のサイクルの個数 [yukicoder No.541]

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

格子点と経路 [yukicoder No.540]

https://yukicoder.me/problems/no/540 追記 : 7/2にこっそり修正しました。「1 1 -> 3」を間違えてました。

インクリメント [yukicoder No.539]

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

N.G.S. [yukicoder No.538]

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

ユーザーID [yukicoder No.537]

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

人工知能 [yukicoder No.536]

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

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]の数の個数を数えよ。