読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

競技プログラミング

AtCoder Beginner Contest 058 / AtCoder Regular Contest 071 解説

http://abc058.contest.atcoder.jp http://arc071.contest.atcoder.jp www.youtube.com 以下、解説

競技プログラミングにおける遅延評価セグメント木問題まとめ

遅延評価セグメント木 セグ木に区間に対して値の変更を行えるデータ構造 pushを使った実装が分かりやすい(pekempeyさんの記事が分かりやすい) よくHL分解やオイラーツアーなどと一緒に使われる(難しくなる) 「vにする」実装の方が簡単なので、こちらから取り…

HourRank 19 問題と解説

https://www.hackerrank.com/contests/hourrank-19/challenges 問題から Recover the Arrays N個の配列が与えられる。 これを先頭から「e a[0] a[1] ... a[e-1]」のルールで改行する。 何行になるか。 What Are the Odds? N個の石の山に対してNimをする。 ゲ…

TCO 2017 Round 1A 問題と解説

問題 Easy. PingPongQueue M人の参加者がいて、それぞれ力skills[i]を持っている。 キューには0さんからM-1さんまで順番に入っている。 以下のルールでゲームをする時、K番目のゲームの勝者と敗者の力の大きさを答えよ。 1. 2人の参加者が揃っていないなら、…

AtCoder Grand Contest 012 解説

http://agc012.contest.atcoder.jp A. AtCoder Group Contest http://agc012.contest.atcoder.jp/submissions/1194360 考察すると、降順で並べた時の偶数番目(2番目,4番目,6番目…)を選択していけば良いと分かる。 それを取る。 Atcoder300点はそんなにつらい…

Codeforces Round #407 問題と解説

http://codeforces.com/contest/788 http://codeforces.com/contest/789 A. Anastasia and pebbles K個だけ入るポケットが2つある。 N種類の小石がそれぞれW[i]個ある。 1日に各ポケット 最大K個だけ入れられる 同じ種類しか入れられない 最短何日で全て回収…

RUPC 2017 day2 解説

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day2本物の解説はこの方のSlideShareにあります。 https://www.slideshare.net/yoshidakuroura/presentations以下、解説

CSAcademy #22 問題と解説

https://csacademy.com/contest/round-22/ 問題 Triangle Count N本の棒があり、長さが分かっている。 この中から任意の3本を選んで三角形が作れる組合せは何通り? Frequency Exception N要素の配列がある。 この中で配列の中に現れる回数が他と異なる要素…

Educational Codeforces Round 18 問題と解説

http://codeforces.com/contest/792 問題 A. New Bus Route N点の座標が与えられる。 任意の2つの座標の最短距離とその最短距離となる2つの座標のペアの組合せを求めよ。 B. Counting-out Rhyme N人が円状に昇順で並んでいる。最初リーダーを1さんとし、以下…

Topcoder SRM 711 問題と解説

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16880 問題 Div1 Easy. ConsecutiveOnes 整数N,Kがあり、以下の性質を満たす最小のmを答えよ。 1. N ≦ m 2. mを2進数にすると少なくともK個連続した1がある Div1 Med. OrderedProduct 素数を…

競技プログラミングにおけるSuffix Array+LCP問題まとめ

Suffix Array 接尾辞配列 全文探索、パターンマッチングに使える Suffix Array構築後にLCPを併用すると更に高速化できる LCP Longest Common Prefix ある2つの文字列について接頭語がどれだけ一致しているか 複数文字列があるとき、ある任意の2つのLCPを求め…

yukicoder contest-159 解説 (yukicoder No.494 495 496 497 498)

http://yukicoder.me/contests/160 以下、解説

Codeforces Round #406 問題と解説

http://codeforces.com/contest/786 http://codeforces.com/contest/787 A. The Monster http://codeforces.com/contest/787/problem/A t回目にAさんはb+ta秒に叫び、Bさんはd+tc秒後に叫ぶ。 同時に叫ぶのは最短で何秒後か。 B. Not Afraid http://codeforc…

RUPC 2017 day1 解説

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day1本物の解説はこっちです。Day1の解説スライドです https://t.co/wa3pgp7mgS ジャッジ解はこちら https://t.co/ESSECDeZDi #rupc2017— tubo28 (@tubo28) 2017年3月24日 以下、解…

競技プログラミングにおける動的計画法更新最適化まとめ

動的計画法更新最適化? 動的計画法で更新式を立ててみると、データ構造などを上手く使うことで計算量が落とせる場合がある。 参考 http://codeforces.com/blog/entry/8219 http://codeforces.com/blog/entry/47932 SegmentTree dp[i][j] = dp[i-1][0] + dp[…

Week of Code 30 問題と解説

問題 Candy Replenishing Robot https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot カップ内のボールの数をb個とする。最初はb=N。 これについて以下の操作をT回する。1. C[i]個のボールを取り除く。つまり、b=b-C[i](各操作で…

Codechef March Cook-Off 2017 問題と解説

https://www.codechef.com/COOK80 問題 Safe Robot https://www.codechef.com/COOK80/problems/ROBOTG 縦N横Mのマスがある。 ロボットはLRUDから構成された命令に従って移動する。 全ての命令の過程でマス目からはみ出ないロボットの初期マスが存在するか。 …

CSAcademy Round #21 問題と解説

https://csacademy.com/contest/round-21/ 問題 Min Coin Payment https://csacademy.com/contest/round-21/#task/min-coin-payment 無限の1,5,50ドルがある。 これを使ってKドルを最小個数で作れ。 Prime Distance https://csacademy.com/contest/round-21/…

競技プログラミングにおける戻すDP問題

戻すDPとは https://yukicoder.me/wiki/polynomial_techniques http://sigma425.hatenablog.com/entry/2015/07/31/121439 問題 ARC 028 D. 注文の多い高橋商店 http://arc028.contest.atcoder.jp/tasks/arc028_4 yukicoder No.155 生放送とBGM http://yukico…

Codeforces Round #405 問題と解説

http://codeforces.com/contest/790 http://codeforces.com/contest/791 A. Bear and Big Brother http://codeforces.com/contest/791/problem/A 2つの数A,Bがある。 一回の操作でAは3倍、Bは2倍される。 最小何回の操作でA > Bとなるか。 B. Bear and Frien…

AtCoder Beginner Contest 056 / AtCoder Beginner Contest 070 解説

http://abc056.contest.atcoder.jp http://arc070.contest.atcoder.jp以下、解説

Codeforces Round #404 問題と解説

http://codeforces.com/contest/785 A. Anton and Polyhedrons http://codeforces.com/contest/785/problem/A "Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。 N個の上の5つの…

競技プログラミングにおける連立方程式問題まとめ

連立方程式を使った解法について 一次連立方程式を解く ガウスの消去法, 反復法(誤差に注意)のどちらでも解ける 反復法で10^4ループぐらいすれば十分な精度が得られそう?(初期値も適当で大丈夫そう。誤差10^-9以内でもACできた) 漸化式を作った時にDP更…

AtCoder Grand Contest 011 解説

http://agc011.contest.atcoder.jp以下、解説

Battle Conference U30 解説

http://bcu30.contest.atcoder.jp以下、解説

yukicoder contest-158 解説 (yukicoder No.490 491 492 493)

http://yukicoder.me/contests/159解説です。

Codeforces Round #403 問題と解説

http://codeforces.com/contest/782 A. Andryusha and Socks http://codeforces.com/contest/782/problem/A 1~N番のN組の靴下がある。 左右合わせて2N個の靴下をある順番で受け取る。 もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、も…

HackerRank Game Theory の勧め

HackerRank Game Theory https://www.hackerrank.com/5-days-of-game-theory Typical DP Contestというのがありますが、それのゲーム理論版 ゲームの勝敗判定をする問題を解く選択肢 必勝法・貪欲法(必勝の条件・法則がある) バックトラッキング(遷移先に…

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

へのリンク http://codeforces.com/blog/entry/22616 覚書ついでに。

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

半環 競技プログラミング的な解釈だと https://www.slideshare.net/chokudai/abc009/86 が神がかって分かりやすい。 pekempeyさんの解説もお金取って良いんじゃないかレベルで神がかってる http://pekempey.hatenablog.com/entry/2017/03/07/023127 半環一覧…

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

易しい確率問題 中難易度の確率問題 yukicoder No.475 最終日 - Writerの怠慢 http://yukicoder.me/problems/no/475 確率DP 難しい確率問題

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

区間DP dp[L][R] := 区間[L,R]についての何か 簡単な入門問題があまりなかったですね 問題 Codeforces Tinkoff Challenge - Elimination Round D. Presents in Bankopolis http://codeforces.com/contest/793/problem/D IPCP国内予選2016 D. ダルマ落とし ht…

競技プログラミング練習問題集

フロー 競技プログラミングにおける最小費用流問題まとめ - はまやんはまやんはまやん 競技プログラミングにおける二部マッチング問題まとめ - はまやんはまやんはまやん 競技プログラミングにおける最大流問題まとめ - はまやんはまやんはまやん 数学 競技…

競技プログラミングにおけるNim/Grundy数問題まとめ

Nim/Grundy 本質を理解して無くても使うだけなら大丈夫。 どちらが勝つかを判定するような問題で使える。 HackerRankのGame Theoryも練習としていい。 hamayanhamayan.hatenablog.jp Nim N個の石山があり、交互に山から石を任意個取っていく。 先に取れなく…

競技プログラミングにおける応用動的計画法問題まとめ

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246 基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329 桁DP hamayanhamayan.hatenablog.jp 高難易度区間DP ABC 008 D. 金塊ゲーム http://abc008.contest.atcoder.jp/tas…

競技プログラミングにおける基礎動的計画法問題まとめ

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246 応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423 木DP 木の頂点についてDPを作る dp[i] := 頂点iの部分木についての何か ABC 036 D. 塗り絵 http://abc036.contest.…

競技プログラミングにおける入門動的計画法問題まとめ

基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329 応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423動的計画法は結構練習しないと難しいです。 動的計画法がよく使われる条件は以下の通りです。 数え上げ(mod 10^9+7)…

雪の足跡 [yukicoder 340]

問題 https://yukicoder.me/problems/no/340W×Hの盤面があり、N人の人がそこを通る。 i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。 移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。その移動後に(0,0)から(W - 1…

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

Aho-Corasick法とは Trie木の拡張 このページで概念を理解した http://algoogle.hadrori.jp/algorithm/aho-corasick.html 木を構築するアルゴリズムは正直理解してない ei1333さんのブログでもこれと同様の記事がある http://ei1333.hateblo.jp/entry/2017/0…

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

2-SATとは しっかりした定義ではなく競技プログラミングで使う定義では、「x ∧ y」の選言の充足判定をすること。 http://naoyat.hatenablog.jp/entry/2013/07/13/220034 http://codeforces.com/blog/entry/16205 この辺りが詳しい。 2-SATを特にはSCCを使う…

PalindromicSubseq [SRM 708 : Div1 Med]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14526N文字の文字列Sがある。 X[i] := Sの部分文字列のうちS[i]を含み、回文となる組合せ Y[i] = i * X[i] % (10^9 + 7) Y[1] xor Y[2] xor ... xor Y[N]を答えよ。1

競技プログラミングにおけるマージテク問題まとめ

間違っていたら指摘して頂けると助かります。 マージテクとは? 集合をまとめる時に大きい方に小さい方を移動させることでマージさせることです。 小さい方にしっかりまとめることで処理時間とメモリを節約できて、間に合うというやつです。 マージにかかる…

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

全方位木DP 全方角木DPとも言ったりする 普通の木DPはその頂点を根とした"部分"木についての性質を表すdp 全方位木DPはその頂点を根とした木全体についての性質を表すdp 基本的にDFSを2回回すことで全方位木を作る。 具体的には1回目のDFSで普通の木DPを作り…

競技プログラミングにおける木の同型判定問題まとめ

この前のコドフォで木の同型判定に関連した問題が出ており、この辺りの理解が微妙だったのと、rng_58さんがハッシュアルゴリズムを提唱してたりして、色々あったので、色々まとめました。 木の同型判定について 木についてDFSでハッシュを求め、その比較によ…

MultiplyAddPuzzle [SRM 707 : Div1 Med]

問題 ある数sについて以下の手順をしてある数tにしたい。1. +aする 2. *bする最小のステップ数は?0

Facebook Hacker Cup 2017 Round 2 解説

問題はこっち http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014337

Facebook Hacker Cup 2017 Round 2 問題

読解に苦しむ日本人のための記事。 なんでこんなに問題が読みにくいし、長いのか。 解説はこっち http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014451

PolandBall and Gifts [Codeforces 8VC Venture Cup 2017 - Elimination Round : F]

問題 http://codeforces.com/contest/755/problem/FN人がプレゼントを持っていて、iさんがP[i]さんに渡す。 このうち、K人がプレゼントを忘れてくる。 忘れてくる任意の組合せのうち、以下のルールによりプレゼントが貰えない人数の最大・最小を答えよ。以下…

MovingTokens [SRM 705 : Div1 Med]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14471N個のトークンが1つずつ入ったビンがある。 N*Mの行列Aがあり、以下の操作がある。0 M-1 を1つ選び、j番目のビンの中身を全てA[j][i]に全てのビンで同時に移すこの操作を無限回最適な…

競技プログラミングにおける期待値問題

この前出たんで調べてまとめた。 結構やったので、大体わかってきたぞ やり次第逐一更新する。 再帰関数系 Codeforces Round #362 (Div. 2) D. Puzzle http://codeforces.com/contest/697/problem/D Codeforces Beta Round #62 D. Half-decay tree http://co…