問題 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 解法 ボールを獲得するたびに、(ボールを獲得した時刻, ボールを獲得した場所, 直前にボールを獲得した場所, 直前にボールを獲得した場所が再度利用可能になるまでの時…

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

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

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

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

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

長閑だ 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…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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