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

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

操作の流れを単純化する

AtCoder ABC 323 F - Push and Carry (水色, 525 点)

怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…

Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad (R??00)

区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

AtCoder ABC 286 C - Rotate and Palindrome (茶色, 300 点)

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

DISCO presents 2016 予選 C - アメージングな文字列は、きみが作る! (橙色)

とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…

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

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

JOI 二次予選 2021 D - 安全点検 (AOJ 0694, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

AtCoder AGC 049 C - Robots (黄色, 800 点)

11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…

AOJ 2681 Parentheses (JAG 春コン 2014 E) (500 点)

めちゃくちゃ面白かった! 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…

AtCoder ABC 180 D - Takahashi Unevolved (茶色, 400 点)

2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…

AOJ 2956 ジャム (Jam) (HUPC 2019 day2-E)

こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…

AOJ 3170 Freqs (HUPC 2020 day1-G)

難しかったー!!平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…

Educational Codeforces Round 84 F. AND Segments (R2500)

実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…

Codeforces Round #618 (Div. 1) C. Water Balance (R2100)

これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…

Codeforces Round #615 (Div. 3) E. Obtain a Permutation (R1900)

こういうのをちゃんと解けるようになったのは成長! 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…

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

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

diverta 2019_2 D - Squirrel Merchant (青色, 600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。 問題へのリンク 問題概要 問題画像そのままを 解法 1: 自分のやつ 僕が最初に考えたことは、例えば 「最初…

AtCoder ABC 128 D - equeue (水色, 400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

みんなのプロコン 2019 C - When I hit my pocket... (茶色, 400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…

AtCoder ABC 124 D - Handstand (緑色, 400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AOJ 3059 Shuffle 2 (RUPC 2019 day2-I)

与えられた操作を「わかりやすいものに読み替える」というのが本質な問題だと思う。AtCoder でもよく見られるタイプの 問題へのリンク 問題概要 の書かれた 枚のカードを順に並べたものに対し 左から偶数番目のみを順に取り出して並べたものを A 右から偶数…

AtCoder ABC 119 C - Synthetic Kadomatsu (水色, 300 点)

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう!!!!! 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…

みんなのプロコン 2019 D - Ears (青色, 600 点)

郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。 問題へのリンク 問題概要 すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。 このとき、各区間 [ ] () に…

AtCoder AGC 008 A - Simple Calculator (茶色, 300 点)

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を繰り返す 最後…