問題 E: Grouping - AtCoder Regular Contest 067 | AtCoder 解法 dp[i][member] := i人をmember人未満のグループに分ける組合せとしてDPします。 コード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java…

問題 http://codeforces.com/contest/757/problem/D0と1からなるn文字の文字列が与えられます。この文字列の好きな位置（先頭や末尾も含むN+1個）に仕切りを入れることができます。仕切りはいくつ入れても構いませんが、同じ位置に2個以上入れることはできま…

問題 http://codeforces.com/contest/754/problem/D[l, r] のような範囲の組が N 個あります。このうちK個を選び、K個すべてが重なる範囲を最大にしたいです。最大値と、その時選ぶ範囲のidを出力してください。 解法 非想定解法っぽい Treap コード import …

はじめに この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの23日目の記事として書かれました。最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフロ…

問題 Attachments - 2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) - Codeforces根つき木があって、各頂点にはランクとコストが定められています。各頂点について、その頂点の子孫であり、かつ、その頂点のランク未…

問題 https://arc065.contest.atcoder.jp/tasks/arc065_d 解法 dp[x][y] := x 文字目まで決めて1をy個使ってできる決め方の数とします。l 文字目まで見るとき、どこまでがシャッフルされる範囲に含まれるかというのを前もって計算しておけば良いです。 コー…

問題 http://codeforces.com/contest/744/problem/Bn x n の行列があります。行列の要素は全て非負整数で、対角成分はすべて0です。この行列に対して、n以下の自然数の集合Sをクエリとして投げると、各行についてとなる x 列目の要素のうち最小のものを返し…

問題 D: Xor Sum - AtCoder Regular Contest 066 | AtCoder 解法 解説動画を観ました。www.youtube.com 解法 import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.NoSuchE…

問題 C: 01文字列 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 | AtCoder 解法 ある位置を決めて、そこから前を操作1で、そこから後ろを操作2で作ることを考えます。決め打ちすべき位置はセグメントの隙間だけで良く、置換操作は…

問題 http://cf16-tournament-round1-open.contest.atcoder.jp/tasks/asaporo_c 解法 求めるべき2つの木は元のグラフの最小全域木の部分木であることは明らかなので、最初に最小全域木を作ります。S-Tパスの最も大きい辺を切るのが最適なので、各クエリに対…

問題 http://codeforces.com/contest/740/problem/Dツリーがあり、頂点1が根です。各頂点 u には数字が書き込まれています。各頂点 v について、v の部分木に含まれ、かつ を満たす頂点uの数を出力してください。 解法 DFS で辺の重みを BIT に持ちながら潜…

問題 http://codeforces.com/contest/740/problem/EN 個の非負の数列{a}があります。クエリが M 個あり、各クエリでは、l 番目から r 番目までの数字にそれぞれ v を足し、数列に含まれる最大の hill の幅を答えてください。 ただし、hill とはを満たす部分…

問題 http://arc033.contest.atcoder.jp/tasks/arc033_3 解法 Treap を実装した。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; i…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=L 解法 kenkoooo.hatenablog.com コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; impor…

問題 Longest Match | Aizu Online Judge 解法 SuffixArray を作ると、Sに含まれる a の SuffixArray 上での lower_bound と upper_bound を求めることができます。その中で最も前のものを求めたいですが、これはRMQで持っておけば良いです。b については上…

問題 http://codeforces.com/contest/734/problem/F 解法 Fはb_i+c_iを足すとなんとa_i*n+(sum a_j)になりそこからがんばる。あと検証もちゃんとする— 有為 (@uwitenpen) 2016年11月15日 コード import java.io.IOException; import java.io.InputStream; im…

問題 http://codeforces.com/problemset/problem/734/EN頂点のツリーがあり、各頂点は白か黒で塗られています。1回の操作で同じ色の連結成分の色を全て塗り替えることができます。ツリーを全て同じ色にするための最小の操作回数を求めてください。 解法 連結…

問題 http://codeforces.com/contest/701/problem/EN 頂点のツリー状に 2K 個の大学があります。これらの大学を K このペアに分割します。ペアとなっている大学間の距離の合計が最大となるようにペアを作るとき、その最大値を答えてください。 解法 辺 (v, p…

問題 "()" は良い文字列です。 S を良い文字列としたとき、"(SSS...S)" は良い文字列です。 文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。 解法 括弧列に対する様々な先入観から良い文…

問題 http://codeforces.com/contest/733/problem/EN 階建ての建物の中にいます。各階には 'U' または 'D' の文字が書かれています。 i 階にいて U と書かれているときは i+1 階へ、D と書かれているときは i-1 階へ移動します。移動すると、直前にいた階の…

問題 http://agc006.contest.atcoder.jp/tasks/agc006_c 解法 editorial 通りにやった。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java…

問題 http://codeforces.com/contest/732/problem/FN 頂点 M 辺の連結な無向グラフが与えられます。すべての辺の向きをそれぞれどちらか 1 方向に限定した時に頂点 i から到達可能な頂点の数を mi とします。mi の最小値を最大化するとき、その値と、その時…

問題 Problem - 732E - CodeforcesN 台のパソコンがあり、パソコン i の消費電力は Pi です。ソケットが M 個あり、ソケット j の供給電力は Sj です、消費電力と供給電力が等しいとき、パソコンをソケットに接続できます。1 つのソケットには 1 台のパソコ…

問題 Problem - D - Codeforces相異なる自然数を N 個もった集合 X があります。X の各要素 に対して、以下の操作を行うことができます。 を X から取り除き、 を X に加える。 を X から取り除き、 を X に加える。 集合 X に何回か操作を加えて Y にするこ…

問題 https://www.hackerearth.com/july-circuits/algorithm/benny-and-the-universe/N 個の整数が与えられます。Q 個の整数 X が与えられるので、各Xがこれらの整数の線形和（係数は非負整数）でできるかどうか判定してください。 解法 ダイクストラします…

問題 Problem - D - CodeforcesN 人の子供がいて、一度に K 人乗れるバスがあります。子供の速度が v1 , バスの速度が v2 である時、N 人全員が L 以上進むのに必要な時間を求めてください。 解法 全員が T だけバスに乗るとして、これを二分探索で求めます…

復習シリーズ D. Fix a Tree Problem - D - CodeforcesN 頂点の有向グラフがあり、頂点 i から頂点 a[i] に向かう辺があります。できるだけ少ない辺を張り替えてある1つの頂点に向かう有向木にしてください。 解法 連結成分内に閉路が含まれているとき、閉路…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=J 解法 J : 解説 from Takumi Yamashita www.slideshare.net元の文字列がアルファベット を 個含むとき、前半と後半に寄せて、 を 個ずつ含むようにします。（解説スライ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=H 解法 ボールを獲得するたびに、(ボールを獲得した時刻, ボールを獲得した場所, 直前にボールを獲得した場所, 直前にボールを獲得した場所が再度利用可能になるまでの時…

問題 N 匹の狼が 0〜2^30-1 の中の数字から 1 つずつ数字を選んでそれぞれ持っています。各狼は「黙秘する」か「自分以外の全ての狼の数字のXOR」かのどちらかを教えてくれます。教えてもらった情報から、全狼の数字の合計の最小値を求めてください。 解法 30…