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

この記事は退学 Advent Calendar 2016 - Adventarの22日目の記事です。アドベントカレンダーに投稿されている記事を見ると、退学した人間の自分語りか退学する予定の自分語りの記事しかないので、ここでは少し趣向を変えて、退学の技術的なノウハウを共有し…

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

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

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

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

角谷杏は生徒会長という役職だが、大洗女子学園が学園艦であるという性質上、生徒会長というのも一高校の役職というよりも、地域の支配者という感じがする。OVAでもそのへんに言及があった気がする。そんな会長の活躍を振り返っていきたい。 学校の代表とし…

ガルパン Advent Calendar 2016 - Adventarの記事として書かれました。ガルパン9話「絶体絶命です！」で泣いた視聴者は多いと思います。ご多分に漏れず、私も毎回泣くので、それについて書きます。 「無謀だったかもしれないけどさあ、あと1年、泣いて学校生…

ガルパン Advent Calendar 2016 - Adventarの記事として書かれました。出典: http://girls-und-panzer.jp/chara_nakajima.htmlナカジマといえば、終盤の決勝戦からポルシェティーガーとともに参戦した自動車部のレオポンさんチームの車長ですが、自動車部の…

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

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

この記事は Recruit Engineers Advent Calendar 2016 の3日目の記事です。www.adventar.org リクルートコミュニケーションズ (RCO) とは？ まずはこのサイトを見てください。www.rco.recruit.co.jpサイトトップに表示される仕事中の（はずの）社員の画面に "…

128 ビット整数を使いたいけど boost が入ってないので多倍長整数が使いづらいという環境で __int128 なるものの存在を知ったのでメモ。自前でパースとか出力とかを用意するのでやや面倒だが、多倍長整数ライブラリを持っていなくても安心。 #include <bits/stdc++.h> using</bits/stdc++.h>…

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

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

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

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

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

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

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

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

前回のページ kenkoooo.hatenablog.com内容は大体かぶってます。 プッシュ再ラベルアルゴリズム 今までは頂点にフローを溜め込むことができない条件のみを考えてきた。頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。 これを緩和し…

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

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

先週のページ kenkoooo.hatenablog.com 少し被りがあります。 先週のまとめ G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。 定理 26.6 最大フロー最小カットの定理 fはGの最大フローである。 残余ネットワーク Gf は増加可能経…

フローネットワーク 各辺 が、容量 を持つ有向グラフである。入り口 s と出口 t が設定されている。非負の値を取る量 を頂点 u から頂点 v へのフローと呼ぶ。フローは以下の 2 条件を満たす。 容量制限: 全ての に対して、 でなければならない。 フロー保存…

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

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

Jupyter autopep8 github.com これは何 Jupyter Notebook の Cell 内で使えるコードフォーマッタです。コード編集中に Ctrl+L を押すと autopep8 を使ってコードが整形されます。 インストール方法 pip install autopep8 jupyter nbextension install https:…