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

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

hamayanhamayan's blog

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

シフトセグメントツリー shifted segment tree(造語) 一般的なセグメントツリーに全ての要素をシフトさせる機能を付けたもの ルートとなる頂点を用意してそこを基準として更新や取得を行うというだけ 傾向になるかもしれないのでまとめておく 問題 yukicoder…

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

桁DP dp[桁数][条件][上限ギリギリか] Digits DP 参考サイト http://pekempey.hatenablog.com/entry/2015/12/09/000603 http://torus711.hatenablog.com/entry/20150423/1429794075 問題 上に行くほど簡単なはず ABC007 D. 禁止された数字 Typical DP Contes…

yukicoder contest-161 解説 (yukicoder No.504 505 506 507)

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

CSAcademy Round #25 問題と解説

https://csacademy.com/contest/round-25/ 0-Sum Array N個の数列Aがある。 i番目だけ-1倍して数列の総和を取ると0になるような最小のiを求めよ。 無ければ"-1" Suspect Interval N個の全ての要素が異なる数列Xがある。 以下の性質を満たすA,Bの中で、B-A+1…

競技プログラミングにおけるMo's Algorithm問題まとめ

Mo's Algorithm pekempeyさんの最強解説 pekempeyさんの記事に乗っていることですが「要素が更新されない」「クエリの先読みが可能」「区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる」という条件が大切 計算量はO( …

CodeChef April Challenge 2017 問題と解説

https://www.codechef.com/APRIL17?order=desc&sortBy=successful_submissions Similar Dishes T組の料理がある。 各料理は4つの材料で構成されている。 T組の料理が似ているならば"similar"、似てないならば"dissimilar"をそれぞれ答えよ。 ※似ている : 材…

HackerRank Week of Code 31 問題と解説

https://www.hackerrank.com/contests/w31/challenges問題 Beautiful Word 隣り合う文字が同じではない 母音("aeiouy")が隣り合わない ならば、その文字列は美しい。 文字列wが美しいなら"Yes", そうでないなら"No"を出力せよ Accurate Sorting 長さNの0~N-…

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

包除原理 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい N^2系(i+jの偶奇で+/-)と2^N系(bitが立っている数の遇奇で+/-)がある メビウス関数による高速化を伴う場合がある 問題 yukicoder No.316 もっと刺激的なFizzBuzzをください N^2系…

Codeforces Round #409 Div1 問題と解説

http://codeforces.com/contest/800問題 A. Voltage Keepsake N個のデバイスがあり、1秒にA[i]エネルギー使い、元々B[i]エネルギー分充電されている。 毎秒Pエネルギー充電できる充電器が1つだけある。 全てのデバイスを同時に使用する時、充電器を適切に使…

Google Code Jam 2017 Round 1A 問題と解説

https://code.google.com/codejam/contest/5304486/dashboard A. Alphabet Cake R*Cのマスがある。 各マスは?かA~Zで塗られている。 A~Zは最多"1つ"だけ書かれている。 残りの?のマスを全ての文字の領域が長方形になるようにA~Zを塗れ。 B. Ratatouille …

競技プログラミングにおける平方分割問題まとめ

平方分割 Square Root Decomposition 区間に対するクエリに対して高速に処理できる ここが詳しい 平方分割を理解しておくと、Mo's algorithmを理解しやすい 問題 AOJ Range Query - Range Sum Query (RSQ) セグメントツリーでできるけど、平方分割でもできる…

競技プログラミングにおけるHL分解まとめ

HL分解 Heavy-Light Decomposition 木に対するクエリをO(log^2n)くらいで処理できる 頂点にコストが載っているときと辺にコストが載っているときで処理が違ってくる 辺にコストが載っている場合は以下のようにして頂点にコストを移す http://pekempey.hatena…

競技プログラミングにおけるオイラーツアー問題まとめ

オイラーツアー(Euler Tour) 使う目的 根付き木のある頂点からの部分木に対するクエリを処理するのに長ける ある頂点がある頂点の部分木に含まれるかを高速に判定する 上手くオイラーツアーを作るとパスのコストの総和が取れる 以下、問題 Educational Codef…

Google Code Jam Qualification Round 2017 問題と解説

https://code.google.com/codejam/contest/3264486/dashboard問題 A. Oversized Pancake Flipper +と-から成る文字列Sがある。 連続する丁度K個の文字をひっくり返して全て+にする。 最小何回ひっくり返すと全て+になるか。 不可能ならIMPOSSIBLE B. Tidy N…

AtCoder Beginner Contest 058 / AtCoder Regular Contest 071 解説

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

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

遅延評価セグメント木 セグ木に区間に対して値の変更を行えるデータ構造。 色んなパターンがあるので、まとめついでに。 あと、よくHL分解と一緒に使われる(難しくなる)以下、問題 [l,r)にvを足す + [l,r)の最大値 CODE FESTIVAL 2015 決勝 D. 足ゲームⅡ htt…

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とLCP 問題 RUPC 2017 day1 D. Password(パスワード) http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day1&pid=D 高速にパターンマッチングする必要があり、その場面で使用する。 DDPC 2016 C. アメージングな文字列…

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…

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

競技プログラミングにおけるシフトセグメントツリー問題まとめ - はまやんはまやんはまやん 競技プログラミングにおける桁DP問題まとめ - はまやんはまやんはまやん 競技プログラミングにおけるMo's Algorithm問題まとめ - はまやんはまやんはまやん 競技プ…

競技プログラミングにおける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.…