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

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

データ構造

AtCoder ABC 158 D - String Formation (400 点)

先頭と末尾の両方から push できるデータ構造といえば、deque!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1: 文字列 を左右反転する type 2: 値 F と文字 c が与えられ、F = 1 のと…

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AtCoder ARC 033 C - データ構造

BinaryTrie を確認した!!! 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…

AtCoder ABC 154 C - Distinct or Not (300 点)

こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う std::set や std::map などの連想配列を用いて管理する ソートしてソート順に処理していく 問題へのリンク 問題概要 個の整数 が与えられる。この整数列のどの 2 つの要素も…

CADDi 2018 E - Negative Doubling (800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…

Educational Codeforces Round 81 E. Permutation Separation (R2200)

これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …

AtCoder ABC 153 F - Silver Fox vs Monster (600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

Codeforces Round #609 (Div. 1) C. K Integers (R2300)

とてもこどふぉっぽい問題だと思った!!!こういうのを得意になるぞー!!! 問題へのリンク 問題概要 の順列が与えられる。各 に対して、以下の問いに答えよ。 順列の隣り合う 2 要素を swap して、順列のどこかの場所で がこの順に連続で並んでいる状態に…

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…

AtCoder ARC 099 F - Eating Symbols Hard (1200 点)

楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …

AtCoder ARC 101 F - Robots and Exits (900 点)

またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…

Educational Codeforces Round 73 F. Choose a Square (R2500)

「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする!!! 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…

AtCoder ABC 141 D - Powerful Discount Tickets (400 点)

問題を読み替えつつ Greedy!!! 問題へのリンク 問題概要 個の品物があって、それぞれ 円で売られている。今 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。 円の品物を買う際に 枚の割引券を使った場合、その品物を 円で…

AtCoder ARC 065 D - 連結 / Connectivity (400 点)

Union-Find 木に関するすごくいい感じの問題 問題へのリンク 問題概要 個の駅がある。 本の道路と 本の鉄道があって、それぞれ双方向に駅ペアを結んでいる。 各駅に対して、その駅から道路のみを使っていくことができて、かつ鉄道のみを使ってもいくことがで…

AtCoder ARC 065 E - へんなコンパス / Manhattan Compass (900 点)

めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…

AtCoder ABC 128 E - Roadwork (500 点)

これと似てる!!! これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […

AtCoder ABC 127 F - Absolute Minima (600 点)

超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

AtCoder ABC 126 E - 1 or 2 (500 点)

これまた Union-Find を用いる教育的問題!!!!! 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

AtCoder ABC 116 D - Various Sushi (400 点)

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった! 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

AtCoder ARC 074 D - 3N Numbers (500 点)

昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…

Codeforces 552 DIV3 E. Two Teams (R1800)

超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…

GCJ 2019 Round 1A C - Alien Rhyme

いい感じの Greedy 問題 問題へのリンク 問題概要 個の文字列 が与えられる。2 つの文字列 について、 の最後 i 文字と、 の最後 i 文字が共通 の後ろから i 文字目も、 の後ろから i 文字目も c である という条件を満たすとき、ラベル (i, c) をつけながら…

AtCoder ABC 123 D - Cake 123 (400 点)

priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった!!!!!! 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…

AtCoder AGC 005 B - Minimum Sum (400 点)

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

Educational Codeforces 62 C - Playlist (R1600)

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