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

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

復元

AtCoder ABC 133 D - Rain Flows into Dams (400 点)

時々こういうの見る気がする。とりあえず求めたい値を と置いてみる感じ。 問題概要 を奇数とする。整数 が与えられるので ... を満たすような を求めよ。 制約 は奇数 考えたこと 問題の構造として 「 を決めると、残りが芋づる式にすべて決まってしまう」 …

diverta 2019_2 C - Successive Subtraction (500 点)

復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…

AtCoder AGC 006 B - Median Pyramid Easy (400 点)

これの Easy バージョン。すごく楽しくて好き!!!!! Easy:操作の結果が所望になる入力を求める逆問題 Hard:操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …

AtCoder AGC 002 C - Knot Puzzle (500 点)

気づけばすぐな感じかな 問題へのリンク 問題概要 本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく …

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

AtCoder AGC 032 A - Limited Insertion (400 点)

好き!!!!!でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…

AOJ 3059 Shuffle 2 (RUPC 2019 day2-I)

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

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…

AOJ 1392 Shortest Common Non-Subsequence (ICPC アジア 2018 D)

ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン! 問題へのリンク 問題概要 2 つの '0' と '1' で構成された文字列 S, T が与えられる。 S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…

AtCoder ARC 081 E - Don't Be a Subsequence (600 点)

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 (ARC 081 E) 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制…

AtCoder ABC 109 D - Make Them Even (400 点)

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 (ABC 109 D) 縦 行、…

Codeforces 502 C - The Phone Number

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

CS Academy 084 DIV1 C - Split the Sticks

これは楽しい 問題へのリンク 問題概要 個の整数 が与えられる。 今ある整数の中から 1 個 ( とする) を選んで、好きな整数 を選んで、 を と に分裂させる という操作を繰り返して、最終的に得られる整数の集合が、まったく同一の 2 つの集合に分けられるよ…

Codeforces 190 DIV1 C - Ciel the Commander (重心分解)

てんぷら君が解いていたのを見て... 問題へのリンク 問題概要 頂点のツリーが与えられる。 ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。 任意の 2 頂点 u, v について、u…

CS Academy 081 DIV2 E - Fold Polygon

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題なん。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速…

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかったん。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そうなん... ツリーの重心に関する理解が足りてないことがわかったので勉強してまとめたのん。 ツリーの重心分解 (木の重心分解) の図解 - Q…