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 一般に単調増加は狭義単調増加であるが、広義…

桁DP dp[桁数][条件][上限ギリギリか] 下から桁DPというのもある（繰り上がり的なのが発生する時はこっちで考えるべき？） 参考1 参考2 問題 普通の桁DP ABC007 D. 禁止された数字 Typical DP Contest E. 数 EDPC Digit Sum 解説 ABC029 D. 1 yukicoder No.7…

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

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 pekempeyさんの最強解説 ei1333さんの最強解説 pekempeyさんの記事に乗っていることですが「要素が更新されない」「クエリの先読みが可能」「区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる」という…

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

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

包除原理 包除原理についての偉大なスライド 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい 基本は状態系包除原理 状態系包除原理を個数に注目して個数系包除原理にするテクがある（抽象化による状態圧縮） 例 n(AorBorC) = n(A) + n(B) …

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

並列プロセスの形式的解析 この辺を見ると大体つかめる https://ja.wikipedia.org/wiki/並行性 https://ja.wikipedia.org/wiki/プロセス計算 並列的相互作用と通信 共有メモリ通信 メッセージパッシング通信 メッセージパッシング通信 Erlang, Occamなどでプ…

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 区間に対するクエリに対して高速に処理できる ここが詳しい 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある こういう問題 1.添字と共に昇順ソート 2.バケッ…

HL分解 Heavy-Light Decomposition 木に対するクエリをO(log^2n)くらいで処理できる 辺にコストが載っている場合は頂点にコストを移す 部分木クエリもこなせる構築方法 問題 頂点にコストがある問題 yukicoder No.399 動的な領主 HL分解 + 遅延セグ木(区間加…

オイラーツアー 木をDFSしたときの順番で頂点を記録する手法 pre-order : 頂点に到着したら記録 post-order : 頂点から離れるときに記録 用途 根付き木のある頂点からの部分木に対するクエリを処理 ある頂点がある頂点の部分木に含まれるかを高速に判定する …

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

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

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をする。 ゲ…

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

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