競技プログラミング

CS Academy Round #14 Subarrays Xor Sum

問題 https://csacademy.com/contest/round-14/task/subarrays-xor-sum/ 解法 eha くんに解説をしてもらってようやく理解した。各ビットごとに独立なので、ビットごとに分ける。0と1のみの数列の長さ k 以下の数列の xor の合計値をとりたい。 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…

CS Academy Round #29: Root Change

問題 https://csacademy.com/contest/round-29/task/root-change/ツリーの各頂点 i について、 i を根とした時に切断してもツリーの高さが変化しない辺の数を出力してください。 解法 editorial のコード通りです。いわゆる全方位木dpと呼ばれる手法です。 …

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…

Codeforces Round #411 (Div. 1) C. Ice cream coloring

問題 http://codeforces.com/contest/804/problem/Cn 頂点のツリー T と m 種類のアイスクリームがあります。T の各頂点はアイスクリームの集合をもっています。あるアイスクリーム i をもつ頂点同士は、連結なサブグラフになっています。m 頂点の無向重みな…

TopCoder SRM 710 Div 1 Easy: ReverseMancala

解法 操作Aと操作Bは完全に対称な操作であることが分かる。操作Aをしまくって1箇所に集め、操作Bをしまくって復元すれば良い。 コード import java.util.ArrayList; import java.util.Collections; public class ReverseMancala { private int N; private Ar…

Codeforces Round #402 (Div. 2) E. Bitwise Formula

# 問題http://codeforces.com/contest/779/problem/EMビットからなる変数がN個与えられます。各変数は、代入か、異なる2つの変数の AND OR XOR のいずれかの結果です。すべての変数の合計値が最小になるような変数 '?' と最大になるような変数 '?' を求めて…

Codeforces Round #397 E. Tree Folding

問題 Problem - E - Codeforcesツリーがあって、ある頂点から同じ長さの枝が2本出ている時、そのうち1本を取り除くことが出来ます。この操作を繰り返してツリーを直線に出来る場合、その最小の長さを出力してください。 解法 葉から登っていき、自分より下方…

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について全て足し合わせる…

8VC Venture Cup 2017 - Elimination Round F. PolandBall and Gifts

問題 http://codeforces.com/contest/755/problem/Fプレゼント交換をします。iさんはp[i]さんにプレゼントを渡します。複数の人が同じ人にプレゼントを渡すことはありません。K人がプレゼントを忘れました。プレゼントを忘れた人はプレゼントを受け取れませ…

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…

Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) D. Felicity's Big Secret Revealed

問題 http://codeforces.com/contest/757/problem/D0と1からなるn文字の文字列が与えられます。この文字列の好きな位置(先頭や末尾も含むN+1個)に仕切りを入れることができます。仕切りはいくつ入れても構いませんが、同じ位置に2個以上入れることはできま…

Codeforces Round #390 (Div. 2) D. Fedor and coupons

問題 http://codeforces.com/contest/754/problem/D[l, r] のような範囲の組が N 個あります。このうちK個を選び、K個すべてが重なる範囲を最大にしたいです。最大値と、その時選ぶ範囲のidを出力してください。 解法 非想定解法っぽい Treap コード import …

Push-Relabel による最大フローアルゴリズム

はじめに この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの23日目の記事として書かれました。最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフロ…

2016-2017 ACM-ICPC Southwestern European Regional F Performance Review

問題 Attachments - 2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) - Codeforces根つき木があって、各頂点にはランクとコストが定められています。各頂点について、その頂点の子孫であり、かつ、その頂点のランク未…

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

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

Codeforces Round #385 (Div. 1) B. Hongcow's Game

問題 http://codeforces.com/contest/744/problem/Bn x n の行列があります。行列の要素は全て非負整数で、対角成分はすべて0です。この行列に対して、n以下の自然数の集合Sをクエリとして投げると、各行についてとなる x 列目の要素のうち最小のものを返し…

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パスの最も大きい辺を切るのが最適なので、各クエリに対…

Codeforces Round #381 (Div. 2) D. Alyona and a tree

問題 http://codeforces.com/contest/740/problem/Dツリーがあり、頂点1が根です。各頂点 u には数字が書き込まれています。各頂点 v について、v の部分木に含まれ、かつ を満たす頂点uの数を出力してください。 解法 DFS で辺の重みを BIT に持ちながら潜…

Codeforces Round #381 (Div. 2) E. Alyona and towers

問題 http://codeforces.com/contest/740/problem/EN 個の非負の数列{a}があります。クエリが M 個あり、各クエリでは、l 番目から r 番目までの数字にそれぞれ v を足し、数列に含まれる最大の hill の幅を答えてください。 ただし、hill とはを満たす部分…

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…

RUPC 2016 Day2 L: String in String

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=L 解法 kenkoooo.hatenablog.com コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; impor…

AOJ 2644 Longest Match

問題 Longest Match | Aizu Online Judge 解法 SuffixArray を作ると、Sに含まれる a の SuffixArray 上での lower_bound と upper_bound を求めることができます。その中で最も前のものを求めたいですが、これはRMQで持っておけば良いです。b については上…

Codeforces Round #379 (Div. 2) F. Anton and School

問題 http://codeforces.com/contest/734/problem/F 解法 Fはb_i+c_iを足すとなんとa_i*n+(sum a_j)になりそこからがんばる。あと検証もちゃんとする— 有為 (@uwitenpen) 2016年11月15日 コード import java.io.IOException; import java.io.InputStream; im…

Codeforces Round #379 (Div. 2) E. Anton and Tree

問題 http://codeforces.com/problemset/problem/734/EN頂点のツリーがあり、各頂点は白か黒で塗られています。1回の操作で同じ色の連結成分の色を全て塗り替えることができます。ツリーを全て同じ色にするための最小の操作回数を求めてください。 解法 連結…

Codeforces Round #364 (Div. 2) E. Connecting Universities

問題 http://codeforces.com/contest/701/problem/EN 頂点のツリー状に 2K 個の大学があります。これらの大学を K このペアに分割します。ペアとなっている大学間の距離の合計が最大となるようにペアを作るとき、その最大値を答えてください。 解法 辺 (v, p…

TopCoder SRM 702 Div1 Medium: RepeatedStrings

問題 "()" は良い文字列です。 S を良い文字列としたとき、"(SSS...S)" は良い文字列です。 文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。 解法 括弧列に対する様々な先入観から良い文…

Codeforces Round #378 (Div. 2) E. Sleep in Class

問題 http://codeforces.com/contest/733/problem/EN 階建ての建物の中にいます。各階には 'U' または 'D' の文字が書かれています。 i 階にいて U と書かれているときは i+1 階へ、D と書かれているときは i-1 階へ移動します。移動すると、直前にいた階の…

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…

Codeforces Round #377 (Div. 2) F. Tourist Reform

問題 http://codeforces.com/contest/732/problem/FN 頂点 M 辺の連結な無向グラフが与えられます。すべての辺の向きをそれぞれどちらか 1 方向に限定した時に頂点 i から到達可能な頂点の数を mi とします。mi の最小値を最大化するとき、その値と、その時…

Codeforces Round #377 (Div. 2) E. Sockets

問題 Problem - 732E - CodeforcesN 台のパソコンがあり、パソコン i の消費電力は Pi です。ソケットが M 個あり、ソケット j の供給電力は Sj です、消費電力と供給電力が等しいとき、パソコンをソケットに接続できます。1 つのソケットには 1 台のパソコ…

Intel Code Challenge Elimination Round D. Generating Sets

問題 Problem - D - Codeforces相異なる自然数を N 個もった集合 X があります。X の各要素 に対して、以下の操作を行うことができます。 を X から取り除き、 を X に加える。 を X から取り除き、 を X に加える。 集合 X に何回か操作を加えて Y にするこ…

HackerEarth July Circuits : Benny and the Universe

問題 https://www.hackerearth.com/july-circuits/algorithm/benny-and-the-universe/N 個の整数が与えられます。Q 個の整数 X が与えられるので、各Xがこれらの整数の線形和(係数は非負整数)でできるかどうか判定してください。 解法 ダイクストラします…

Codeforces Round #364 (Div. 2) D. As Fast As Possible

問題 Problem - D - CodeforcesN 人の子供がいて、一度に K 人乗れるバスがあります。子供の速度が v1 , バスの速度が v2 である時、N 人全員が L 以上進むのに必要な時間を求めてください。 解法 全員が T だけバスに乗るとして、これを二分探索で求めます…

Codeforces Round #363 (Div. 2) DE

復習シリーズ D. Fix a Tree Problem - D - CodeforcesN 頂点の有向グラフがあり、頂点 i から頂点 a[i] に向かう辺があります。できるだけ少ない辺を張り替えてある1つの頂点に向かう有向木にしてください。 解法 連結成分内に閉路が含まれているとき、閉路…

ACPC2016 Day2 J : Char Swap

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=J 解法 J : 解説 from Takumi Yamashita www.slideshare.net元の文字列がアルファベット を 個含むとき、前半と後半に寄せて、 を 個ずつ含むようにします。(解説スライ…

ACPC2016 Day2 H : Hogemon Get

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=H 解法 ボールを獲得するたびに、(ボールを獲得した時刻, ボールを獲得した場所, 直前にボールを獲得した場所, 直前にボールを獲得した場所が再度利用可能になるまでの時…

TopCoder SRM 699 Div1 Easy: OthersXor

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

TopCoder SRM 699 Div2 Hard: FromToDivisibleDiv2

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

Codeforces Round #373 (Div. 1) C. Sasha and Array

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

Codeforces Round #373 (Div. 2) C. Efim and Strange Grade

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

ACPC2016 Day2 G : Star

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

ACPC Day2 F : Curling Puzzle

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

ACPC Day2 D : One-Time Path

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

Codeforces Round #372 (Div. 2) D. Complete The Graph

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

CS Academy Round #12 Prefix Suffix Counting

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

天下一プログラマーコンテスト2016本戦 C - たんごたくさん

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