2016-07-01から1ヶ月間の記事一覧
問題 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; …
