こどふぉ div. 3 ボス問
この問題を自力 AC しました。バチャでは前の E に詰まって F まで見れませんでした、E に詰まったら F を見よう!の典型ができませんでした。 問題概要 文字列 と長さ の文字列 、整数 が与えられる。文字列 の任意の要素を任意の文字に置き換える操作を 回…
この問題を(バチャ終了半年後の今日)自力ACしました。解法自体はわかっていましたが、実装に詰まって放置していました。 問題概要 配列 が与えられます。両端の連続部分列の最大値 と、真ん中の連続部分列の最小値 が一致するように、配列を三分割しなさい。…
div. 3 ボス問解説、すっかりやるのを忘れていましたね。こどふぉの問題は何故か頭に残りにくいので、ちゃんと頭に残すためにも、解き直して(実装はしない)解説をしていくことにしました。 問題概要 頂点 辺の重み付き無向グラフがあります。 個の始点と終…
これのバチャをしました。 ボス問を解説するつもりでやっていますが、ボス前のほうが難しかったので、そっちをやります。 問題概要 Polycarp 君は 円稼ぎたいです。彼が1日のうちに取れるアクションは、現在の彼のレベルを として、 a[x] 円稼ぐ b[x] 円払い…
バチャでこの問題を自力ACしました。 全完気持ち〜〜 の反面、得意分野の問題に時間をかけすぎてしまい、反省です。 問題概要 頂点の木があり、各頂点には-1か1が割り当てられています。各頂点について、自身を含む部分木のうち、部分木の頂点に書かれている…
これを自力ACしました。バチャ中はEに引っかかってここまでたどり着けなかったけど、先にFを見ておくべきでした...。 問題概要 数列 が与えられる。以下の操作を繰り返して 内に少なくとも 個の等しい要素を取得しなさい。 内の最大の要素の大きさを 1 小さ…
これを自力ACしました 見た瞬間に方針が立つものの、実装方針を詰める&実装嫌だ〜〜とうだうだする&実装する をしていたらバチャ中に間に合わず、悔しいです... 問題概要 行 列のグリッドグラフが与えられる 。グリッドグラフには色と方向が示してある。毎タ…
これを自力ACしました。 バチャ中に通し切ることができずに悔しいです。最適な経路を考えると、どこか一つの頂点は最初と同じ高さを保っているとわかります。 操作を行わない頂点を固定してBFSをすると、できます。 計算量は です。バチャ中の立ち回り。 map…
これを解説ACしました。 連続部分列に関する条件が複数与えられ、条件を満たす順列を構成する問題。 条件をよく見ると、一番右の数字は1度しか登場しないことがわかる。・・・(1) 条件を更新していきながら構築をしていくとできそうだけど、実はできない。 …
これを解説ACしました。 問題概要 長さ の配列 が与えられる。 配列内の要素を先頭に持っていく/最後尾に持っていく という操作を繰り返してソートしたい。 最低何回ソートをする必要があるか? 言い換え ソート後の配列の連続部分列かつ の部分列である配列…
codeforces.com 上の回をやりました。 A~C2までの3完でした。終了後にDとEを解きました。 A. Ropewalkers ソートしてmax(0,d-a[1]+a[0])+max(0,d-a[2]+a[1]) B. Email from Polycarp それぞれをランレングス圧縮をして、圧縮後の長さが同じかつ、全てのindex…
Codeforces Round674に参加しました(ratedだと思ってたらunratedだった......)、結果は1:19で全完しました(プレテストあるのかな?知らない)!! a. Floor Number Petyaくんの住んでいる部屋番号が与えられるので、何回に住んでいるかを答えなさい。 な…