この問題を解説 AC しました。 全く考えもしなかった方針なので、とても面白いと感じました。 問題概要 個の区間が与えられる。 を被覆する区間の subset の最小コストを求めよ。 コスト: subset 中の 区間に与えられる の 考えたこと 1. DP かな〜。やっぱ…

CodeForces #752 (div.2) バチャ A: a[i]-i の最大値 B: n が奇数かつ、転倒数が 0 -> NO C: はどうせ絶対できるので、それ以下を全探索 D: 解けませんでした...... 解説を読む限り、図を描くと分かりやすい問題でしたECR 109 - C: Robot Collisions odd と …

この問題を自力 AC しました。バチャでは前の E に詰まって F まで見れませんでした、E に詰まったら F を見よう！の典型ができませんでした。 問題概要 文字列 と長さ の文字列 、整数 が与えられる。文字列 の任意の要素を任意の文字に置き換える操作を 回…

この問題を(バチャ終了半年後の今日)自力ACしました。解法自体はわかっていましたが、実装に詰まって放置していました。 問題概要 配列 が与えられます。両端の連続部分列の最大値 と、真ん中の連続部分列の最小値 が一致するように、配列を三分割しなさい。…

div. 3 ボス問解説、すっかりやるのを忘れていましたね。こどふぉの問題は何故か頭に残りにくいので、ちゃんと頭に残すためにも、解き直して（実装はしない）解説をしていくことにしました。 問題概要 頂点 辺の重み付き無向グラフがあります。 個の始点と終…

これのバチャをしました。 ボス問を解説するつもりでやっていますが、ボス前のほうが難しかったので、そっちをやります。 問題概要 Polycarp 君は 円稼ぎたいです。彼が1日のうちに取れるアクションは、現在の彼のレベルを として、 a[x] 円稼ぐ b[x] 円払い…

バチャでこの問題を自力ACしました。 全完気持ち〜〜 の反面、得意分野の問題に時間をかけすぎてしまい、反省です。 問題概要 頂点の木があり、各頂点には-1か1が割り当てられています。各頂点について、自身を含む部分木のうち、部分木の頂点に書かれている…

先日行われた第二回日本最強学生選手権で224位perf 2127 を取り、AtCoder 1級になりました！！！ せっかく昇級したので、喜びの声ついでにブログを書こうと思います！！！！！！！！！！！！！！！！！ とりあえず各種記録から↓↓ レーティング遷移 各コンテ…

ARC114お疲れさまでした。ABC3完で温まれてうれしいです。この問題を僕と同じ解き方をした人が少なかったので、自分の解法を紹介します。 問題概要 日本語問題文があるので割愛 解法 大まかな方針は 『愚直な操作回数 から不要な操作を引いていく。』です。 …

これを自力ACしました。バチャ中はEに引っかかってここまでたどり着けなかったけど、先にFを見ておくべきでした...。 問題概要 数列 が与えられる。以下の操作を繰り返して 内に少なくとも 個の等しい要素を取得しなさい。 内の最大の要素の大きさを 1 小さ…

これを自力ACしました 見た瞬間に方針が立つものの、実装方針を詰める&実装嫌だ〜〜とうだうだする&実装する をしていたらバチャ中に間に合わず、悔しいです... 問題概要 行 列のグリッドグラフが与えられる 。グリッドグラフには色と方向が示してある。毎タ…

これを自力ACしました。 バチャ中に通し切ることができずに悔しいです。最適な経路を考えると、どこか一つの頂点は最初と同じ高さを保っているとわかります。 操作を行わない頂点を固定してBFSをすると、できます。 計算量は です。バチャ中の立ち回り。 map…

これを解説ACしました。 連続部分列に関する条件が複数与えられ、条件を満たす順列を構成する問題。 条件をよく見ると、一番右の数字は1度しか登場しないことがわかる。・・・(1) 条件を更新していきながら構築をしていくとできそうだけど、実はできない。 …

これを解説ACしました。 問題概要 長さ の配列 が与えられる。 配列内の要素を先頭に持っていく/最後尾に持っていく という操作を繰り返してソートしたい。 最低何回ソートをする必要があるか？ 言い換え ソート後の配列の連続部分列かつ の部分列である配列…

ぷ～べあさん(Twitter)とAtCoder Problemsのlockout形式のバーチャルコンテストをやりました。 最近話題になっているので僕もやりたいな～～と思っていたらぷ～べあさんも対戦相手を募集してそうだったので、やりませんか？と声を掛けたら快諾してもらえまし…