読者です 読者をやめる 読者になる 読者になる

AtCoder

AtCoder Grand Contest 013 C - Ants on a Circle

問題 http://agc013.contest.atcoder.jp/tasks/agc013_c 解法 解説の通りにやった。Rustでは map を使って for を消せることを学んだ。 コード use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use st…

ABC062/ARC074

Rust でやってみました。標準入出力は他の人のを拝借してきたけど、 println マクロは出力ごとに flush しているようなので注意が必要そう。もっときれいに書けるようになりたい。 A - Grouping http://abc062.contest.atcoder.jp/tasks/abc062_a fn next() …

AtCoder Beginner Contest 010 D - 浮気予防

問題 D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoderRust で Dinitz を実装した コード use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use std::usize; use std::cmp; use std::collections…

AtCoder Regular Contest E - Snuke Line

問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 解法 とても重要な事実として、M以下のxの倍数を、x=1..Mについて列挙すると、その数はM logMくらいになります。自然数xのM以下の倍数の数はM/x個なので、これをx=1..Mについて全て足し合わせる…

AtCoder Regular Contest 067 E - Grouping

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

AtCoder Regular Contest 065 F - シャッフル / Shuffling

問題 https://arc065.contest.atcoder.jp/tasks/arc065_d 解法 dp[x][y] := x 文字目まで決めて1をy個使ってできる決め方の数とします。l 文字目まで見るとき、どこまでがシャッフルされる範囲に含まれるかというのを前もって計算しておけば良いです。 コー…

AtCoder Regular Contest 066 D - Xor Sum

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

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 C - 01文字列

問題 C: 01文字列 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 | AtCoder 解法 ある位置を決めて、そこから前を操作1で、そこから後ろを操作2で作ることを考えます。決め打ちすべき位置はセグメントの隙間だけで良く、置換操作は…

CODE FESTIVAL 2016 Elimination Tournament Round 1 A - グラフ / Graph

問題 http://cf16-tournament-round1-open.contest.atcoder.jp/tasks/asaporo_c 解法 求めるべき2つの木は元のグラフの最小全域木の部分木であることは明らかなので、最初に最小全域木を作ります。S-Tパスの最も大きい辺を切るのが最適なので、各クエリに対…

AtCoder Regular Contest 033 C - データ構造

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

AtCoder Grand Contest 006 C - Rabbit Exercise

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

天下一プログラマーコンテスト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…

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

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

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

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個の頂点に行けるか?」という二分探索を並列に…

AtCoder Beginner Contest 011 D: 大ジャンプ

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

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…

天下一プログラマーコンテスト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; …

AtCoder Regular Contest 055 B: せんべい

問題 B: せんべい - AtCoder Regular Contest 055 | AtCoder 解法 dp[n][k] := n 枚のうち k 枚食べることができる場合のNのせんべいを得られる確率、とおく。 食べるかどうか悩むのは、今までに出てきたせんべいより大きい場合だけで良い。よって残りn枚の…

AtCoder Regular Contest 055 C: ABCAC

問題 C: ABCAC - AtCoder Regular Contest 055 | AtCoder 解法 ABCACの5つの区間に分けるとき、末尾のA+Cの部分の長さ s を全探索する。1 つめの A の始点と、2つめの C の終点は決まっているが、A+Cの長さを定めることで、2つめの A の始点と 1 つめの C の…

AtCoder Beginner Contest 038 D - プレゼント

問題 D: プレゼント - AtCoder Beginner Contest 038 | AtCoder 解法 最終的に重なった箱たちを内側から見た時、縦と横はそれぞれhとwの増加数列になっているはずである。このことから、もしhとwがそれぞれすべて異なる値で構成されている場合、ソートしてLI…

AtCoder Regular Contest 054 C: 鯛焼き

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

第2回 ドワンゴからの挑戦状 予選 D: 庭園

問題 D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder 解法 ある高さ h よりも上の部分でできる長方形の最大値と、下の部分でできる長方形の合計を最大化することを考え、hを全て試せば良い。 コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void c</class></bits/stdc++.h>…

第2回 ドワンゴからの挑戦状 予選 C: メンテナンス明け

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

AtCoder Regular Contest 052 C: 高橋くんと不思議な道

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

square869120Contest #2 C: 何通りの分割方法がある?

問題 C: 何通りの分割方法がある? - square869120Contest #2 | AtCoder 解法 文字列が短いので、全ての部分文字列を数字にした時の値を計算しておく。メモ化再帰で 「substr(pos, length) で D 以下になる組み合わせの数」を求めれば良い。 コード #include <bits/stdc++.h></bits/stdc++.h>…

JAG 夏合宿 2015 Day2 G: Escape

問題 G: Escape - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 「入ったら頂点1に戻ることができずに確実に終了する点」を列挙する。逆に、これらの点以外の点は常に行き来できるので、その点数は確実に手に入る。あとは戻れない点に設定され…

JAG 夏合宿 2015 Day2 D: 真っ暗な部屋

問題 D: 真っ暗な部屋 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 最初 M 人の人が、それぞれの暗い部屋にいるとする。これらの人たちを全員明るい部屋に連れていくことを考える。各状態について、遷移の仕方がk通りある。全員が暗い部屋…

JAG 夏合宿 2015 Day2 B: 監獄

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

JAG 夏合宿 2015 Day2 A: 幾何問題を解こう

問題 A: 幾何問題を解こう - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 N^k 進数で表せる小数は N 進数で表せる。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; set<int> yakusu(int B) { set<int> p; int s = sqrt(B) + 10; for (i</int></int></bits/stdc++.h>…

AtCoder Regular Contest 050 D: Suffix Concat

問題 D: Suffix Concat - AtCoder Regular Contest 050 | AtCoder 解法 公式解説の通り。suffix array ではなく rolling hash でやった。 http://arc050.contest.atcoder.jp/data/arc/050/review.pdf コード #include <bits/stdc++.h> using namespace std; typedef long lo</bits/stdc++.h>…

東京大学プログラミングコンテスト2014 B: 交点

問題 B: 交点 - 東京大学プログラミングコンテスト2014 | AtCoder コード #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cin.tie(0); ios::sync_with_stdio(false); double X, Y; cin >> X >> Y; int cnt = 0; for (int x = floor(X) </bits/stdc++.h>…

AtCoder Regular Contest 018 C: 席替え

問題 C: 席替え - AtCoder Regular Contest 018 | AtCoder 解法 重要な制約として"p a%p!=0 の時、すべての生徒の成績は異なるため、各々が前から何行目に来るかが定まる。各生徒を自分がいるべき行まで移動させる。この時、列は移動させないため、重なる生…

AtCoder Beginner Contest 034 D: 食塩水

問題 abc034.contest.atcoder.jp コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out << '['; std::copy(v.begin(), v.end(), std::ostre</t></typename></bits/stdc++.h>…

AtCoder Regular Contest 033 C: データ構造

問題 C: データ構造 - AtCoder Regular Contest 033 | AtCoder 解法 @kenkoooo BITには二分探索というテクがあるそうです(受け売りhttps://t.co/VM8Y0DxGUz— CodeVS本戦通過ラインの境界 (@btk15049) 2016, 3月 8lower_bound() 搭載 Binary Indexed Tree (BI…

Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match (SA-IS)

kenkoooo.hatenablog.comhirokazu さんの SA-IS ライブラリをコピペさせてもらった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out </t></typename></bits/stdc++.h>…

Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match

問題 RUPC 2016 の時に @public_sate さんに教えてもらった。F: Longest Match - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder 解法 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostrea</typename></bits/stdc++.h>…

東京大学プログラミングコンテスト2013 I: 支配と友好

問題 I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder 解法 2回オイラーツアーするだけ。勝手に根が0だと思い込んで(しかもサンプルがそれで合う)メッチャハマった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; const</bits/stdc++.h>…

AtCoder Regular Contest 048 D: たこ焼き屋とQ人の高橋君

問題 D: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoder 解法 AtCoder Regular Contest 048 Submission #653842 - AtCoder Regular Contest 048 | AtCoder コード #include <bits/stdc++.h> using namespace std; typedef long long ll; struct HL { vec</bits/stdc++.h>…

AtCoder Regular Contest 048 C: 足の多い高橋君

問題 C: 足の多い高橋君 - AtCoder Regular Contest 048 | AtCoder 解法 AtCoder Regular Contest 048 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll mo</bits/stdc++.h>…

東京大学プログラミングコンテスト2014 E: 宝くじ

問題 E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder 解法 yosupo 先生のコードを写経した。Trie 木を作って、その桁で終わるくじの当選金と、その桁より後ろの桁で終わるくじの当選金の最高値をそれぞれのノードに持たせる。 コード #include <bits/stdc++.h></bits/stdc++.h>…

AtCoder Beginner Contest 014 D: 閉路

問題 D: 閉路 - AtCoder Beginner Contest 014 | AtCoder 解法 AtCoder Beginner Contest 014 解説LCA のライブラリを蟻本から写経。 コード #include <bits/stdc++.h> using namespace std; typedef signed long long ll; class LCA { private: LCA() {} vector<vector<int>> G; vector<vector<int></vector<int></vector<int></bits/stdc++.h>…

京都大学プログラミングコンテスト 2015 G: ケンドー

問題 G: ケンドー - 京都大学プログラミングコンテスト2015 | AtCoder 解法 Bは昇順でソートされているので後ろから見ていき、B[i]より大きいAの中で最も右側にあるものをB[i]と戦わせていけば良い。 i を回して、 Priority Queue に毎回 B[i] 以上のA を入…

AtCoder Beginner Contest 033 D: 三角形の分類

問題 abc033.contest.atcoder.jp 解法 ある一点 I を決め、その点を原点として他の点を仰角でソートする。I と他の一点 J を選んだ時に、角 KIJ が鋭角となるような点 K はしゃくとり法によって求められる。発想自体はこれに近い気がする↓ kenkoooo.hatenabl…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C: アメージングな文字列は、きみが作る!

問題 discovery2016-qual.contest.atcoder.jp 解法 DDPC 2016 予選 解説 from AtCoder Inc. www.slideshare.net解説スライドの通り、出来るだけ前の方をaで埋めて、置換しきれない分は辞書順最小の接尾辞を探している。接尾辞を探すのは Suffix Array ではな…

技術室奥プログラミングコンテスト G: おおきなかずを作った

問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…