HackerEarth July Circuits : Benny and the Universe

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

Codeforces Round #364 (Div. 2) D. As Fast As Possible

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

Codeforces Round #363 (Div. 2) DE

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

ACPC2016 Day2 J : Char Swap

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

ACPC2016 Day2 H : Hogemon Get

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

TopCoder SRM 699 Div1 Medium: FromToDivisible

問題 Div 2 Hard の制約きついバージョンらしいのですが、Div 2 で書いたコードがそのまま通ります。kenkoooo.hatenablog.com コード import java.util.ArrayDeque; import java.util.ArrayList; public class FromToDivisible { // 最大公約数 private stat…

TopCoder SRM 699 Div1 Easy: OthersXor

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

TopCoder SRM 699 Div2 Hard: FromToDivisibleDiv2

問題 N 個の頂点があり、各頂点に 1 から N の番号が振られています。各 a[i] と b[i] について、 a[i] の倍数の全ての頂点から b[i] の倍数の全ての頂点へ距離 1 の有向辺を張ります。S から T への距離を求めてください。 解法 条件より 距離が 500 以上に…

Codeforces Round #373 (Div. 1) C. Sasha and Array

問題 http://codeforces.com/contest/718/problem/C下記の二種類のクエリを処理せよ。 数列 のlからrまでにvずつ足せ。 数列 のlからrまでの各 について を求め、その和を出力しろ。 解法 StarrySkyTree の各ノードに行列をもたせる。 コード import java.io…

Codeforces Round #373 (Div. 2) C. Efim and Strange Grade

問題 Problem - C - Codeforces小数がある。t 回任意のiについて、「小数点第i位で四捨五入する」という操作をする時、得られる最大の数を求めよ。 解法 小数点に出来るだけ近い位置で四捨五入するのが良い。 コード import java.io.IOException; import jav…

AWS の正しい使い方

長閑だ pic.twitter.com/I7d1SHtZNl— 宇宙ツイッタラーX (@kenkoooo) 2016年9月10日 長閑だ pic.twitter.com/COxTmrZ9RT— 宇宙ツイッタラーX (@kenkoooo) 2016年9月10日 山はいいぞ。 pic.twitter.com/9fk2EMkJbu— 宇宙ツイッタラーX (@kenkoooo) 2016年9月1…

ACPC2016 Day2 G : Star

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=G 解法 正 N 角形から小さい二等辺三角形を N 個除けば良い。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import j…

ACPC Day2 F : Curling Puzzle

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=F 解法 1 列だけのときは @ の片側にある @ から一番近いストーンの位置と、 @ の反対側にあるストーンの数を持てば解けます。それ以外の場合は↓F問題です。 pic.twitter…

ACPC Day2 D : One-Time Path

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=D 解法 N-1 に着く時刻を最大化したいだけで、それ以外の頂点に着く時刻は早ければ早いほど良いことに気づく。あとは一度見た辺を二度と見たくないという気持ちを込めな…

会津大学競技プログラミング合宿2016参加記

会津大学で行われた競技プログラミング合宿に参加した。atnd.org社会人の参加者は多くはなかったが、私の競プロ歴は社会人になってからの方が長いので、今後もすごく嫌がられるまで執拗に参加し続けるつもりである。 1日目: 立命館セット http://judge.u-aiz…

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に…

ICFPC 2016 のメモ

これを読む ctylim.hatenablog.com やったこと 問題を集めるスクリプト 問題の入力を matplotlib で出力するスクリプト この辺はサーバーを立てて、一定時間おきにクロールして、ウェブで問題が見れる状態にしておけば良かった。 やったほうが良かったこと …

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 回目の操…