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

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

log4j2.xmlの置き場所

Gradle環境ではlog4j2の設定ファイルlog4j2.xmlはsrc/main/resourcesに置くっぽい。

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 …

2016年を振り返って2017年の目標を決める

2016年の良かったこと ジムに行って筋トレした Kaggleに参加した ICDMで発表した ルンバを買った ガルパンを観た Reactをやった 会社を辞めなかった 2016年の良くなかったこと 競プロが疎かになった 血糖値 コレステロール値 2017年の目標 競プロを頑張る AO…

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

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

退学を支える技術

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

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…

生徒会長 角谷杏

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

ガールズ&パンツァー 9話

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

レオポンさんチーム車長 ナカジマ

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

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

リクルートコミュニケーションズ (RCO) におけるプログラミングコンテストの活用について

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

C++ (gcc) で 128 ビット整数を使う

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

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 番目の文字列を返してください。 解法 括弧列に対する様々な先入観から良い文…

RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 3

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

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…

RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 2

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

RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 1

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

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 台のパソコ…

Jupyter Notebook 上で autopep8 のフォーマッタを実行できる nbextension を公開しました

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

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 Medium: FromToDivisible

問題 Div 2 Hard の制約きついバージョンらしいのですが、Div 2 で書いたコードがそのまま通ります。kenkoooo.hatenablog.com コード import java.util.ArrayDeque; import java.util.ArrayList; public class FromToDivisible { // 最大公約数 private stat…

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…