競技プログラミング

Codeforces Round #372 (Div. 2) D. Complete The Graph

問題 http://codeforces.com/contest/716/problem/DN 頂点で重み付き無向辺をM本持ったグラフが与えられる。辺のうちいくつかは重みが分からなくなっているが、正の整数だということは分かっている。このとき、s から t への最短距離がちょうど L となるよう…

CS Academy Round #12 Prefix Suffix Counting

問題 https://csacademy.com/contest/round-12/#task/prefix-suffix-counting/巨大な整数 N と M が与えられる。M は K 桁である。この時、1 以上 N 以下の範囲で、上 K 桁と下 K 桁がともに M と一致する整数は何通りあるか。 解法 整数 N の桁数を L とす…

天下一プログラマーコンテスト2016本戦 C - たんごたくさん

問題 C: たんごたくさん - 天下一プログラマーコンテスト2016本戦(オープンコンテスト) | AtCoder 解法 文字列 S の位置 pos を見ている時、 [pos..pos+l) と一致する長さ l の単語を列挙する。l の最大値は 200 なので、列挙される単語もたかだか 200 個…

AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行

問題 E: すぬけ君の地下鉄旅行 / Snuke's Subway Trip - AtCoder Regular Contest 061 | AtCoder 解法 editorial を見ながら解いた。辺の数は M なので、(頂点番号, 来るまでに使った鉄道会社) の組み合わせは 2M 以下になるはず。editorial にある通り、例…

天下一プログラマーコンテスト2016 予選B C - 天下一プログラマーコンテスト1999

問題 C: 天下一プログラマーコンテスト1999 - 天下一プログラマーコンテスト2016予選B | AtCoder 解法 天下一プログラマーコンテスト2016 予選B : C - 天下一プログラマーコンテスト1999 - kmjp's blog自分で思いつけるようになる気がしない…… コード import…

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

問題 E: キャンディーとN人の子供 / Children and Candies - AtCoder Regular Contest 059 | AtCoder 解法 解説そのままhttp://arc059.contest.atcoder.jp/data/arc/059/editorial.pdf コード import java.io.IOException; import java.io.InputStream; impo…

Codeforces Round #369 Div2 E. ZS and The Birthday Paradox

問題 Problem - E - Codeforces1 年は 日であるとする。k 人の人に誕生日を聞いた時、誕生日が同じ人が入る確率を求めよ。 解法 http://mayokoex.hatenablog.com/entry/2016/08/30/083738 MOD 以上の連続した区間の総乗の剰余を取ると 0 になる。 を求めると…

Codeforces Round #369 Div2 D. Directed Roads

問題 Problem - D - CodeforcesN頂点N辺の有向グラフがある。頂点 i からは a_i への辺が出ている。好きなだけ辺の向きを変えることができるとき、有向閉路を持たないグラフは何通りできるか。 解法 長さ d の閉路の辺の組み合わせは 通りである。それ以外の…

Codeforces Beta Round #55 Div2 E. Shortest Path

問題 社内の勉強会で出題された。http://codeforces.com/contest/59/problem/EN 個の頂点と M 本の重み 1 の無向辺からなるグラフがある。K 個の (a, b, c) の組が与えられる。各 (a, b, c) について a, b, c の順で連続して頂点を通ることができないとした…

CS Academy Round #11 A Single One

問題 https://csacademy.com/contest/archive/#task/a-single-one/N 個の整数からなる数列があり、S 番目だけ 1 で残りの数字は 0 である。この数列に対して「K 個の連続する区間を選択し、左右反転させる」という操作を行うことができる。またM個の位置が与…

AtCoder Grand Contest 003 D - Anticube

問題 D: Anticube - AtCoder Grand Contest 003 | AtCoder 解法 解説の通りにやる。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.…

CODE FESTIVAL の練習会をやりました

atnd.org競技プログラミングを始めるきっかけを作りたいと思い、上記のような練習会を開催した。*1 有益な情報 今日の練習会に向けて rian さんをはじめとするプロが問題を厳選した。これは良問集として活用できるかもしれない。docs.google.com 本質的な情…

Codeforces Round #368 Div2 D. Persistent Bookcase

問題 Problem - D - CodeforcesN 行 M 列のビットがあり、最初は全て 0 である。以下の 4 種類のクエリが来るので、各クエリの操作後のビットの合計を出力せよ。 i 行 j 列のビットが0であれば1にする。1ならば何もしない。 i 行 j 列のビットが1であれば0に…

Codeforces Round #362 CDE

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

yukicoder No.409 ダイエット

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

Codeforces Round #367 Div2 D. Vasiliy's Multiset

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

技術室奥プログラミングコンテスト#2 E - 歩くNPCたち(Walking NPCs)

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

Codeforces Round #366 C. Thor

問題 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…

Codeforces Round #365 D. Mishka and Interesting sum

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

Codeforces Round #365 Div2 C: Chris and Road

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

TopCoder SRM 505 Div1 Medium: SetMultiples

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

TopCoder SRM 505 Div1 Easy: RectangleArea

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

HackerRank HourRank 11 - LCS Returns

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

AtCoder Grand Contest 002 E - Candy Piles

問題 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…

AtCoder Grand Contest 002 D - Stamp Rally

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

CodeChef: Chef and Array

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

CodeChef: Chef and Land

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

AtCoder Beginner Contest 011 D: 大ジャンプ

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

Codeforces Round #364 Div2 E. Connecting Universities

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

TopCoder SRM 695 Div1 Medium: BearKRoads

解法 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>…

Codeforces Round #363 Div2 E: LRU

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

TopCoder SRM 695 Div1 Easy: BearPasswordLexic

もうだめ コード 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…

CODE FESTIVAL 2015 決勝 H - 焼肉の達人

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

Codeforces Round #362 (Div. 2) E. PLEASE

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

CodeChef Snackdown 2016 : Online Elimination Round - Jealous Numbers

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

天下一プログラマーコンテスト2014予選A C - 天下一文字列集合

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

Codeforces Round #360 Div2 E. The Values You Can Make

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

CodeChef Snackdown 2016 : Online Elimination Round - Alliances

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

TopCoder SRM 693 Div1 Easy: BiconnectedDiv1

解法 最小費用流そのものやんけ!!!! コード 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 =…

Codeforces Round #359 Div2 D. Kay and Snowflake

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

Codeforces Round #359 Div2 C. Robbers' watch

問題 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…

CodeChef Snackdown 2016 : Online Elimination Round - Cube Towers

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

Codeforces Round #358 Div2 E - Alyona and Triangles

問題 Problem - E - Codeforces平面上に、点がN個あり、どの3点を選んでも三角形を作っても面積がSを超えないように配置されている。このとき、N個の点とは別に3点選び、平面上に配置された全ての点を包含して、かつ、面積が4Sを超えないような三角形を作れ…

Codeforces Round #357 Div2 D: Gifts by the List

問題 Problem - D - Codeforces 解法 あるノード cur について考える。 cur および cur の子孫のうち、まだプレゼントを渡していない人がいるとする。この、「まだプレゼントを渡していない人」の中で cur に渡す人がいるなら、他の「まだプレゼントを渡して…

ICPC2016 模擬国内予選B D 夏合宿の朝は早い

問題 2016/Practice/模擬国内予選B/問題文とデータセット - ACM-ICPC Japanese Alumni Group 解法 強連結成分分解して、最上流の強連結成分の中で誰かが起きれば、強連結成分内の人も、その下流の人も起きる。 コード #include <bits/stdc++.h> using namespace std; int N;</bits/stdc++.h>…

ICPC2016 模擬国内予選B E ぼくのかんがえたさいきょうのおふとん

問題 2016/Practice/模擬国内予選B/問題文とデータセット - ACM-ICPC Japanese Alumni Group 解法 使われているお布団の組み合わせが bitmask とする。この組み合わせでできる最小のコストを dp[bitmask] とする。ここに新しくお布団 i を下に差し込んでコス…

TopCoder SRM 692 Div1 Easy: OrderOfTheHats

解法 二分探索+全探索+BFS コード #include <bits/stdc++.h> using namespace std; class HardProof { int N; bool check(const vector<int> &D, int minCost, int maxCost) { vector<vector<bool>> g(N, vector<bool>(N, false)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { g[i</bool></vector<bool></int></bits/stdc++.h>…

Codeforces Round #356 Div2 E: Bear and Square Grid

問題 Problem - E - Codeforces 解法 潰す範囲の正方形を愚直に全部試す。この時、正方形内部の管理を愚直にやると遅くなるので、しゃくとり法の要領で1列ずつやる。 コード #include <bits/stdc++.h> using namespace std; const int DX[] = {0, 0, 1, -1}; const int DY[]</bits/stdc++.h>…

CodeChef SnackDown Online Pre-elimination round A - Longest Increasing Subsequences

問題 Contest Page | CodeChef100 以下の自然数を使ってLISがちょうどK個存在する数列を作れ。同じ数字は1度しか使えない。 解法 MAKELIS - Editorial - CodeChef Discuss{ 2 1 4 3 }で 2*2 通りのLISが含まれる数列を作れる。ここの左側に {5 6} をつけると…

CodeChef Snackdown 2015 : Online Elimination Round - Chef and Trees

問題 Contest Page | CodeChefツリーが与えられる。1本辺を足して閉路を作るとき、直径を小さくすることが可能か判定せよ。 解法 MAXDIST - Editorial - CodeChef Discussツリーの直径を求める。ツリーの直径が偶数の時、中心となる頂点は1つだけである。中…