AtCoder

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

問題 C - Cheating Nim 解法 Grundy 数の原理から、「各 もしくは の XOR の値を 0 にすることが出来るか?出来るなら を使った回数は何回か?」という問題に言い換えることができます。ここで、ある i について を使うと XOR の値 x は になります。すなわ…

「みんなのプロコン2018」 D - XOR XorY

問題 D - XOR XorY 解法 解説を読んでも分からなかったので 「みんなのプロコン 2018」: D - XOR XorY · うさぎ小屋 を参考にした。 または ということは なので とすると となる。以後、 を満たす を数え上げることにする。 i=j でも条件を満たすため より …

SoundHound Inc. Programming Contest 2018 (春) D - 建物

問題 D - 建物 解法 (i, j) から (i, k) に移動して (i+1, k) に移動する経路 (i, j) => (i+1, k) を考える。このとき、 (i, j-1) => (i+1, k) よりも多くの報酬が得られることに留意する。次に (i+1, k+1) に移動する経路を考える。このとき (i, j-1) => (i…

SoundHound Inc. Programming Contest 2018 (春) C - 広告

問題 C: 広告 - SoundHound Inc. Programming Contest 2018 (春) | AtCoder 解法 グリッドグラフでの最大安定集合を求めたい。最大安定集合は最小点被覆の補集合なので、最小点被覆問題を解く。二部グラフでは最小点被覆問題は最大マッチング問題の双対なの…

並列二分探索(解説なしバージョン)

adventar.org並列二分探索、名前からして難しそうな感じがしていたが、特に難しいわけではなかった。 並列二分探索 個人的には並列という名前は正しくない気がします。普通の二分探索は次の通り。 let mut ng = 0; let mut ok = m; for _ in 0..30 { let med…

CODE FESTIVAL 2017 Final E - Combination Lock

問題 E - Combination Lock 解法 方針としては、 区間を整理しやすいように文字列の長さを偶数にする。 区間の整理をめっちゃ頑張る 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO 文字列の長さを偶数にす…

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…