ARC116Eとxmas16Hの関係性

このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。 かなりびっくりしたので証明をしようとしてみたら出来ました。これら2つの問題はいずれも整数 N, K と N 頂点の木が与えられます。 (xmasの方は重み付きですが、重みなしの問…

ダイクストラ法のよくあるミスと落し方

ダイクストラ法、正しく書けてますか? ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。 この記事では、よくあるミスとその撃墜ケースを紹介していきます。この記…

秋分コンテスト 準備/裏話編

解説/講評編の続きです。コンテスト運営の裏話などを記録しておきます。 メンバー紹介 イカれたお誕生日メンバーを紹介するぜ! kagamiz KCSの開発者にして、伝説の「帰ってきたお誕生日コンテスト」のwriterの1人でもある。KCSは偉大。今回は「帰ってきた…

秋分コンテスト 解説/講評編

秋分コンテスト秋分コンテストを開催しました! スタッフ:japlj,kagamiz,snuke,tozangezanあの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います(?)ただ復活しただけでなく新たな進化を遂げ…

10日後にソートされる数列

何気なくしたネタツイートが不思議な展開になって面白かったので。 togetter.com

New Year Contest 2020

New Year Contest 2020に参加しました。 24時間26問で、出題される問題はノンジャンルなんでもありというお祭りみたいなコンテストです。2687.66点で優勝しました。 AM8時あたりの時点では結構2位に差があったけど、じわじわ追い上げられて結局sugimさんに6…

Xmas Contest 2019

今年もやりました。 コンテストページ:Xmas Contest 2019 - AtCoder 特設ページ:Xmas Contest 2019 たくさんのご参加ありがとうございました!

TTPC2019 Fの一般版

まず、なぜF - Road ConstructionにDAG制約があったのかに気付くのかなりむずい。 で、一般の有向グラフ版がO(V(V+E) log V)で解けて驚き。 結構見たことない感じのアルゴリズムで面白かった。togetter.comところで、TTPCの問題面白かった。 E,J,L,Nが特に好…

GCJ 2019 R3

BC2完で48位。 惜しかったような惜しくなかったような。 final行けなかったのは残念だけど、問題面白くて楽しかったので勝ち(とは)togetter.com

二部マッチングでTLEに苦しんだ話

opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。 そのときに得た知見をまとめておきます。 頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。

グリッドを白く塗る問題

togetter.com

タイルを永遠に置き続ける問題

CF後twitterで話してたのでまとめた。 楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。

DPの区間クエリ的なやつ

雑な記事。 競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com

木と計算量 後編 〜全方位木DP〜

前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…

木と計算量 前編 〜O(N^2)とO(NK)の木DP〜

この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました(嘘)最近、木上のアルゴリズムの面白い計算量解析が2つ話題になったのでまとめておきます。 予備知識 まず、二乗の木 DP - (iwi) { 反省します - TopCoder部 に…

最大マッチングを貪欲する問題の証明典型テク

ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である(つまりxもyも小さい…

Xmas Contest 2018 ギャラリー編

XmasContest終了後にA問題の解答画像をtwitterに上げてくれてる人がたくさんいて嬉しかったので、展覧会を開くことにしました。まずは画像一覧をどうぞ。 photos.app.goo.gl ダウンロードするとファイル名がユーザ名になってます。 これだけだと芸がないので…

Xmas Contest 2018

Xmas Contest 2018 今年も開催しました。 コンテスト密度の高い中、ご参加いただいた皆さまありがとうございました。 楽しんでいただけたでしょうか?(よろしければアンケートお願いします)今年の運営は4年連続のじゃっぷるさんと、2010~2014の運営の本家…

Mail.Ru Cup 2018 Round 1

久しぶりにCFに参加した。(開始10分後くらいに偶然TLを見て気づいた) A 問題文が難しい>< B まぁ。 C として、正しいかチェック。 D 累積xorをとって長さn+1の数列Xを作る。 Xから同じ数を2つ取ってきてその間を選ぶとxorが0になる。 つまり、とすると…

Knapsack And Queries - JAG夏合宿2018 day2 D

D - Knapsack And Queries 良く出来てるなぁ。queueをstack2つで実現できるっていう知る人ぞ知るテクがある。 純粋関数型データ構造界隈とかで有名らしい。どうやるかというと、 queueにpush 単にstack2にpushする queueからpop stack1が空でない:stack1か…

CodeForces #485 Div1 C AND Graph

Um_nik回のCが面白かったので。 あと、自分の解法が想定解と違ったっぽいので。 問題概要 ビットの二進数 が 個与えられる。 のとき頂点 に辺を張ったグラフの連結成分数を求めよ。制約 はdistinct

パソコン詳しくない系競プロ勢向け正規表現

この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の記事として書かれたものです。 上のリンク先にはリンクが張られていないので書いておきますが、競プロadvent calendarはもう1つあります。 昨日の記事 / 明日の記事(明日の記事がすでに…

Xmas Contest 2017 I問題 SAT Puzzle 解説

問題 | 解説まとめまずはコードです。 このコードでやっていることを解説します。まず、各マスには「黒」または「白」ではなく、「黒」または「(1,1)~(4,4)」を割り当てることにします。 ただし、(j,k)は「j番目の白マスグループのk番目のマス」を表すものと…

Xmas Contest 2017 H問題 Ango 解説

問題 | 解説まとめリアクティブ・encode/decode系の変わった問題。 部分点はmax(x)に関する関数にしてもよかったかなぁ。 部分点1 割と効率が悪くてもACできますがそこまで簡単ではないと思います。 例えばNが小さければフィボナッチ数列でいけますが、N=30…

Xmas Contest 2017 G問題 Maze 解説

問題 | 解説まとめ作問slackに最初に投稿した問題。 今年はこんな感じの問題にするぞという思いも込めて作りました。解法:ペイント等でゴールのラインに縦線を引き、バケツツールで塗りつぶすと・・・答え:ACEFGHNPQSYZ ペイントってBFSができるんですねぇ…

Xmas Contest 2017 F問題 Tree Disassembly 解説

問題 | 解説まとめ1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。 手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。 1~5 1は…

Xmas Contest 2017 E問題 String Problem 解説

問題 | 解説まとめこのセット随一の普通の問題です。 少し言い換えると、Sから'A'をいくつか削除し、Tから'B'をいくつか削除することによってSもTもUにすることができるような文字列Uが存在するかを判定すれば良いです。 「dp[i][j] = S[0]~S[i]とT[0]~T[i]…

Xmas Contest 2017

Xmas Contest 2017 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。(そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です) あと、アンケートに回答してくださったみなさまありがとう…

IOI2017

IOI2017を観戦しました。師匠が圧倒的な1位を取り、日本チーム自体も金3銀1と過去最高成績で激アツでした。 金3も1,4,5位で凄すぎる。 おめでとう&お疲れ様! 本番から1時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か…

KMPのK

snuke.hatenablog.com上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。 KMPは、上の記事で紹介したMP(Morris-Pratt)にKnuthパワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じで…