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

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パワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じで…

丸くなってしまったtwitterアイコンを戻す方法

なんか、twitterとtweetdeckのアイコンが突然丸くなった。 四角を想定して作られたアイコンの四隅が切り取られるのはアレなので、CSSをいじって直した。 twitter社はなにを思ってこんなことをしてしまったんだろう・・・? 直し方 まず、CSSをカスタマイズで…

Google Code Jam 2017 Round 3

通過しました。 初のGCJ決勝進出です。 GCJは現時点での第一目標だったのでとても嬉しい。 次はTCOかぁ、きっつい。今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。 (けど謎の問題(sortアルゴリズムを推測せよとか、乱択とか…

最小費用流の負辺除去

つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくな…

ARC075 F 「Mirrored」 速い解法

ARC075Fとりあえず桁数を1~18まで全部試します。 例えば6桁なら、 D = fedcba - abcdef = 99999*(f-a) +9990*(e-b) + 900*(d-c)となるようなa~f(0≦a~f≦9, a≠0)の個数を数えれば良いです。 (f-a),(e-b),(d-c)みたいに端から決めていくんですが、 解説ではD…

ICPCのライブラリPDFの生成

ICPCのWFまたは多くのアジア地区予選では持ち込めるライブラリのページ数が決まっています。 また、PDFの右上にページ番号、左上に大学名を入れろという指定がついてきます。 PDF化するコマンド sublimeに印刷機能がなかったし、ページ番号と大学名を入れる…

ARC070 F「HonestOrUnkind」別解

HonestOrUnkind解いた。 面白かった、と思ってたけど想定解と違ったのでメモ。 想定解の方がシンプルで頭良い。正直者を1人特定するところが違った。まず人の組をN/2組作る。Nが奇数なら1人余る。 各組(x,y)について? x yを質問する。 'N'なら正嘘、嘘正、…

AGC013F「Two Faced Cards」別解(TLE)

Two Faced Cardsのコンテスト中に書いてた別解です。 O(N√N logN) なのでTLEして悲しいけど紹介しておきます。 (想定解も理解したけどadhocで面白かった) 下ごしらえ とりあえずC(とA,B)を0~Nに変換しておきます。 Ai<Biのカードは裏で使うメリットがな…

根付き木のハッシュ

りんごさんがちゃんとしたハッシュについての記事を書いてくれたのでそちらを推奨しておきます。 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい? multisetのハッシュ、0になりやすいなぁ…

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の2通りではそれぞれ衝突確率がかなり異なる。(少し考えれば当たり…

Xmas Contest 2016 I解説

I問題の解説です。

Xmas Contest 2016 F解説

F問題の解説です。