こういうの典型なんですかね？結構面白い気がしたのでブログに残しておく 問題概要 原文 → Problem - G - Codeforces 個の箱が一列に並んでいる。箱の中身は石またはギフトである。石が入っている箱はすべて同じ重さであり、ギフトが入っているどの箱よりも…

はじめに これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。 ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ) https://hcpc-hokudai.github.io/archive/algorithm_divide_and…

問題概要 原文 → Problem - D2 - Codeforces 0 と 1 のみからなる長さ の文字列 が与えられる。 の文字を、以下の条件が満たされた上で変更することを考える。 全ての に対して、 の 文字目から 文字目までのみからできる最長単調非減少列の大きさが元の文字…

本番は嘘解法で通してしまったのでちゃんと書きます。 問題概要 原文 → Problem - D - Codeforces のグリッド状のマスが与えられ、それぞれは白または黒に塗られている。 このマスの任意の 長方形領域に対して、その領域内にあるマスを全て白にするという操…

問題概要 原文 → Problem - D - Codeforces 長さ の整数列 と、パラメータ が与えられる。 数列内の連続する閉区間 について、そのコストは で表される。なお、空の区間に対するコストは である。 あり得る全ての区間を考慮した時のコストの最大値を求めよ。…

問題概要 原文 → Problem - E - Codeforces 色のボールがあり、 番目の色で塗られたボールは 個ある。 これらのボールを以下の条件を全て満たすように箱に入れる。 それぞれの箱について、箱の中にあるボールの色は 種類のみ 空箱が存在しない 箱に入ってい…

問題概要 原文 → Problem - F1 - Codeforces 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。 木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これ…

問題概要 原文 → Problem - E - Codeforces 頂点からなる根付き木が与えられる。根は頂点 であり、木の各頂点には色 がついている。 各頂点 について、 を根とする部分木に存在する頂点の中で、塗られている個数が最も多い色を求め (タイもすべて数えるため…

問題概要 原文 → Problem - F - Codeforces の倍数 と、整数 が与えられるので、以下を全て満たす正の整数集合を構築できるかどうか判定せよ。 要素数は で、値は全て 以下で相異なる の各元 について、要素を で割ったあまりが になるような、集合内の要素…

問題概要 原文 → Problem - E - Codeforces '.' または 'z' のマスのみからなる の盤面が与えられる。この盤面内に存在する「Z 型」の正方形領域がいくつ存在するか求めよ。 Z 型の正方形領域の定義 最も上と最も下の行は全て 'z' 反対角成分は全て 'z' それ…

問題概要 原文 → Problem - F - Codeforces 以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。 点集合に を追加する 点集合から を削除する 点 が与えられる。その時点の点集合について、原点 と を結んでできる直線に対して線対…

問題概要 原文 → Problem - E - Codeforces 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。 解説 森を木に分割して、木同士をマージするこ…

問題概要 原文 (D1) → Problem - D1 - Codeforces 原文 (D2) → Problem - D2 - Codeforces 長さ の数列が与えられる。以下の操作を繰り返し行うことによって、全要素の値を等しくしたい。 D1 で認められる操作 値が同じである隣り合う要素を選び、その両方に…

問題概要 原文 → Problem - C - Codeforces 文字の文字列 があり、あなたは が全体としてどのような文字列であるかは知らない。しかし、長さが から までの全ての prefix と suffix についての情報は持っている (ただし、どれが prefix でどれが suffix かは…

本番出てた回。ようやく復習できました。 問題概要 原文 → Problem - C - Codeforces 長さ の数列があり、 番目の要素を と書く。 次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合…

問題概要 原文 → Problem - 733C - Codeforces サイズの配列と、サイズの配列が与えられる。配列に対して、隣り合う要素が自分より小さい場合、自分にその要素の値を加算し、その要素を削除する操作(つまりマージ)が可能である。この操作を繰り返して配列を…