AtCoder
問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 解法 とても重要な事実として、M以下のxの倍数を、x=1..Mについて列挙すると、その数はM logMくらいになります。自然数xのM以下の倍数の数はM/x個なので、これをx=1..Mについて全て足し合わせる…
問題 E: Grouping - AtCoder Regular Contest 067 | AtCoder 解法 dp[i][member] := i人をmember人未満のグループに分ける組合せとしてDPします。 コード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java…
問題 https://arc065.contest.atcoder.jp/tasks/arc065_d 解法 dp[x][y] := x 文字目まで決めて1をy個使ってできる決め方の数とします。l 文字目まで見るとき、どこまでがシャッフルされる範囲に含まれるかというのを前もって計算しておけば良いです。 コー…
問題 D: Xor Sum - AtCoder Regular Contest 066 | AtCoder 解法 解説動画を観ました。www.youtube.com 解法 import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.NoSuchE…
問題 C: 01文字列 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 | AtCoder 解法 ある位置を決めて、そこから前を操作1で、そこから後ろを操作2で作ることを考えます。決め打ちすべき位置はセグメントの隙間だけで良く、置換操作は…
問題 http://cf16-tournament-round1-open.contest.atcoder.jp/tasks/asaporo_c 解法 求めるべき2つの木は元のグラフの最小全域木の部分木であることは明らかなので、最初に最小全域木を作ります。S-Tパスの最も大きい辺を切るのが最適なので、各クエリに対…
問題 http://arc033.contest.atcoder.jp/tasks/arc033_3 解法 Treap を実装した。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; i…
問題 http://agc006.contest.atcoder.jp/tasks/agc006_c 解法 editorial 通りにやった。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java…
問題 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…
問題 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.…
問題 E: 歩くNPCたち（Walking NPCs） - 技術室奥プログラミングコンテスト#2 | AtCoder 解法 解説：歩くNPCたち from 理玖 川崎 www.slideshare.net解説の通り、小さな v について v ごとに累積和を作っておき、大きな v については小さな t について t ご…
問題 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個の頂点に行けるか？」という二分探索を並列に…
問題 D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解法 水平方向に飛ばなければならない回数を H 、垂直方向に飛ばなければならない回数を V とする。垂直方向に飛ぶ回数を v とすると、垂直方向に戻る回数は v-V、 水平方向に飛ぶ回数 h=(N-v-…
問題 H: 焼肉の達人 - CODE FESTIVAL 2015 決勝（オープンコンテスト） | AtCoder 解法 mayokoex.hatenablog.com言われてみるとダイクストラするだけ。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; impor…
問題 C: 天下一文字列集合 - 天下一プログラマーコンテスト2014予選A | AtCoder 解法 bitDP コード package atcoder.tenka12014quala; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; …
問題 B: せんべい - AtCoder Regular Contest 055 | AtCoder 解法 dp[n][k] := n 枚のうち k 枚食べることができる場合のNのせんべいを得られる確率、とおく。 食べるかどうか悩むのは、今までに出てきたせんべいより大きい場合だけで良い。よって残りn枚の…
問題 C: ABCAC - AtCoder Regular Contest 055 | AtCoder 解法 ABCACの5つの区間に分けるとき、末尾のA+Cの部分の長さ s を全探索する。1 つめの A の始点と、2つめの C の終点は決まっているが、A+Cの長さを定めることで、2つめの A の始点と 1 つめの C の…
問題 D: プレゼント - AtCoder Beginner Contest 038 | AtCoder 解法 最終的に重なった箱たちを内側から見た時、縦と横はそれぞれhとwの増加数列になっているはずである。このことから、もしhとwがそれぞれすべて異なる値で構成されている場合、ソートしてLI…
問題 C: 鯛焼き - AtCoder Regular Contest 054 | AtCoder 解法 http://arc054.contest.atcoder.jp/data/arc/054/editorial.pdf コード #include <bits/stdc++.h> using namespace std; int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) { int64_t d = a; if </bits/stdc++.h>…
問題 D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder 解法 ある高さ h よりも上の部分でできる長方形の最大値と、下の部分でできる長方形の合計を最大化することを考え、hを全て試せば良い。 コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void c</class></bits/stdc++.h>…
問題 C: メンテナンス明け - 第2回 ドワンゴからの挑戦状 予選 | AtCoder 解法 第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け - うさぎ小屋 コード #include <bits/stdc++.h> using namespace std; typedef pair<int64_t, int> P; int main() { cin.tie(0); ios::sync_with_stdio</int64_t,></bits/stdc++.h>…
問題 C: 高橋くんと不思議な道 - AtCoder Regular Contest 052 | AtCoder 解法 (辺Bを通った数, 頂点vまでのコスト) を頂点としてダイクストラする。 コード #include <bits/stdc++.h> using namespace std; typedef tuple<int, int, int> P; // cost, count, vertex int main() { cin.tie(</int,></bits/stdc++.h>…
問題 C: 何通りの分割方法がある？ - square869120Contest #2 | AtCoder 解法 文字列が短いので、全ての部分文字列を数字にした時の値を計算しておく。メモ化再帰で 「substr(pos, length) で D 以下になる組み合わせの数」を求めれば良い。 コード #include <bits/stdc++.h></bits/stdc++.h>…
問題 G: Escape - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 「入ったら頂点1に戻ることができずに確実に終了する点」を列挙する。逆に、これらの点以外の点は常に行き来できるので、その点数は確実に手に入る。あとは戻れない点に設定され…
問題 D: 真っ暗な部屋 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 最初 M 人の人が、それぞれの暗い部屋にいるとする。これらの人たちを全員明るい部屋に連れていくことを考える。各状態について、遷移の仕方がk通りある。全員が暗い部屋…
問題 B: 監獄 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 N回目に [0, k-2] の人は N-1 回目には +1 した位置に、[k-1, 2*k-3] の人は +2 した位置にいるので、遡っていけば良い。 コード #include <bits/stdc++.h> using namespace std; typedef long lo</bits/stdc++.h>…
