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

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

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

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

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

文字列アルゴリズム ローリングハッシュ 文字列をハッシュ化をするもの 詳しくはこっち Suffix Array 接尾辞配列 全文探索、パターンマッチングに使える LCP ある2つの文字列について接頭語がどれだけ一致しているか 複数文字列があるとき、ある任意の2つのL…

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

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…

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日 以下、解…

動的計画法更新最適化？ 参考1 参考2 参考3 セグメント木や累積和 dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) みたいに区…

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

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

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[i+1]からdp[i]を復元することで問題を解くテク 間違ってたらごめんなさいメモ ナップサックDPで順番を変えても問題なくて、一部なくすとかなら戻すDPかも 多項式の母関数がDPになってる問題で使える（遷移が多項式の掛け算なので、多項式で割るこ…

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…

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

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つの…

連立方程式を使った解法について とりあえず、けんちょんさんの最強記事を読もう 一次連立方程式を解く ガウスの消去法（掃き出し法,O(N^3)）, 反復法（誤差に注意）のどちらでも解ける 反復法でやるときは行列累乗を使って2^20くらい回すといいかも 漸化式…

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

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

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

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

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

半環 参考1 参考2 半環一覧 (集合,+演算子,*演算子) 1. (整数,+,*) 2. (整数,xor,and) 3. (整数,max,+) 4. (行列,+,*) 考え方と注意 漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー) 漸化式をとにかく上手く作る 複数のパラメタ…

GPUプログラム検証？ プログラム検証という研究分野がある。 検証の意味合いについては色々あるが、GPUプログラム上での検証は主にデータ競合の検知が重要となる。 そのデータ競合の検知についての最近の研究についてまとめていく。最近の事情の俯瞰には、書…