お題箱より。 E - Second Sum 解法 まずは「数え上げの順番をひっくり返す」という発想が大事です。 全ての区間 について、その区間内で2番目に大きい値 を求め、合計する をひっくり返して、 順列内の全ての要素 について、その要素が2番手になるような区間…

イマイチ良い言葉が見つからなかったのでタイトルが長くなりました。最近見る機会が多かったので記事を書いてみます。 以下のような形に帰着されるような区間の数え上げに使えるテクニックです。 例題 以下の2つの数列が与えられる。 左端から見た右端の条件…

Problem - F - Codeforces 問題概要 整数 と、整数の組 が 個与えられる。以下の条件を満たす長さ の整数列 の個数を で求めよ。 全ての要素は を満たす。 整数の組 で表現される以下の条件を 個全て満たす。 のビットANDを取った値がちょうど となる。 制約…

D - Merge Triplets 解法 操作の説明で登場する長さ の数列たちを「ミニ数列」と呼ぶことにします。 結果的にできる順列にどのような特徴があるかを考える上で、まず一番大きな値に注目すると良いと思います。 最大値 は、 が存在しているミニ数列以外の要素…

Problem - E - Codeforces 問題概要 から までの順列 が与えられる。 爆弾が仕掛けられているインデックスの集合 を考える。 に対して以下のように計算される値を と定義する。 を空集合とする。 の順に以下の操作を行う。 集合 に を追加する。その後 なら…

Problem - G - Codeforces 問題概要 個の相異なる英小文字列からなる集合 がある。この集合の要素 それぞれについて以下を求めよ。 文字列 を空文字列から始めて、以下の2つの操作を好きな順番で繰り返して と一致させるための最小コストを求めよ。 操作1： …

Problem - C - Codeforces 問題概要 左側、右側それぞれに 個の頂点があり、その間に合計 本の辺が存在する二部グラフが与えられる。右側の頂点にはそれぞれ正整数 が書かれている。 左側の頂点の部分集合 について、 を「右側の頂点のうち の要素のいずれか…

お題箱より。 B - 準急電車 (Semiexpress) 解法 後戻りできないこと、急行が停まる駅には必ず準急も停まることから、駅 からある目的駅までの最適な移動経路は「行けるところまで急行で行く→行けるところまで準急で行く→残りは普通で行く」となります。 その…

Problem - E - Codeforces 問題概要 整数 が与えられる。以下の条件を満たす長さ の数列 を1つ構築するか、そのようなものが存在しないことを判定せよ。 各要素は 以下の正整数である。 狭義単調増加である。 かつ を満たす3つ組 の個数はちょうど 個である…

お題箱より。 Programming Problems and Competitions :: HackerRank 公式解説はこちらで公開されています。 ゆるふわオンサイト#3 解説 - Google スライド 解法 2点をswapするクエリを処理するような問題は、swapであることを上手く活用するような解法も考…

お題箱より。 Problem - E - Codeforces 問題概要 頂点の木が与えられ、各頂点には a から t までのうち1文字のアルファベットが書かれている。 この木の2点間を結ぶパスであって、「通過する頂点のアルファベットを並び替えることで回文にすることができる…

お題箱より。 Problem - E - Codeforces 問題概要 整数 が与えられる。頂点数 の木であって、根を頂点 としたときに二分木になっていて、全頂点の深さ（根までの距離）の合計が であるものを構築せよ。またはそのような二分木が存在しないことを判定せよ。 …

Programming Problems and Competitions :: HackerRank 解法 最初の気付き まず初手に気づけるかどうかが勝負です。この問題は、以下のような2本の経路のペアを数える問題に言い換えられます。 このように、下と右の移動だけで左上隅→右下隅を結ぶ経路と、上…

お題箱より。 D - Ki 様々な木の問題を解く上で基本となるような実装なので、実装も含めて解説します。 解法 1回の操作のイメージを図にすると以下のようになります。 実際には大量の操作があるので、これを1つ1つ処理していくことはできません。ではどうす…

お題箱より。 Problem - B - Codeforces 問題概要 頂点の無向完全グラフがある。このグラフの辺のうち、指定される 本の辺の重みは であり、それ以外の辺の重みは全て である。 このグラフの最小全域木の重み合計を求めよ。 制約 解法 クラスカル法のアルゴ…

Problem - D - Codeforces 計算量がキツキツなので想定解じゃないような気もするのですが、通せたので私の解法を書きます。 問題概要 頂点の有向完全グラフが与えられ、各辺にコストが設定されている。 頂点1からスタートしてちょうど 辺を通って頂点1に戻る…

お題箱より。 Problem - F1 - Codeforces 問題概要 Polycarpは初期評価 のフリーランスである。 依頼が 個ある。 番目の依頼は受諾時点で 以上の評価が必要であり、完了後に評価が 変化する（これは負であることもあり得る）。依頼の順序は好きに選んで良い…

先日やっていたバチャで出てきたので、まとめておきます。 この記事では二項係数を と表記します。また法を とします。 はじめに が必要となる の最大値をそれぞれ として、 や が許される制約であれば、パスカルの三角形で全部計算できます。こちらのほうが…

バチャでやってて結構面白かったので。 Problem - G - Codeforces 問題概要 以下のように構成される、頂点数 ・辺数 の有向グラフを考える。 頂点は 個ずつの2グループに分類され、それぞれAパート・Bパートと呼ぶ。頂点を 、 と表記する。 について、 から …

Problem - E - Codeforces 問題概要 本の草が横一列に並んでいて、 本目の草の味は整数 で表現される。また 頭の牛がいて、 頭目の牛は味 の草を好み、それを 本食べると満足する。 以下の処理を行う。 互いに素な牛の集合 を選ぶ。一方または両方が空であっ…

E - Payment 上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。 解法 上の桁から見ていって、その桁までで支払う＆お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。 例えば 円だったとして、 の位の桁まで…

D - Pairs ※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。 解法 二分探索に落とし込む 与えられた数列などに対して大量の数を計算し、その 番目…

Problem - E - Codeforces 問題概要 のマス目が与えられ、各マスは赤・緑・黄・青のいずれかに塗られている。 このマス目から の連続する正方形領域を取り出したときに、それが問題文の図の位置関係通りに4色の の正方形で構成されているとき、これをレベル …

Problem - F - Codeforces ※解説の都合上、マスに書かれている整数を「色」と表現することにします。記号も だし。 問題概要 のマスからなる盤面があり、各マスには色が塗られている。このマスそれぞれを頂点とし、隣り合うマスの色が等しいときにその間に辺…

Problem - C - Codeforces 問題概要 ※0-indexedで記載します。 実数列 が与えられる。（初期状態では各要素は正整数） この実数列に対して、「ある連続する区間を選び、その区間に含まれる要素全てをそれらの平均で置き換える」という操作を好きな回数繰り返…

お題箱より。 E - Children and Candies 部分点解法から満点解法へのステップアップについて重点的に書きます。 解法 部分点解法 部分点解法は公式解説にもしっかり書かれているので軽く。各 について なので、ある1つの組 に対してだけ を求めてください、…

Problem - C - Codeforces コンテスト本番は闇実装に突っ込んだので、ながたかなさんの解法をベースに書き直しました… 問題概要 ※解説・コードと合わせるため0-indexedで記述します。 番号 の電球が並んでいて、それぞれ初期状態でON/OFFどちらになっている…

Problem - F - Codeforces 問題概要 問の問題からなるコンテストがある。 番目の問題の正解者数は、区間 に含まれる整数の中から等確率で決まる。 問題 の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、 で出力せよ。 制約 解法 問題 …

No.980 Fibonacci Convolution Hard - yukicoder 変な解き方をしました…。後述するように厳密に正しい解法ではないので、あまりオススメはしません。 解法 0-indexedのほうが楽なので、数列 を あとは同様の漸化式で定義される数列、としておきます。クエリ…

Problem - E - Codeforces 問題概要 ※解説と合わせるために0-indexedで表記します。 長さ の順列 が与えられる。また を移動させるためのコスト がそれぞれ与えられる。 この順列に対して以下の処理を行う。 順列の隣り合う2要素間の境界を自由に選び、左グ…