とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

高速化できる最小費用流のよくあるからくり / グリッド上の最大流問題

この記事は Competitive Programming (1) Advent Calendar 2019 - Adventar の25日目の記事です. 24日目はbeet_aizuさんの記事で,Online Judge Verify Helper のススメ - beet's soilでした.この記事ですが,気合を入れすぎたので15ページもあります. そ…

modint構造体の工夫

(注 (2021/1/31) : この記事はとても古く、なおかつもっといい実装が考えられます。さらに言えば、AtCoderではac-libraryが整備されている現在では価値は無いと思われます) はじめに プログラミングコンテストの問題では、答えをある値で割ったあまりを求め…

競技プログラミング再入門 環境構築編

はじめに 私は競技プログラミングでは、5年くらい前に頑張っていた時期がありましたが、最近は気が向いたらコンテストに出るくらいでした。ところが、さすがにそれだと問題が生じてきました。 昔整備したライブラリは滅茶苦茶なまま。何がどこに行ったかわか…

Code Festival 2017 J (Tree MST) と 距離空間上のボロノイ図

春ですね。今回はCode Festival 2017のJ問題に対する面白い着眼点を紹介します。問題はこちら -> J: Tree MST - CODE FESTIVAL 2017 Final | AtCoder 1900点!ボロノイ図の説明はこちら -> ボロノイ図 - Wikipedia想定読者層 : MSTを知っている人 Kruskal法の…

Project Selection (燃やす埋める) 周りの話についてもう少し考えた

Competitive Programming Advent Calendar 2017 - Adventar アドベントカレンダー最終日です。 先月はこの過激記事をご覧になった方も多いのではないでしょうか。 : 『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめこれについてもう少し…

第2回ドワンゴからの挑戦状「花火」に対するシンプルな解法と最小費用流の双対

競技プログラミングアドベントカレンダー2017(その1)の二日目の記事です。 adventar.org この記事では花火に対するシンプルな解法を説明します。これは最小費用流の双対問題を用いて説明できますので、そういったことに触れつつ解説します。本文は次のPDFに…

TCO2017 Semifinal2 500 RatingProgressAward

(UPD 12/24) 説明に誤りがあったので修正。前回の続きです。前回はいろはちゃんの疑問に答えたつもりでしたが、聞いてみたところ違った問題のことを指していて、表題の問題だったようです。 link :TopCoder Statistics - Problem Statement 今回もProjectSel…

AGC 016 C (+/- Rectangle) と Farkas' lemma

AGC 016 Cを考えていると気づいたことがあるので、紹介します。まず、AGCの問題文 : C: +/- Rectangle - AtCoder Grand Contest 016 | AtCoder この問題は要するに、局所的には負にしつつ、全体は正にする、というような気分のような問題です。 私も結局よく…

JOI春合宿2017 Day1 手持ち花火(Sparklers) の別解と上位問題の解法

こんにちは。今回はタイトル通りのことについて気づいたので紹介していこうと思います。 一応注意をしておくとネタバレを含むので、見たくない人は見ないでください。 また、この記事を書くにあたってsnukeさんに多大な助言をいただきました。この場で感謝し…

競プロとLP双対まわりの話で最近知ったこと

こんにちは。tokoharuです。これは Competitive Programming (その2) Advent Calendar 2016 - Adventar の12/7の記事です。問題も稀にしか確認しなくなりましたが最近得た知見をここで報告・宣伝しておきます。少々マニアックな記事です。 概要 私のtwitte…

AOJ0304がコーナーケースを入れ損ねてるっぽい話

競プロとLPまわりの記事 : github.com をupdateしたくなったので色々整理しているとこういう話になっているっぽいことを確認しました。まず、次のふたつのACされたコードを用意します。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1197971#1と h…

2015 JAG Regional J : Longest Shortest Path

原案出しました。 この問題は考察が非人道的ですが、壁を突破した後にたどり着く解法は美しいものです。 今回は感想や小話を書いたり、中の人の議論ページにあるのをちょっと編集して貼り付けます。 感想や小話 解法を知りたい人はもう少し下を眺めてくださ…

とこはるの問題

今までに作った(or原案に携わったレベルの)問題と簡単なコメント 2012年 かけざん http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2424 簡単な問題を作りたかった ほそながいところ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2…

2013アジア地区大会振り返り

おさけーさんによる別視点 http://www.osak.jp/diary/diary_201312.html#20131205 まとめ(1/8 追記) binding.pryの一員としてICPCアジア地区大会の会津大会(日本大会)およびDanang大会(ベトナム大会)に参加してきた。会津大会で国内大学としては、東大に次ぐ…

DP俯瞰?

他のDPの記事 http://d.hatena.ne.jp/Tayama/20111210/1323502092 http://d.hatena.ne.jp/komiyam/20111212/1323615687Typical DP Contest http://tdpc.contest.atcoder.jp/ 基本(1) フィボナッチ数列 一次元累和 パスカルの三角形 多次元累和 二次元はセル(…

GCJ 2013 Qual

http://snuke.hatenablog.com/entry/2013/04/14/164938 ここにsnuke神さんが解説書いてくれています。 C 制約をうまく使って解を全列挙して、クエリが来るたび二分探索をすることを考えます (制約とは、すべての桁の(数字)^2の総和以下はPracticeで通したコ…

xmas contest 2012 G問題について

ネット環境がよい場所に来たので書きます。 日本語が合っているかはよくわかりませんがどうぞ。 問題概要 平面上の格子点にn個の点があって、凸5角形が何個作れるか。 ただし任意の三点は同一直線上に存在しない n 解法 求めるのは、5点選んでそれの凸包が5…

2012年JAG夏合宿Day2の作問について

この記事について この記事はhttp://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9 Competitive Programming Advent Calendar Div2012の12/18の記事です。 コンテストの概要 9/15(土)(11:00-16:00)の http://judge.u-aizu.ac.jp/onlinejudge/cont…

チェックした問題

http://d.hatena.ne.jp/anta1/20120730/1343650604 リスペクトanta1さん今まで見た問題は確実に無理だし、昔見た系は使わないかも 最近もっぱらtopcoder系のまとめにしか使っていない ◎ 初見で解けた ○f 自分で解いたが、Practice System TestでFailedしてRe…

このページは

tokoharu_sakuraが考えたことのまとめみたいなのを置くページです。 内容は競技プログラミング中心になるかもしれません。 使い勝手が悪ければなかったことにします