解説放送で話したのをメモしておきます。 （ABC231の解説放送のスクショ）関連記事：最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。 かなりびっくりしたので証明をしようとしてみたら出来ました。これら２つの問題はいずれも整数 N, K と N 頂点の木が与えられます。 （xmasの方は重み付きですが、重みなしの問…
ダイクストラ法、正しく書けてますか？ ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。 この記事では、よくあるミスとその撃墜ケースを紹介していきます。この記…
解説/講評編の続きです。コンテスト運営の裏話などを記録しておきます。 メンバー紹介 イカれたお誕生日メンバーを紹介するぜ！ kagamiz KCSの開発者にして、伝説の「帰ってきたお誕生日コンテスト」のwriterの１人でもある。KCSは偉大。今回は「帰ってきた…
秋分コンテスト秋分コンテストを開催しました！ スタッフ：japlj,kagamiz,snuke,tozangezanあの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います（？）ただ復活しただけでなく新たな進化を遂げ…
何気なくしたネタツイートが不思議な展開になって面白かったので。 togetter.com
New Year Contest 2020に参加しました。 24時間26問で、出題される問題はノンジャンルなんでもありというお祭りみたいなコンテストです。2687.66点で優勝しました。 AM8時あたりの時点では結構２位に差があったけど、じわじわ追い上げられて結局sugimさんに6…
今年もやりました。 コンテストページ：Xmas Contest 2019 - AtCoder 特設ページ：Xmas Contest 2019 たくさんのご参加ありがとうございました！
まず、なぜF - Road ConstructionにDAG制約があったのかに気付くのかなりむずい。 で、一般の有向グラフ版がO(V(V+E) log V)で解けて驚き。 結構見たことない感じのアルゴリズムで面白かった。togetter.comところで、TTPCの問題面白かった。 E,J,L,Nが特に好…
BC２完で48位。 惜しかったような惜しくなかったような。 final行けなかったのは残念だけど、問題面白くて楽しかったので勝ち（とは）togetter.com
opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。 そのときに得た知見をまとめておきます。 頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。
togetter.com
CF後twitterで話してたのでまとめた。 楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。
雑な記事。 競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com
前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…
この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘）最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https:…
ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である（つまりxもyも小さい…
XmasContest終了後にA問題の解答画像をtwitterに上げてくれてる人がたくさんいて嬉しかったので、展覧会を開くことにしました。まずは画像一覧をどうぞ。 photos.app.goo.gl ダウンロードするとファイル名がユーザ名になってます。 これだけだと芸がないので…
Xmas Contest 2018 今年も開催しました。 コンテスト密度の高い中、ご参加いただいた皆さまありがとうございました。 楽しんでいただけたでしょうか？（よろしければアンケートお願いします）今年の運営は４年連続のじゃっぷるさんと、2010~2014の運営の本家…
久しぶりにCFに参加した。（開始10分後くらいに偶然TLを見て気づいた） A 問題文が難しい＞＜ B まぁ。 C として、正しいかチェック。 D 累積xorをとって長さn+1の数列Xを作る。 Xから同じ数を２つ取ってきてその間を選ぶとxorが0になる。 つまり、とすると…
D - Knapsack And Queries 良く出来てるなぁ。queueをstack２つで実現できるっていう知る人ぞ知るテクがある。 純粋関数型データ構造界隈とかで有名らしい。どうやるかというと、 queueにpush 単にstack2にpushする queueからpop stack1が空でない：stack1か…
Um_nik回のCが面白かったので。 あと、自分の解法が想定解と違ったっぽいので。 問題概要 ビットの二進数 が 個与えられる。 のとき頂点 に辺を張ったグラフの連結成分数を求めよ。制約 はdistinct
この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の記事として書かれたものです。 上のリンク先にはリンクが張られていないので書いておきますが、競プロadvent calendarはもう１つあります。 昨日の記事 / 明日の記事（明日の記事がすでに…
問題 | 解説まとめまずはコードです。 このコードでやっていることを解説します。まず、各マスには「黒」または「白」ではなく、「黒」または「(1,1)~(4,4)」を割り当てることにします。 ただし、(j,k)は「j番目の白マスグループのk番目のマス」を表すものと…
問題 | 解説まとめリアクティブ・encode/decode系の変わった問題。 部分点はmax(x)に関する関数にしてもよかったかなぁ。 部分点１ 割と効率が悪くてもACできますがそこまで簡単ではないと思います。 例えばNが小さければフィボナッチ数列でいけますが、N=30…
問題 | 解説まとめ作問slackに最初に投稿した問題。 今年はこんな感じの問題にするぞという思いも込めて作りました。解法：ペイント等でゴールのラインに縦線を引き、バケツツールで塗りつぶすと・・・答え：ACEFGHNPQSYZ ペイントってBFSができるんですねぇ…
問題 | 解説まとめ1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。 手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。 1~5 1は…
問題 | 解説まとめこのセット随一の普通の問題です。 少し言い換えると、Sから'A'をいくつか削除し、Tから'B'をいくつか削除することによってSもTもUにすることができるような文字列Uが存在するかを判定すれば良いです。 「dp[i][j] = S[0]~S[i]とT[0]~T[i]…
Xmas Contest 2017 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。（そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です） あと、アンケートに回答してくださったみなさまありがとう…
IOI2017を観戦しました。師匠が圧倒的な１位を取り、日本チーム自体も金３銀１と過去最高成績で激アツでした。 金３も１，４，５位で凄すぎる。 おめでとう＆お疲れ様！ 本番から１時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か…
