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

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

hamayanhamayan's blog

競技プログラミング

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

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…

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」「永続木」「永続平衡二分木」 部分永続 1. 最新版のみ変更可能 2. Undoができる機構がある 完全永続 1. 昔のどのバージョンからでも変更で…

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)の順でこなす。 正しく時系列順で伝えられているかどうか…

競技プログラミングにおけるベルマンフォード問題まとめ

ベルマンフォード Bellman-Ford 最短距離を求めるアルゴリズム ダイクストラと違い、負のコストを含む辺があっても正しく動作する 負のサイクルがあると止まらないため、負のサイクル検出ができる 参考 最長距離を求めるようにも書け、その場合は正のサイク…

Google Code Jam Round 2 2017 問題と解説

https://code.google.com/codejam/contest/5314486/dashboard#s=p0 A. Fresh Chocolate Nグループあり、それぞれG[i]人いる。 1パックにP個のチョコが入っている。 あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。 もし、チョコが余…

Codeforces Round #413 問題と解説

http://codeforces.com/contest/799 A. Carrot Cakes T秒でK個ケーキを焼ける装置が1つある。 同じ装置をもう一つだけD秒かけて用意できる。 用意すると、並行してケーキを焼ける。 同じ装置を用意することで、用意しない場合より早くN個のケーキが作れるか …

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

マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 1. 二部最大マッチング 2. 重み付き二部最大マッチング 3. 一般最大マッチング 4. 重み付き一般最大マッチング 二部最大マッチングは最大流問題とし…

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

最大流 Max flow 有向グラフで各辺ごとに流せる水の量が決まっていて、始点から終点まで最大どれだけの量流せるかを判定する 参考1 参考2 参考3 Dinic法はO(V^2E)、フォード・ファルカーソンではO(E*maxflow) 辺の貼り方の最強スライド 最大流を応用すると「…

Topcoder SRM 714 問題と解説

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16883 Div1 Easy. ParenthesisRemoval ()から成る文字列が与えられる。 ()は良い文字列 X,Yが良い文字列ならばXYも良い文字列 Xが良い文字列ならば(X)も良い文字列 最も左の"("を1つ選んで、…

競技プログラミングにおける高度なグラフ理論問題まとめ

スペクトルグラフ理論 このスライドがとても凄い 使う行列をわかりやすく教えてくれる 無向グラフをあるルールで行列に変換したものを使って色んな問題を解決する グラフの同型判定ができたり、彩色問題が解けたりする 問題化されている(のを探せた)理論 1. …

AtCoder Grand Contest 014 解説

http://agc014.contest.atcoder.jp【AGC014】コンテストは終了しました。ご参加ありがとうございました。解説PDF:https://t.co/9jlGEa5Dci解説放送:https://t.co/AT3kOEbKyo— AtCoder (@atcoder) 2017年5月6日以下、解説

yukicoder contest 第163回 解説

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

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

LCA Lowest Common Ancestor 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること yukicoder上でのantaさんの解説 アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような……

HackerRank HourRank 20 問題と解説

https://www.hackerrank.com/contests/hourrank-20/challenges Hot and Cold 4人が部屋の温度の条件を言っている。 AさんはC[0]度以上がいい BさんはC[1]度以上がいい CさんはC[2]度以下がいい DさんはC[3]度以下がいい 4人の条件を満たす温度にできるか Cou…

HackerRank World CodeSprint 10 問題と解説

https://www.hackerrank.com/contests/world-codesprint-10/challenges問題 Reward Points 1回スワイプすると10ポイント貯まる。 一ヶ月に最大100ポイント貯められる。 三ヶ月間のスワイプ回数が与えられるので、何ポイント貯まったか答えよ。 Zigzag Array …

AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説

ABC060: http://abc060.contest.atcoder.jp ARC073: http://arc073.contest.atcoder.jp本家の解説【ARC073/ABC060】コンテストは終了しました。ご参加ありがとうございました。解説PDF:https://t.co/mRtuITS6X7解説放送:https://t.co/GLCwB5ZScR— AtCoder …

競技プログラミングにおける最長部分増加列問題まとめ

最長部分増加列 LIS : Longest Increasing Subsequense 参考サイト 入れ子構造がLISに帰着できるケースはよくある(この問題は違うけど) 二次元での入れ子構造は二次元平面上にプロットすると考えやすい 例1 例2 一般に単調増加は狭義単調増加であるが、広義…

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

シフトセグメントツリー 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が立っている数の遇奇で+/-)がある メビウス関数による高速化を伴う場合がある 問題 N^2系包除原理 yukicoder No.316 もっと刺激的なFizzBuzzを…

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) AOJ Range Query - Range Minimum Query (RMQ) AOJ …

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