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

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

2019-12-01から1ヶ月間の記事一覧

AtCoder ARC 097 F - Monochrome Cat (赤色, 800 点)

とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…

AtCoder ARC 059 F - バイナリハック / Unhappy Hacking (橙色, 800 点)

面白かった 問題へのリンク 問題概要 長さ の '0' と '1' と 'B' からなる文字列 として、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 空文字列に対し、 を左から順に見て、以下の操作を順に行ってえられる文字列が に一致…

AOJ 1595 Traffic Tree (AUPC 2016 day2-I)

全方位木 DP の練習も兼ねて 問題へのリンク 問題概要 頂点数 のツリーが与えられる。ツリーの各頂点 に対して、 から出発して全頂点を訪れるまでに通る辺の本数の最小値を求めよ。 制約 解法 1: 全方位木 DP 1 つの根についての答えなら普通の木 DP で求め…

Codeforces Round #479 (Div. 3) F. Consecutive Subsequence (R1700)

教育的で楽しい 問題へのリンク 問題概要 長さ の数列 が与えられる。数列中の部分列 (連続でなくてよい) であって、連続する自然数となっているもののうち、最長のものを求めよ。 また、それを復元せよ (添字を答える)。 ex: (3, 3, 4, 7, 5, 6, 8) -> (3, …

Xmas Contest 2019 J - Sub-Post Correspondence Problem

信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…

AtCoder AGC 023 A - Zero-Sum Ranges (緑色, 200 点)

200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました! qiita.com

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

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

AtCoder ABC 148 C - Snack (灰色, 300 点)

結構、そのまんまな問題が来ましたね。 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 でも でも割り切れる正の整数のうち、最小の値を求めよ。 制約 考えたこと すごくそのまんまですね。 と の最小公倍数を求めよ、という問題。実は と の最大公…

AtCoder ABC 148 D - Brick Break (灰色, 400 点)

とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…

AtCoder ABC 148 E - Double Factorial (緑色, 500 点)

じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。 問題へのリンク 問題概要 以上の整数 が与えられる。 を計算した値において、末尾に何個の 0 がつくのかを求めよ。 制約 考えたこと これとよく似た形で、たとえば の末尾に 0 が何個つくか…

AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点)

| x - a | + | x - b | + | x - c | + ... の最小値を求める問題には定石があるぞいぞい 問題へのリンク 問題概要 長さ の整数列 が与えられます。整数 をいろいろ変えたときの の最小値を求めてください。 制約 考えたこと 非本質だけど、 って普通「変数」…

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

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

動的計画法で求めた解を全列挙する方法

きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ!複数通りある場合は列挙!みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…

AtCoder ABC 111 C - /\/\/\/ (ARC 103 C) (緑色, 300 点)

意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…

AtCoder ARC 085 E - MUL (橙色, 700 点)

いわゆる「燃やす埋める」の典型です。 問題へのリンク 問題概要 個の整数 が与えられます (負値もありえます)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができます。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 …

AtCoder ARC 085 F - NRE (赤色, 1000 点)

実家なんだと思うけど...意外とはまりやすい問題な気 がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…

AtCoder ARC 103 F - Distance Sums (赤色, 900 点)

900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった!!! 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。…

AtCoder ABC 147 C - HonestOrUnkind2 (緑色, 300 点)

とても教育的な問題でしたね!!! ここにまとめました! drken1215.hatenablog.com 以下のような問題です。bit 全探索とよばれているもので、 通りの選択肢をすべて調べ上げる手法を用います。 問題概要 人がいて、それぞれ「正直者」であるか、「不親切な…

bit 全探索

0. はじめに ビット演算については、以下の記事で特集しました。 qiita.com しかし、この中で、bit 全探索に関する説明がだいぶ簡潔すぎたので、ちゃんと書きたいなと思って、この記事書きます!!!ただし、ビット演算に関する知識は前提としているので、そ…