復習シリーズ C Problem - C - Codeforces二分木上で、以下の2種類のクエリを処理せよ。 u-v 間の最短経路の各辺に w の重みを追加する。 u-v 間の最短経路のコストを計算せよ。 解法 木の深さは高々 60 くらいにしかならないので、愚直にやって良い。 コー…

問題 No.409 ダイエット - yukicoder 嘘解法 ドーナッツの増加量の上限が 1,000,000 であることから、B が正の値であるときストレス値が 1000 を超えないことが分かる。（1000 を超える時、どのドーナツよりもコストが高くなってしまう）よってストレス値を…

問題 Problem - D - Codeforcesmultiset に最初 0 が入っている。以下のような 3 種類のクエリが q 個くるので処理せよ。 x を 1 個 multiset に入れる。 x を 1 個 multiset から削除する。 multiset 内の各数字と x との xor をとった時の最大値を出力せよ…

問題 E: 歩くNPCたち（Walking NPCs） - 技術室奥プログラミングコンテスト#2 | AtCoder 解法 解説：歩くNPCたち from 理玖 川崎 www.slideshare.net解説の通り、小さな v について v ごとに累積和を作っておき、大きな v については小さな t について t ご…

問題 Problem - C - Codeforces コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Map; import java.util.NoSuchElementException…

問題 Problem - D - Codeforces長さ N の自然数の配列が与えられる。以下のような M 個のクエリに答えよ。 [l, r] の範囲にある整数のうち、偶数個登場したものだけを取り出し、それらの xor を出力せよ。 解法 Kmcode 先生のコードを見た。天才を感じた。[l…

問題 Problem - C - Codeforcesxy 平面上で (0, 0) にいて、(0, w) に行きたい。自分は y 軸方向に最大 u の速さで動くことができる。N この頂点を持つ凸多角形が x 軸方向に -v の速さで動く。多角形の最初の座標が与えられるので、多角形にぶつからずに（…

問題 自然数の集合 S1 と S2 がある。S1 に含まれる全ての数について、その数の自然数倍の数が S2 に含まれるとき、S2 は S1 の multiple であるということにする。S に含まれる自然数 x は A素数はいくつか。 解法 まず A A = Math.max(A, B / 2 + 1); C = …

問題 ある大きさの長方形を水平方向に切って N 行に分割する。この時、各行の高さは必ずしも同じではない。次に垂直方向に切って M 列に分割する、この時、各列の幅は必ずしも同じではない。この操作によって、N 行 M 列の小さい長方形の集合になる。元の長…

問題 www.hackerrank.com文字列 a と b が与えられる。a と b の LCS を増やすように a の好きな場所に好きな文字を 1 文字だけ挿入するような場所と文字の組み合わせはいくつあるか。 解法 A[i] と A[i+1] の間に文字 c を挿入することを考える。この時、LC…

問題 E: Candy Piles - AtCoder Grand Contest 002 | AtCoder 解法 http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdfこういう問題見ると sugim48 さんを感じる（小学生並みの感想） 解法 import java.io.IOException; import java.io.InputStre…

問題 D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder 解法 kusano_k さんの解法を見た。天才を感じる。D、UnionFindで連結成分の個数を調べるというのをlog(M)回繰り返した。「k番目までの辺を使ってz個の頂点に行けるか？」という二分探索を並列に…

問題 https://www.codechef.com/problems/CHEFLKJ要素数 N の数列が与えられ、Q 個のクエリが来る。クエリは以下の2種類である。 x 番目の数字を y に変更する。 l 番目から r 番目までの部分列の中で、過半数は同じ数であるか判定する。 解法 2次元BITを構…

問題 https://www.codechef.com/problems/CHEFIHGN x M の 2 次元平面のマップが与えられる。マップには道 '.' と壁 '*' と首都 'C' がある。ロボットがあり、ロボットに U, R, L, D のコマンドを与えることで上下左右に動かすことが出来る。全ての道にロボ…

問題 D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解法 水平方向に飛ばなければならない回数を H 、垂直方向に飛ばなければならない回数を V とする。垂直方向に飛ぶ回数を v とすると、垂直方向に戻る回数は v-V、 水平方向に飛ぶ回数 h=(N-v-…

問題 Problem - E - CodeforcesN 個の頂点からなる木がある。2K個の大学があり、それぞれ異なる頂点上にある。K個のペアを作ってペア内の各2頂点の距離の合計を最大化せよ。 解法 ある辺を見た時、ペアの両端がそれぞれ辺の反対側にある方が良い。この考えに…

解法 happy が最大となる辺の、大きい方の端は必ず選択される。 コード import java.util.ArrayList; public class BearKRoads { private int N; ArrayList<Integer>[] graph; int[] a, b; int dfs(int[] x, int k) { if (k == 0) return 0; ArrayList<int[]> ab = new Array</int[]></integer>…

問題 http://codeforces.com/contest/699/problem/EN 個のビデオがあり、ビデオ i は の確率で選択される。キャッシュは最近選ばれたビデオを K 個まで記憶しておくことができ、K 個キャッシュした状態でキャッシュに含まれていないビデオが選択された時、キ…

もうだめ コード import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; public class BearPasswordLexic { private String gen(int lenght, int isa) { String s = ""; for (int i = 0; i < lenght; i++) { if (isa % 2…

問題 H: 焼肉の達人 - CODE FESTIVAL 2015 決勝（オープンコンテスト） | AtCoder 解法 mayokoex.hatenablog.com言われてみるとダイクストラするだけ。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; impor…

問題 Problem - E - Codeforces3つのカップを1列に伏せて並べておき、真ん中のカップにコインを入れる。左右どちらかのカップをランダムに選んで真ん中のカップと交換するという操作をn回繰り返す。n は非常に大きい数なので、以下の式で与える。n 回目の操…

CodeChef の SnackDown 2016 Onsite Final Round に uwi さんと一緒にリクルートコミュニケーションズのチームとして出場しました。 コンテスト前 準決勝にあたる Elimination Round で上位 15 位以内に入れなかったため、航空券代は CodeChef 側から支給さ…

問題 1000 以下の数が N 個与えられるので、部分集合の中の任意の2つが互いに素になるように部分集合を作るとき、最大の部分集合の数を答えよ。 解法 NUMSET - Editorial - CodeChef Discuss uwiさんに聞いた。すべての数は 31 以下の素数と、32以上の素数 0…

問題 C: 天下一文字列集合 - 天下一プログラマーコンテスト2014予選A | AtCoder 解法 bitDP コード package atcoder.tenka12014quala; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; …

問題 Problem - E - CodeforcesN 枚のコインと K が与えられるので、Kを作れるコインの集合で作れる数字を列挙しろ。 解法 DP コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; i…

問題 Contest Page | CodeChef頂点数 N のツリーが与えられる。 K 個のギャングがいて、各ギャングはツリー上のある頂点集合を支配している。 クエリが Q 個くる。各クエリはある頂点 v と、ギャングのリストが含まれている。 リスト中のギャングが支配して…

解法 最小費用流そのものやんけ！！！！ コード import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class BiconnectedDiv1 { public int minimize(int[] w1, int[] w2) { int V =…

問題 Problem - 686D - Codeforces頂点数 N の木が与えられる。頂点 v を根とする部分木を考えた時、その部分木に含まれる頂点の u うち、u を消去してできる残りの部分木が、いずれも元の部分木の半分以下のサイズになるような u を「v の centroid である…

問題 Problem - C - Codeforces 解法 よく考えると状態はくらいしかない。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchE…

問題 Contest Page | CodeChefN 個の空文字列と M 個の単語が与えられる。Q 個のクエリに応答せよ。クエリは以下の 3 種類からなる。 文字列 X の先頭に文字 C を挿入する。 L〜R 番目の文字列の中で単語 P を含むものがいくつあるか出力する。 L〜R 番目の…