AtCoder

ARC082 F - Sandglass

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_d 解法 解説動画の通りにやった。最初に a 入っている時の t 秒後の砂の量は以下のように書ける。この をシミュレーションしていけば良い。 コード use std::io; use std::str; use std::usize; …

ARC082 E - ConvexScore

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_c 解法 解説の通りにやった。 の意味するところを考える。これは凸包が S となるような部分集合の数である。よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいの…

ARC080 E - Young Maids

Rust の練習 問題 http://arc080.contest.atcoder.jp/tasks/arc080_c 解法 逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i…

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