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

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

AtCoder

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…

AtCoder ABC 026 D - 高橋君ボール1号 (水色)

方程式を解くタイプの二分探索の問題ですね。 問題へのリンク 問題概要 正の整数 が与えられます。 秒後のボールの位置 は で表されます。 を満たす実数 の値を十分高い精度で求めてください。 を満たせば正解とみなされます。 制約 解へのアプローチ の解を…

AtCoder ARC 037 C - 億マス計算 (青色)

二分探索法の教育的典型問題ですね!! 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…

AtCoder ABC 206 C - Swappable (灰色, 300 点)

包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1):約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…

AtCoder ABC 206 F - Interval Game 2 (黄色, 600 点)

Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…

AtCoder ABC 014 C - AtColor (水色)

いもす法の典型問題 問題へのリンク 問題概要 サイズ 1000001 の配列 v が与えられる (index は、0, 1, ..., 1000000)。 以下の 回の操作を行う。 回目の操作では、 を満たす について、v[x] に 1 を加算する すべての操作を行ったあとの、配列中の値の最大…

AtCoder ABC 014 D - 閉路 (青色)

木上のパスに関する問題!! LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…

AtCoder ABC 019 D - 高橋くんと木の直径 (水色)

木の直径の求め方を知っていれば解ける!! 問題へのリンク 問題概要 頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。 そのために、以下のクエリを 100 回まで投げることがで…

競プロ典型 90 問 003 - Longest Circular Road(★4)

木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …

競プロ典型 90 問 002 - Encyclopedia of Parentheses(★3)

整合したカッコ列を bit 全探索する問題!!! 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問…

AtCoder ABC 023 D - 射撃王 (青色)

大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。 問題へのリンク 問題概要 個の風船がそれぞれ初期状態では高度 の位置にあり、1 秒ごとに ずつ上昇する。これらすべての風船を射撃によって割りたい。 競技開始時に 1 個風船…

競プロ典型 90 問 001 - Yokan Party(★4)

「最小値の最大化」 (or 「最大値の最小化」) には二分探索が有効という典型ですね。 類題とか (二分探索以外の問題も含むことと、ハイレベルな問題も多いことに注意) drken1215.hatenablog.com 問題へのリンク 解説へのリンク 問題概要 長さ のようかんがあ…

AtCoder ARC 117 C - Tricolor Pyramid (青色, 600 点)

面白かった。リハビリになった。 問題へのリンク 問題概要 長さ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。 それぞれの隣り合う 2 文字に対して それらが同じ文字な…

AtCoder AGC 053 A - >< again (水色, 400 点)

自明な上界を達成できるパターンだった! 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

「決めてから、整合性を確認する」というタイプの問題の典型例ですね! 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …

AtCoder ARC 115 E - LEQ and NEQ (黄色, 700 点)

間に合わなかった!!!悔しい!!! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…

AtCoder ABC 196 C - Doubled (灰色, 300 点)

いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする! 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…

AtCoder ABC 193 D - Poker (緑色, 400 点)

発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …

AtCoder ABC 193 C - Unexpressed (灰色, 300 点)

むずかしかった!!! でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった!! 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…

AtCoder ABC 077 C - Snuke Festival (ARC 084 C) (緑色, 300 点)

lower_bound の練習に!!! あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…

パ研合宿2020 第1日「SpeedRun」 N - 背の順

面白かった!セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね! 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…

JOI 春合宿 2007 day3-2 Route (難易度 7)

DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

AtCoder ABC 187 C - 1-SAT (灰色, 300 点)

とにかく実装力を鍛えよう〜〜 問題へのリンク 問題概要 個の文字列が与えられる。そのうちのいくつかは先頭の文字が ! である (それ以外はすべて英小文字)。 red gray !orange yellow !blue cyan !green brown !gray ! の付いていない文字列と、付いている…

AtCoder ABC 187 D - Choose Me (茶色, 400 点)

ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…

AtCoder ABC 187 E - Through Path (水色, 500 点)

これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…