けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

データ構造

AtCoder AGC 005 B - Minimum Sum (400 点)

教育的な典型問題! 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…

Educational Codeforces 62 C - Playlist (R1600)

楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…

AOJ 2931 括弧を語る数 (RUPC 2019 day3-B)

こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい!!!!!! ということで教育的な楽しい問題!!! 問題へのリンク 問題概要 整合するカッコ列 があって、 から以下のように定義される長さ の順列 が与えれる: i …

AtCoder ABC 120 C - Unification (300 点)

久しぶりのカッコ列の整合判定問題!!! カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

全国統一プログラミング王決定戦 本選 D - Deforestation (500 点)

遅延評価セグメントツリーで殴った...速度重視ならそれでいい気もする 問題へのリンク 問題概要 本の竹があって、時刻 0 においてすべての竹の高さは 0 である。それぞれの竹は時刻が 1 経過するごとに高さが 1 増える。 竹を伐採するイベントが 回予定され…

AtCoder ABC 064 D - Insertion (400 点)

教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…

AtCoder ARC 038 D - 有向グラフと数

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う スタート時には駒を頂点 1 に置く 各プレイ…

JOI 2014 予選 F - 財宝 (AOJ 0613)

スライド最小値の練習 問題へのリンク 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテムを取ることはできず、2 人ともとらな…

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 2891 な◯りカット (AUPC 2018 day3 C)

なもりなもり。サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことなん。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに最小何個の辺を…

AOJ 2890 ピボット (AUPC 2018 day3 B)

ぐへへへ...ლ(´ڡ`ლ)グェッヘッヘッ 勉強になった。 問題へのリンク 問題概要 1 〜N の順列 a1, a2, ..., aN が与えられる。 この順列に対して Q 個のクエリが順に与えられる。i 番目のクエリでは次の操作をしなければならない: 値 q が与えられる。順列 {a1, a2,…,…

COLOCON 2018 Final C - スペースエクスプローラー高橋君 (600 点)

Convex Hull Trick の練習に。DP ではないけど、DP 高速化でよくやる Convex Hull Trick の構造そのものを試せる問題。Convex Hull Trick についての詳しい解説は Convex-Hull Trick (satanic さん) がとてもわかりやすい! 問題へのリンク 問題概要 長さ の…

CODE THANKS FESTIVAL 2017 H - Union Sets (600 点)

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみたん。 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになった…

AtCoder AGC 002 D - Stamp Rally (1000 点)

部分永続 Union-Find 木の練習をした。 問題概要 (AGC 002 D) N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値…

JOI 2011 本選 E - JOI 国のお祭り事情 (AOJ 0575)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん!!! 問題へのリンク 問題概要 制約 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(in</int></algorithm></map></queue></vector></iostream>…

Codechef Product on the segment by modulo

Disjoint Sparse Table の勉強をした!!! 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…

AtCoder ARC 101 D - Median of Medians (700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなくて後半の議…

AOJ 2842 たい焼きマスターと食べ盛り

二次元 BIT ライブラリ の verify をした 問題へのリンク 問題概要 H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの…

NJPC 2017 H - 白黒ツリー

オイラーツアー練習第二弾。 そして、これにて一応、ツリーの辺に重みがある場合にも対応できることとなった。 問題へのリンク 問題概要 頂点 1 を根とした頂点数 N の根付き木が与えられる。初期状態では各頂点に 0 か 1 の値が割り当てられている。以下の …

天下一 2015 本戦 F - 根付き木のみさわさん

オイラーツアーの練習に解いたけど、発想も面白いん!!! 問題へのリンク 問題概要 頂点 1 を根とする、頂点数 N の根付き木がある。以下の Q 個のクエリに答えよ: M 個の頂点 v1, v2, ..., vM に実をつける。「その頂点を根とする部分木に含まれる実の個数…

AOJ 2427 ほそながいところ

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。

2018 codeFlyer 本選 C - 部分文字列と括弧 (500 点)

超定番の「対応がとれている」カッコ列を題材にした問題なん。色んな出題がやり尽くされてそうな中、まだこんなのが残っていたのんな!! ある文字列が与えられたときにそれが正しいカッコ列かどうか判定するのは、AGC 005 A - STring の方法でできるん。 今…

AtCoder ARC 008 D - タコヤキオイシクナール

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…